백준 25918번 북극곰은 괄호를 찢어

문제 설명

이번 문제는 협이가 O와 X를 원하는 만큼 놓을 수 있고, 하루가 지나면 북극곰이 O는 '('와 ')'로 찢고 X는 ')'와 '('로 찢을 경우,

주어진 괄호 문자열을 만들기 위해서는 최소 며칠이 걸리는지 구하는 문제입니다.

 

문제 풀이

아이디어

스택

괄호가 어느 방향으로 존재하든 그 반대 방향의 괄호가 들어오면 해당 문자열 'O'나 'X'를 만들 수 있다는 것입니다. 그러므로 이전에 들어온 문자열과 비교할 수 있는 FIFO인 스택을 사용해보도록 하겠습니다.

 

하루보다 더 많이 걸리는 경우

만약 '()'와 ')('와 같이 다른 방향의 괄호가 나란히 왔을 경우, 해당 괄호 문자열은 하루만에 만들 수 있습니다.

만약 '(('와 '))' 같은 방향의 괄호가 나란히 나왔을 경우, 해당 괄호 문자열을 하루만에 만들 수 있는 문자는 없습니다. 그러므로 해당 문자열은 이틀에 걸쳐서 만들어질 수 있다는 뜻입니다.

 

여기서 스택을 이용해 괄호를 비교할 경우, 스택에 들어가 있는 이전 순서의 괄호와 비교해 같은 방향의 괄호가 들어온다면 스택에 push,

다른 방향의 괄호가 들어온다면 스택에서 pop해줍니다.

 

풀이

최소 날짜 구하는 방법

만약 '()'와 ')('와 같이 다른 방향의 괄호 문자열이 있다고 하면, 해당 괄호 문자열들은 모두 하루만에 만들 수가 있습니다.

만약 '(('와 같은 나란한 방향의 괄호 문자열이 있다고 하면, 해당 문자열들은 모두 스택에 들어가게 됩니다.(다른 방향의 괄호 ')'가 나올 때까지).

'(('와 같은 경우 '))'문자열이 나중에 등장한다면, 이 문자열은 2일만에 만들 수 있습니다. 그렇다는 것은 스택에 최대로 들어간 문자열의 길이가 해당 괄호 문자열을 만들 수 있는 길이가 된다는 것입니다.

 

그러므로, 반복문으로 괄호 문자열을 보고, 이전 괄호와 다른 방향의 괄호가 등장하면 스택에서 pop, 같은 방향의 괄호가 들어가면 스택에 push해주고 스택의 최대 길이를 출력해주면 됩니다.

(반복문이 종료됐을 때 스택에 문자열이 남아 있다면 -1을 출력합니다.)

 

 

해결

괄호가 이전 괄호와 같은 방향일 때, 다른 방향일 때에 따라 며칠이 필요한지를 생각해내면 해결해내기 어렵지 않은 문제였습니다.

 

문제 링크 : https://www.acmicpc.net/problem/25918

25918번: 북극곰은 괄호를 찢어

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/25918.py