코딩테스트 고득점 kit / 스택&큐 / 쇠막대기 / JAVA

 

풀이 방법1

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int solution(String arrangement) {
        int answer = 0;
        Deque<Character> stack = new ArrayDeque<Character>();
        char[] c = arrangement.toCharArray();
        
        for(int i=0; i<c.length; i++) {
        	
        	if(c[i] == '(') stack.push(c[i]);
        	else {
        		if(c[i-1] == ')') {
        			stack.pop();
        			answer++;
        		}else {
        			stack.pop();
        			answer += stack.size();
        		}
        	}
        }
        return answer;
    }
}

스택을 이용한 풀이방법 입니다.

')'가 들어올때마다 pop을 실행하고 스택안에 들어있는 '(' 의 개수를 카운트 합니다.

하지만 조그만 함정이 숨어있습니다.

여기서 키 포인트는 무조건 pop해서 size를 더해주면 다음과 같은 문제가 발생합니다.

 

왼쪽 그림과 같이 같은 pop이지만

하나는 쇠막대기의 끝 지점이고 다른 하나는 레이저 입니다.

 

따라서 ')'가 들어오면 배열에서 이전값이 '(' 였는지 ')'였는지 구분해서

다른 연산을 취해줘야 합니다.

 

즉, 이전값이 '('였다면 현재의 ')'는 레이저로 취급하여 size를 answer에 더해주면되고

이전값이 ')'였다면 현재의 ')'는 쇠막대기가 끝나는 지점으로 취급하여 answer에 1만 더해주면 됩니다.

 

 

 

 

 

히스토리

chucoding/algorithm