괄호 변환
문제정의
괄호의 짝이 맞도록 괄호 변환 프로그램을 개발하는 일이다. 감사하게도 변환하는 과정을 담은 알고리즘을 주었다. 변환 과정을 보고 오지 않은 사람들은 링크에서 보고 오길 바란다.
문제풀이
전체 코드는 다음과 같다. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91public class ConvertBracket {
//프로그래머스 문제풀이 level2 괄호 변환
public static void main(String[] args) {
String p = "()))((()";
String answer = "";
if(isCorrectBracket(p))
answer = p;
else
answer = ChangeBracket(p);
System.out.println(answer);
}
public static boolean isCorrectBracket(String s)
{
char[] arr = s.toCharArray();
int open = 0;
int close = 0;
for(char c : arr)
{
if(c == '(')
open++;
else
close++;
if(close > open)
return false;
}
return true;
}
public static String ChangeBracket(String s)
{
//1. 입력이 빈 문자열인 경우 빈 문자열을 반환합니다.
if(s.equals(""))
return "";
else
{
//2. u, v로 분리
String u = "";
String v = "";
char[] arr = s.toCharArray();
int open = 0;
int close = 0;
for(char c : arr)
{
if(c == '(')
open++;
else
close++;
if(open == close)
break;
}
int idx = open*2;
u = s.substring(0, idx);
if(idx < s.length())
v = s.substring(idx);
String temp = ChangeBracket(v);
//3.u가 올바른 문자열일 경우
if(isCorrectBracket(u))
return u + temp;
//4.u가 올바른 문자열이 아닐 경우
else
{
StringBuilder buff = new StringBuilder();
//4-1.
buff.append("(");
//4-2.
buff.append(temp);
//4-3.
buff.append(")");
//4-4.
u = u.substring(1, u.length()-1);
if(!u.equals(""))
{
char[] array = u.toCharArray();
for(int i = 0; i < array.length; i++)
array[i] = array[i] == '(' ? ')' : '(';
buff.append(array);
}
//4-5.
return buff.toString();
}
}
}
}
1 | String p = "()))((()"; |
함수를 실행하는 부분이다. p는 입력이고 p가 만약 올바른 괄호 문자열이라면 p그대로를 정답으로 한다. 그렇지 않으면 변환 프로그램을 거친다. 먼저 올바른 괄호 문자열인지 판별해 주는 isCorrectBracket함수를 살펴보자.
1 | public static boolean isCorrectBracket(String s) |
올바른 괄호 문자열인지 판별하는 방법은 간단하다. 닫은 괄호가 연 괄호보다 많아지는 순간 그 문자열은 올바르지 않다. 이를 그대로 코드로 구현하였다. open과 close를 이용해 닫는 괄호가 여는 괄호보다 많아지면 거짓을 반환하고 그렇지 않다면 참을 반환하도록 했다.
1 | public static String ChangeBracket(String s) |
제일 긴 괄호 변환 프로그램인데 해당 과정마다 주석을 달아놨다. 코드를 찬찬히 읽어보면 이해가 갈 것이다. 2과정에서 u는 더 이상 나누어지지 않는 균형잡힌 괄호 문자열이므로 처음으로 균형이 잡히면 반복문을 탈출한다.
이 코드의 시간 복잡도를 생각해보면 ')('가 여러 개 반복되는 패턴이다(재귀를 최대한 호출하기 때문이다.). 재귀의 반복횟수는 p의 길이를 N이라 할 때, \(log_{2}N\)이고, 재귀 안에서의 시간복잡도는 \(O(N)\)이므로, \(O(Nlog_{2}N)\)이 최종 시간복잡도이다.
테스트
카카오를 지원했을 때 2-3시간이 지나도 잘 못 풀었던 문제들을 풀어나가서 기쁘다. 비록 이것도 1시간이나 걸렸지만 앞으로 시간을 더 줄여나가야겠다.