[고득점Kit][스택] 쇠막대기 ⭐⭐

Date:     Updated:

카테고리:

태그:

C++로 풀이했습니다.
출처 : 프로그래머스 고득점 Kit 문제 풀이. https://programmers.co.kr/learn/challenges

[스택/큐] 쇠막대기

난이도 ⭐⭐

문제

image


내 풀이

정말 오랜만에 고민 길게 안하고 바로 풀었던 문제여서 뿌듯했다. 웬일인지 테스트 케이스들도 전부 한방에 통과하길래 얼떨떨.. 원래 같으면 실패실패실패실패.. 떠줘야 정상인데 ㅎㅎ..

#include <string>
#include <stack>
#include <vector>

using namespace std;

int solution(string arrangement) {
    int answer = 0;
    int count = 0;
    
    stack<char> stack;
    char pre = '(';
    
    for(int i = 0; i < arrangement.length(); i++)
    {
        if (arrangement[i] == '(')
        {
            stack.push(arrangement[i]);
        }
        else if (arrangement[i] == ')')
        {
            stack.pop();
            if (pre == '(')
                answer += stack.size();
            else if (pre == ')')
                count++;
        }
        pre = arrangement[i];
    }
    answer += count;
    
    return answer;
}

pre 👉 이전문자 / count 👉 쇠막대기의 개수가 될 것 (조각 말고) / answer 👉 쇠막대기의 총 조각 개수

  • (
    • 스택에 push
  • )
    • 레이저든, 쇠막대기 하나의 끝에 도달한 것이든, 가장 최근에 추가했던 (을 스택에서 pop()시켜 제거해야 한다. stack.pop()
    • 스택의 이전 문자가 (인 경우
      • () 즉, 레이저를 쏜 것!
      • 여태 스택에 들어있는 (들, 즉 쇠막대기에 레이저를 적용시켜 주어야 한다.
        • answer += stack.size();
        • 쇠막대기가 스택에 현재 3개 들어있다면 레이저 쏠시 answer에 3 더해주어야 함
    • 스택의 이전 문자가 )인 경우
      • )) 즉, 가장 최근 쇠막대기의 끝에 도달한 것!
      • 3 등분 하면 사실 4 조각이 되듯이 쇠막대기마다 레이저를 쐰 총 횟수에 1 을 최종적으로 더해주어야 한다. 따라서 쇠막대기 끝에 도달했으니 count에 1을 더해준다.
    • 이전 문자를 새롭게 업뎃 해준다.
  • 마지막으로 answer에 count를 더해준다.

image


살짝 아쉬운 점

  • precount는 필요 없다.
    • prearrangement[i-1]로, count는 그냥 else if (pre == ‘)’) 에서 answer++ 해주면 됐었다.
      int solution(string arrangement) {
      int answer = 0;
      int count = 0;
          
      stack<char> stack;
      char pre = '(';
          
      for(int i = 0; i < arrangement.length(); i++)
      {
          if (arrangement[i] == '(')
          {
              stack.push(arrangement[i]);
          }
          else if (arrangement[i] == ')')
          {
              stack.pop();
              if (arrangement[i - 1] == '(')
                  answer += stack.size();
              else if (arrangement[i - 1] == ')')
                  answer++;
          }
      }
      
      return answer;
      }
      


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

댓글남기기