제출 코드
- 사용 알고리즘 :
자료구조,스택
문자열을 짝지어서 같은 문자끼리 없애고, 다시 붙이고를 반복하여 전체 문자열을 제거할수 있는지 묻는 문제이다.
처음엔 간단하게 생각하고 문자열을 첫 자리부터 읽어 짝지은 문자가 나오면 그 부분을 제외하고 앞뒤 문자열을 다시 이어 붙이는 식으로 연결해서, 남는 문자열이 있는지 확인하는 방식으로 했다.
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
// 첫번째 풀이 (실패)
import java.util.*;
class Solution
{
public int solution(String s)
{
String str = s;
int idx = 0;
while(str.length()>0 && idx+1<str.length()){
if(str.charAt(idx) == str.charAt(idx+1)){
if(idx == 0){
str = str.substring(2, str.length());
}else{
str = str.substring(0, idx) + str.substring(idx+2, str.length());
idx -= 1;
}
}else{
idx++;
}
}
}
}
그런데 이렇게 풀면 유효성 검사에서 모두 시간초과가 난다.
시간복잡도가 그렇게 크진 않다고 생각했는데, charAt과 subString, length 등 String의 메서드의 잦은 호출이 문제가 된다고 생각된다.
어떻게 바꿔야 하나 고민했는데, 생각해보면 이 문제는 고민할 필요가 없는 전형적인 stack 사용 문제였다.
짝 비교를 무조건 직전에 지나온 문자열과 비교하기 때문에, 문자열의 처음부터 시작해서 스택이 비어있거나 짝이 맞지 않으면 스택에 저장하고 가장 최상단의 문자와 짝 비교를 하면 된다.
이렇게 풀면 딱 문자열 길이만큼 탐색하기에 시간복잡도도 미세하게 더 줄어드는거 같기도?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 두번째 풀이 (성공)
import java.util.*;
class Solution
{
public int solution(String s)
{
Stack<Character> stack = new Stack<Character>();
int size = s.length();
for(int i=0; i<size; i++){
if(stack.isEmpty() || stack.peek()!=s.charAt(i)) stack.push(s.charAt(i));
else stack.pop();
}
if(stack.isEmpty()) return 1;
else return 0;
}
}