[프로그래머스] [월간 코드 챌린지 시즌2] 괄호 회전하기

[문제 설명]

 

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

[제한사항]

s의 길이는 1 이상 1,000 이하입니다.

 

[입출력 예]

s	result
"[](){}"	3
"}]()[{"	2
"[)(]"	0
"}}}"	0

 

[입출력 예 설명]

입출력 예 #1

다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.

x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
0	"[](){}"	O
1	"](){}["	X
2	"(){}[]"	O
3	"){}[]("	X
4	"{}[]()"	O
5	"}[](){"	X

=> 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

 

입출력 예 #2

다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.

x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
0	"}]()[{"	X
1	"]()[{}"	X
2	"()[{}]"	O
3	")[{}]("	X
4	"[{}]()"	O
5	"{}]()["	X

=> 올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

 

입출력 예 #3

s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

 

입출력 예 #4

s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

 

[문제풀이]

올바른 문자열인지 아닌지만 탐색하면 되므로, 올바른 문자열이 아닌 경우의 수를 구현해주면 된다.

즉, 다음 3가지 경우를 생각해보자.

① (}) 이렇게 괄호 중간에 잘못된 닫힌 괄호가 들어온 경우

② ), }, ] 등 닫힌 괄호로 시작하는 경우

③ 괄호가 홀수개 입력되어 괄호 쌍이 맞지 않는 경우

 

문제를 풀기 위해 생각한 것들... 생각의 흐름 첨부

1. 문자열 s는 어떤 자료형으로 받지? string? char?
한글자씩 저장해야하니깐 char이 나을 거 같다.
근데 프로그래머스에 나와있는 기본틀은 string이라네 허허

 

2. 알고리즘의 대략적인 틀은?
1) 문자길이만큼 왼쪽으로 한칸씩 회전
2) 올바른 괄호인지 체크
3) 올바른 괄호이면 count값 1씩 늘려주기
4) 마지막에 count값 출력

3. 탐색시 빠져나올 조건?
거짓이 될 경우의 수

① ), }, ]로 시작하는 경우
② (, {, [로 끝나는 경우
③ 주어진 문자열의 길이(=개수)가 홀수인 경우

4. 올바른 괄호인지는 어떻게 체크하지?
문제 힌트에서 A가 올바른 괄호 문자열이면 (A) or [A] or {A} 도 올바른 괄호 문자열이라네?
예를 들어, []가 올바른 괄호 문자열이므로 ([]) 도 올바른 괄호 문자열인거...
근데 올바른 괄호를 어떻게 찾는지를 모르겟다.
검색해보니 (, {, [ 를 만날 때마다 stack에 넣어주고
), }, ] 를 만날 때 마다 가장 마지막에 넣은(최신) 여는 괄호가 맞는지 비교한다.
왜냐하면 안에 괄호가 올바른 괄호여야 바깥 괄호도 올바른 괄호일 수 있기 때문이다.
즉, 예를들어 (}) 이렇게 되면 정상적인 괄호가 아니다.
그럼 회전은 어떻게 표현해야 할까?
맨 앞에껄 빼서 뒤로 넣는 구조니까 queue를 이용해야겠다! -> 문제에선 string을 사용했으니 string을 사용해서 문자를 회전하는 법을 찾아봐야겠다.

---

구현 1차 시도...

 

닫힌 괄호를 만났을 때 (), {}, [] 를 어떻게 같다고 표현할지가 막힘..

 

구현 2차 시도

switch 문을 이용해서 열린괄호를 저장한 스택의 top과 현재 탐색하는 괄호 index를 비교하니깐 가능했다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int findCorrectBracket(string);	//올바른 문자열인지 아닌지를 체크하는 함수
string rotateString(string);	//문자열 길이만큼 왼쪽으로 한 칸씩 회전하는 함수

int main() {
	string bracketString;
	int correctNum = 0;

	cin >> bracketString;
	for (int idx = 0; idx < bracketString.length(); idx++) {
		correctNum += findCorrectBracket(bracketString);
		bracketString = rotateString(bracketString);
	}
	cout << correctNum;
}

string rotateString(string bracketString) {
	string firstString = bracketString.substr(0, 1);
	string subString = bracketString.substr(1, bracketString.length() - 1);
	return subString + firstString;
}

int findCorrectBracket(string bracketString) {
	int correctBracketNum = 0;
	stack<char> s_openBracket;

	for (int idx = 0; idx < bracketString.length(); idx++) {
		char closedBracket;
		char currentBracket = bracketString[idx];
		//올바르지 않은 괄호의 경우를 예외처리문으로 적어주고
		//그 외의 경우를 올바른 괄호라고 처리해주자.

		//열린괄호
		if (currentBracket == '(' || currentBracket == '{' || currentBracket == '[') {
			s_openBracket.push(currentBracket);
		}
		//닫힌괄호
		else {
			if (s_openBracket.empty()) { //바로 ),},] 같은 닫힌괄호로 시작하면 그건 올바른 괄호 문자열이 아님
				return 0;
			}

			switch (currentBracket) {	// (,{,[ 열린 괄호로 시작했으면 그 다음 예외처리를 따져보자.
			case ')':
				if (s_openBracket.top() != '(') { //직전 괄호가 (이면 이번 괄호는 )여야 올바른 괄호겠지
					return 0;
				}
				break;
			case '}':
				if (s_openBracket.top() != '{') { //직전 괄호가 {이면 이번 괄호는 }여야 올바른 괄호겠지
					return 0;
				}
				break;
			case ']':
				if (s_openBracket.top() != '[') {	//직전 괄호가 [이면 이번 괄호는 ]여야 올바른 괄호겠지
					return 0;
				}
				break;
			default:
				break;
			}
			s_openBracket.pop();	//올바른 괄호이면 top() 포인터를 한칸 옮겨서 다음도 올바른 괄호인지 체크해보자.
		}
	}
	if (s_openBracket.empty()) return 1;	//마지막까지 남김없이 올바른 괄호로 판단이 되었을 때 1을 return.
	else return 0;	// ★ 마지막에 { 하나만 남았다면 올바른 괄호가 아니니깐 이런 경우도 예외처리 해주기.
}

검색해보니 괄호 문자열을 애초에 ()는 1, {}는 2, []는 3이라고 표현해서 숫자가 같은지를 비교하기도 했다.

코드가 좀더 간단해질 거 같긴 하다~!

참고로 12번 Testcase에서 실패가 떴었는데, {, (, [ 같은 열린 괄호가 마지막에 올 경우를 계산하지 않았기 때문이었다.

 

시간복잡도

괄호 문자열의 길이 안에서 왼쪽으로 한칸씩 이동하는 경우 O(N)

현재 회전 결과 에서 괄호 문자열의 길이 만큼 차곡차곡 열린 괄호를 stack에 저장하고 탐색하는 경우 O(N) 으로

총 O(N²)의 시간 복잡도를 갖는다.