백준 1874

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out););
        List<Integer> list = new ArrayList<>();
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }

        Deque<Integer> deq = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();
        
        int num = 1;
        int target = 0;
        while (num <= N) {
            deq.addLast(num++);
            sb.append("+\n");

            while (!deq.isEmpty() && deq.getLast().equals(list.get(target))) {
                deq.removeLast();
                sb.append("-\n");
                target++;
            }
        }
        if (!deq.isEmpty()) {
            bw.write("NO\n");
        } else {
            bw.write(sb.toString());
        }
        bw.flush();
        bw.close();
    }
}

풀이과정 및 리뷰

실패

1. 1 ~ N 까지의 숫자를 담을 덱 선언(구현쳬: ArrayDeque)
2. 입력받는 값을 컬렉션으로 담지않고 int n 으로 계속 값을 변경해가며 덱의 마지막 값(스택의 젤 윗값)과 비교하려고 했으나 실패

성공

1. 먼저 입력값들을 모두 List에 담아둠
2. num이 List.get(target) 의 값과 동일해질 때까지 deque에 담음
3. 만약 2번 조건이 일치한 경우, deque의 제일 위의 값과 List.get(target) 값이 동일한지 확인
4. 3의 조건을 만족한 경우, 만족하지 않을 때까지 deque에서 제일 윗값 제거 + list 인덱스++
5. StringBuilder에 + / - 조건을 매 경우 더해준 후 한번에 flush

리뷰

스택이나 덱 자료구조를 쓸 때, 자꾸 stack.isEmpty() 조건을 빼먹어서 오류를 한번씩 내는것 같은데 조심해야할 것 같다.

그리고, 처음 결과를 제출했을 때는 StringBuilder 를 사용하지 않고 BufferedWriter 만 사용했더니

출력초과 에러를봤다…첨봤다. 데이터 갯수가 최대 10만개이므로, 출력값이 많은 경우 BufferedWriter 와 StringBuilder 를 함께 사용하는 방법을 사용해야겠다.

• BufferedWriter vs StringBuilder