프로그래머스[Java] - (Level2)쇠막대기(스택/큐)

https://programmers.co.kr/learn/courses/30/lessons/42585

프로그래머스

코드

import java.util.*;

class Solution {
    public int solution(String arr) {
        int answer = 0;
        Stack<Character> s = new Stack<Character>();
        
        for(int i=0; i<arr.length(); i++){
            // 현재 값이 '(' 인 경우 -> 스택에 쌓기
            if(arr.charAt(i) == '(')
                s.push('(');
            
            // 현재 값이 ')' 인 경우 -> 이전값이 '('인지 ')'인지 판단.
            else{      
                s.pop();     // 스택에서 '(' 하나 제거
                if(i>0 && arr.charAt(i-1) == '(')   
                    answer += s.size(); // '()' 인 경우 -> 레이저
                else    
                    answer ++;   // '))' 인 경우 -> 쇠막대기가 하나 끝나는경우
            }
        }
        return answer;
    }
}

풀이

Stack을 이용해 해결했다.

현재 값이 '(' 이냐, ')' 이냐를 기준으로 판단하는데,,

아래 사진에서 보듯 레이저는 연달아 나오는 '()'쌍 이다.

레이저에 의해 잘리는 쇠막대기의 갯수는 레이저'()' 가 오기 전 '(' 의 갯수(쇠막대기 갯수)와 같다.

(앞에서 잘린것만 생각하고 뒷부분은 생각하지 않는다.)

쇠막대기가 닫히는 구간 - ')' 가 오는 곳은, 아래에서 표시한 부분인데 닫히는구간에서는 쇠막대기가 한개씩 증가한다.

 

● 현재 문자가 '(' 인 경우

  - 스택에 그대로 쌓는다.

 

● 현재 문자가 ')' 인 경우

  - 스택에서 '(' 하나를 제거한다.

 

  - 이전 문자가 '(' 인 경우 -> 연달아 나오는 '()'쌍 이므로, 레이저이다.

  - 따라서 쇠막대기의 갯수(이전 '('의갯수 = 스택의 사이즈) 만큼 더해준다.

 

  - 이전 문자가 ')' 인 경우 -> 레이저가 아닌 쇠막대기가 끝나서 닫히는 부분이다.

  - 따라서 쇠막대기의 갯수를 +1 해준다.

 

 

 

 

* 문제에서 연달아 나오는 쌍'()' 을 replace("()", "0"); 과 같이 치환해서 레이저를 구분해서 해결하면 더 간단하다.,

import java.util.*;
 
class Solution {
    public int solution(String arrangement) {
        int answer = 0;
        
        arrangement = arrangement.replace("()", "1");
        
        Stack<Character> a = new Stack<Character>();
        for(int i=0; i<arrangement.length(); i++) {
            char cursor = arrangement.charAt(i);
            if(cursor == '(') {
                a.push(cursor);
            } 
            else if(cursor == '1') {
                answer += a.size();
            }
            else if(cursor == ')') {
                answer += 1;
                a.pop();
            }
        }
        
        return answer;
    }
}

https://ju-nam2.tistory.com/46

[Java][프로그래머스][Level 2] 쇠막대기