문제
이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다.
평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.
입력
첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)
다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.
출력
첫째 줄에 좋은 단어의 수를 출력한다.
예제 입력
3
ABAB
AABB
ABBA
예제 출력
2
내가 했던 풀이 방법
-
입력받은 단어를 문자 단위로 list에 넣어준 뒤, 무한 반복문 while을 이용하여 현재 index와 다음 index 값을 비교하여 같을 경우 list에서 해당 값들을 삭제해준 뒤, index를 0으로 이동시켜줌. index가 list의 마지막 index까지 갔거나, list의 size가 0이 될 경우 반복문 탈출. 반복문 탈출한 뒤, list의 size가 0일 경우 좋은 단어 -> 실패 (시간 초과) 50%까지는 맞았다는 것에서 알고리즘이 틀리지 않았다고 생각. 하나의 쌍을 제거해가면서, 결과적으로 모두 쌍을 이룬다는 것에서 stack으로 풀이 가능할 것이라 생각
-
for문을 이용해 입력받은 단어 처음부터 끝까지 문자 단위로 체크한다. -> 만약 stack이 비어있을 경우, stack에 넣어주고, prev를 현재 문자로 바꿔준다. -> stack이 비어있지 않고, prev와 현재 문자가 같을 경우 stack을 pop해주고, peek을 통해 마지막 요소를 prev에 넣어준다. (이때, stack이 비어있을 경우 생략) -> stack이 비어있지 않고, prev와 현재 문자가 다를 경우 stack에 넣어주고, prev를 현재 문자로 바꿔준다. -> 모든 문자를 다 처리했을 때 stack이 비어있다면 좋은 단어 -> 성공
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cases = Integer.parseInt(br.readLine());
int good = 0;
String word;
char prev;
for(int i=0; i<cases; i++) {
prev = ' ';
word = br.readLine();
Stack<Character> stack = new Stack<>();
for(int j=0; j<word.length(); j++) {
if(stack.isEmpty()) {
stack.push(word.charAt(j));
prev = word.charAt(j);
} else {
if(prev==word.charAt(j)) {
stack.pop();
if(!stack.isEmpty()) {
prev = stack.peek();
}
} else {
stack.push(word.charAt(j));
prev = word.charAt(j);
}
}
}
if(stack.isEmpty()) {
good++;
}
}
System.out.print(good);
}
}
회고
1번으로 풀이한 것도 시간 초과가 났긴 했지만, 나름 코드를 잘 짯다고 생각했다. 시간 초가 짧기에 분명 이렇게 풀이하는 게 시간 초과가 날 것이라 생각하긴 했지만.. 그래도 풀이가 맞다는 걸 확인해보고 싶어서 쭉 풀었더니 그래도 50%까지는 정답이었다는 것에 만족했다. 다행히 풀이 방법으로 괄호넣기 문제를 생각해내서 stack으로 빠르게 방향을 바꿀 수 있었다.
