import java.util.Stack;
class Solution {
public int solution(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!stack.isEmpty() && stack.peek() == c) {
stack.pop();
} else {
stack.push(c);
}
}
return stack.isEmpty() ? 1 : 0;
}
}
이 문제를 처음 풀 땐, 깊게 생각안하고 String.subString()
을 사용하려 했다. 현재인덱스와 다음인덱스가 같을 땐 그 두 개만 제외하고 앞 뒤로 잘라서 붙이려고 했다. 이러니까 시간도 오래걸리고, 효율성면에서 아예 통과하지 못했다. 그러다 문득 생각난 것이 Stack
을 이용해서 푸는 것이다. 스택이 비어있거나, 비어있진 않은데 바라보고 있는 인덱스의 값과 다르다면 넣는 것이다. 같거나 비어있으면 pop하고. 이렇게하면 O(N)만 돌면 된다. 옛날에 풀었던 풀이들을 꼼꼼하게 생각해보는 버릇을 길러야겠다.
[출처] : 프로그래머스 코딩테스트 짝지어 제거하기
[출처] : 개인저장소