[Java] 11단계. queuestack [24511번]

https://www.acmicpc.net/problem/24511

• 예제 입력1

4
0 1 1 0
1 2 3 4
3
2 4 7

• 예제 출력1

4 1 2

• 예제 입력2

5
1 1 1 1 1
1 2 3 4 5
3
1 3 5

• 예제 출력2

1 3 5

---

• 문제 접근
  
  • 입력
    
    • 첫째 줄 : queuestack의 자료 구조 개수 N (1 <= N <= 100,000)
    • 둘째 줄 : 길이 N의 수열 A, 0 = Queue, 1 = Stack
    • 셋째 줄 : 길이 N의 수열 B, Bi는 i번 자료구조에 들어가있는 원소 (1 <= Bi <= 1,000,000,000)
    • 넷째 줄 : 삽입할 수열의 길이 M (1 <= M <= 100,000)
    • 다섯째 줄 : 길이 M의 삽입할 원소 수열 C (1 <= Ci <= 1,000,000,000)
  • 출력
    
    • 수열 C의 원소를 차례대로 queuestack에 삽입했을 때 리턴 값을 한 줄에 출력
• 문제 해결
  • 문제를 해석하면 다음과 같음
    • 첫째 줄 : 총 4개의 자료구조
    • 둘째 줄 : Queue(0)  → Stack(1) → Stack(0) → Queue(1)의 순서로 queuestack의 자료구조가 있음
    • 셋째 줄 : 1 2 3 4가 각각의 자료구조에 들어감
      • 1번 Queue 원소 : 1
      • 2번 Stack 원소 : 2
      • 3번 Stack 원소 : 3
      • 4번 Queue 원소 : 4
    • 넷째 줄 : 총 3개의 원소를 삽입할 것임
    • 다섯째 줄 : 2, 4, 7 원소를 순서대로 추가했을 때 최종적으로 반환되는 값을 나열
      • 최초 구조 : Queue(1), Stack(2), Stack(3), Queue(4)
      • 원소 2 삽입 : add(2) → Queue(1, 2) → pop(1) & add(1) → Stack(2, 1) → pop(1) & add(1) →Stack(3, 1) → pop(1) & add(1) → Queue(4, 1) → pop(4) → StringBuilder 추가
      • 결과 : Queue(2), Stack(2), Stack(3), Queue(1)
      • 원소 4 삽입 : add(4) → Queue(2, 4) → pop(2) & add(2) →Stack(2, 2) → pop(2) & add(2) → Stack(3, 2) → pop(2) & add(2) → Queue(1, 2) → pop(1) → StringBuilder 추가
      • 결과 : Queue(4), Stack(2), Stack(3), Queue(2)
      • 원소 7 삽입 : add(7) → Queue(4, 7) → pop(4) & add(4) → Stack(2, 4) →pop(4) & add(4) → Stack(3, 4) → pop(4) & add(4) → Queue(2, 4) → pop(2) → StringBuilder 추가
      • 결과 : Queue(7), Stack(2), Stack(3), Queue(4)
  • 문제 자체를 이해하는데 시간이 너무 오래 소요 되었음
  • 하지만, 위의 것을 그대로 적용하게 되면 삽입할 원소 길이 M번 만큼 반복 내부에 자료 구조 개수 N번 만큼 반복의 2중 for문이 나오게 되는데, N과 M은 최대 100,000이기 때문에 100000^2 = 100억으로 시간 초과가 나오게 됨
  • Stack은 push & pop을 하면 결국 들어간 데이터와 나온 데이터가 동일하기 때문에 Stack을 무시해도 됨
  • 첫번째 Queue(1)과 마지막 Queue(4)만 놓고 규칙을 탐색하면 다음의 규칙을 발견
    • 새로운 원소 삽입 → 첫번째 Queue의 front가 이 네 번째 원소에 추가되고, 네 번째 원소의 front가 출력
    • 위의 것을 Deque로 구현하면 3번째 줄 수열 B를 Queue인 경우에만 처리(Deque에 추가)
    • 5번째 줄에서 원소를 추가할 때 Deque.addFirst()를 하고, Deque.pollLast()를 하게 되면 원하는 결과가 출력

기존 풀이 [메모리 : 65,176 KB / 시간 : 588 ms]

public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    // 첫째 줄
    int N = Integer.parseInt(br.readLine());
    Deque<Integer> deque = new ArrayDeque<>();
    // 둘째 줄
    int[] A = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    // 셋째 줄
    int[] B = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    for(int i = 0; i < N; i++){
        if(A[i] == 0) deque.add(B[i]);
    }
    // 넷째 줄
    int M = Integer.parseInt(br.readLine());
    // 다섯째 줄
    int[] C = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    // 로직
    for(int i = 0; i < M; i++){
        int data = C[i];
        deque.addFirst(data);
        sb.append(deque.pollLast()).append(" ");
    }

    System.out.println(sb);
}