Table of contents

프로그래머스 쇠막대기

굉장히 복잡해 보이지만, 사실 별로 어렵지 않은 문제이다.

계속해서 쇠막대의 시작지점인 '(' 를 스택에 저장하다가 레이저 '()'에 도달하는 순간 스택에 저장되어 있는 쇠막대의 개수를 누적한다.

결과는 3 + 3 + 3 + 2 + 1 = 12가 된다. 그런데, 위의 과정에서는 쇠막대의 종료지점에서 잘린 막대의 개수를 셀 수 없다. 쇠막대의 종료지점에 도달하는 경우 다음 레이저에서 해당 쇠막대는 잘리면 안된다. 이를 위해서는 마지막으로 스택에 저장된 쇠막대기를 꺼내야 한다.

스택에 저장된 쇠막대기를 꺼낼 때 주의해야할 점이 있다. (())의 경우를 생각해보자.

  • (
    • stack.push, size = 1
  • ()
    • 결과 += stack.size 누적
  • )
    • 쇠막대기 종료, 레이저에 의해 잘린 오른쪽 부분을 누적한다.
    • 결과 += 1

이처럼 쇠막대기가 종료되는 시점에는 해당 쇠막대에서 레이저에 의해 잘린 오른쪽 부분을 고려해서 결과에 1을 더해줘야한다.

 private int ironBar(String arrangement) {
     arrangement = arrangement.replace("()", "0");
     int answer = 0;
     Stack<Character> stack = new Stack<>();

     for (int i = 0; i < arrangement.length(); i++) {
         if (arrangement.charAt(i) == '(') {
             stack.push('(');
         } else if (arrangement.charAt(i) == ')') {
             stack.pop();
             answer += 1;
         } else if(arrangement.charAt(i) == '0') {
             answer += stack.size();
         }
     }
     return answer;
 }

편의를 위해서 레이저를 0으로 치환한다. 치환을 사용하지 않는다면 ')'를 만났을 때 이전 문자가 '('인지 확인하여 레이저인지 검사하면 된다.