[SWEA] 1234 비밀번호

: 문자열에서 서로 같은 번호로 붙어있는 쌍들을 소거하고 남은 번호를 비밀번호로 만들게 된다. 처음에는 재귀로 풀까하다가 스택이 생각났다. 문자열을 차례대로 스택에 넣다가 만약 스택의 마지막에 있는 문자와 현재 넣을 문자가 서로 같으면 스택의 마지막 문자를 빼주는 것이다.

: 주의할 점은 문자를 스택에 처음 넣어줄 때는 스택이 비어있기 때문에 그 값을 비교할 수 없다. 따라서 첫 요소는 반복문을 돌기 전에 넣어주는 것이 좋다. 

: 중간에 스택에 있는 요소가 다 빠지는 경우도 생각해봐야한다. 

예를 들어 122134의 문자열이라면 1221까지 넣으면 해당 문자들이 스택에서 모두 빠져서 빈 스택 상태가 된다. 그러면

새로 들어오는 문자와 비교할 수 없어 에러가 날 수 있다. 따라서 값을 비교하기 전에 스택이 비어있지 않다는 것을 보장해줘야한다.

 

1. N에 암호문의 길이를 입력받는다.

2. 암호는 char형 배열로 저장시킨다.

3. 암호를 한 문자씩 넣을 배열(tmp)을 만든다.

4. 암호문에서 첫 문자는 미리 배열에 넣어두어야 다음 문자부터 스택의 마지막 요소와 비교할 수 있다.

5. 스택(pw)의 마지막 문자와 넣을 문자가 같으면 스택에서 마지막 문자를 빼주는 과정을 반복한다.

6. 암호를 저장해두었던 배열(tmp)을 모두 순회하면 5번 과정을 끝낸다.

7. 스택에 남았는 문자들이 최종 암호문이 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Solution {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
         
        for(int tc = 1; tc <= 10; tc++) {
            st = new StringTokenizer(br.readLine());
            // 암호문 길이
            int N = Integer.parseInt(st.nextToken());
             
            // 암호문
            char[] tmp = st.nextToken().toCharArray();
             
            // 암호문을 스택으로 관리
            Stack<Character> pw = new Stack<>();
             
            // 처음 원소를 넣어줌 -> stack이 null이면 값을 비교할 수 없으므로
            pw.push(tmp[0]);
            // 첫번째 원소를 이미 넣어줬기 때문에 인덱스는 1부터 시작
            int idx = 1;
            while(idx < tmp.length) {
                // idx가 배열 끝에 도달할때까지 만약 들어가려는 요소와 스택의 마지막 요소가 같으면 스택 요소를 하나 뺌
                if(!pw.isEmpty() && pw.peek().equals(tmp[idx])) {
                    pw.pop();                   
                }
                // 같지 않다면 스택에 넣어줌
                else {
                    pw.push(tmp[idx]);
                }
                idx++;
            }
            sb.append("#" + tc + " " + pw.toString().replace(", ","").replace("[", "").replace("]","") + "\n");
        }
        System.out.println(sb);
    }
}