[백준]24511.queuestack

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

원래 나의 풀이 (이중 for)

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 자료구조 개수 N개
        int N = Integer.parseInt(br.readLine());
        String str = br.readLine();
        StringTokenizer stringTokenizer = new StringTokenizer(str, " ");
        int[] structure = new int[N];
        long[] value = new long[N];
        for (int i = 0; i < N; i++) {
            structure[i] = Integer.parseInt(stringTokenizer.nextToken());
        }
        // System.out.println(Arrays.toString(structure));
        str = br.readLine();
        stringTokenizer = new StringTokenizer(str, " ");
        for (int i = 0; i < N; i++) {
            value[i] = Long.parseLong(stringTokenizer.nextToken());
        }
        // System.out.println(Arrays.toString(value));

        int M = Integer.parseInt(br.readLine());
        long[] c = new long[M];
        str = br.readLine();
        stringTokenizer = new StringTokenizer(str, " ");
        for (int i = 0; i < M; i++) {
            c[i] = Long.parseLong(stringTokenizer.nextToken());
        }

        String ans = "";
        // 수열의 길이 M번만큼 반복을 해야 합니다.
        for (int i = 0; i < M; i++) {
            // 여행을 다닐 변수를 선언합니다. 수열 c의 값들이 여행을 시작하는 상황.
            long traveler = c[i];

            // 여행을 시작합니다.
            for (int j = 0; j < value.length; j++) {
                // 자료구조가 0이면 스위칭 , 1이면 그대로
                if (structure[j] == 0) {
                    long tmp = traveler;
                    traveler = value[j];
                    value[j] = tmp;
                }
            }
            // 여행이 끝난 traveler 은 , ans 에 추가합니다.
            ans += traveler + " ";
        }
        System.out.println(ans);
    }
}

---

손 풀이

스택은 무시하고 큐만 따진다는 것까지는 인지를 했지만 이중포문을 사용하면 시간초과가 날 것이라는 사실을 생각못했다.
이 문제에서는 시간초과를 해결하는 것이 관건인데 키 포인트가 두 개였다.

1. 스택은 아예 무시하라. 큐를 한 줄 세워라

스택을 싹 다 무시하고 큐들만 모아서 한 줄 세워버리기를 하면 , 이 또한 길어진 큐 하나로 퉁칠 수 가 있다.
왜냐하면 원래는 하나의 원소만 갖고있던 큐와 traveler를 스위칭하고 다음 큐에서도 또 스위칭을 하는 과정이 이루어지는데
결국 이것은 왼쪽으로 들어온 traveler가 맨 오른쪽에 있던 원소를 밖으로 밀어내는 것과 동치이기 때문이다.

2. String 쓰지말고 StringBuilder써라

분명 큐를 한 줄 세우기 해서 이중 for문을 없앴음에도 불구하고 시간초과가 1퍼센트에서 벗어나지 못했다.
서칭을 해본결과 나의 풀이와 다른 사람들의 풀이는 StringBuilder의 유무였는데 , C++이나 파이썬에서도 문제가 똑같이 발생할지는 모르겠으나 , 자바에서는 String이 불변 객체이기 때문에 문자열 결합이 발생할 때마다 새로운 문자열 객체가 생성된다고 한다. StringBuilder는 가변 객체이기 때문에 ans.append(traveler + " "); 와 같은 방법으로 시간복잡도를 줄일 수 있다는 것을 처음 알았다.

정답

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

public class App {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 자료구조 개수 N개
        int N = Integer.parseInt(br.readLine());
        String str = br.readLine();
        StringTokenizer stringTokenizer = new StringTokenizer(str, " ");

        // 자료구조 수열
        int[] structure = new int[N];
        // 값을 넣어놓을 배열
        int[] value = new int[N];

        // 큐가 어느 인덱스에 있는지 확인하기 위한 idxArr
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            structure[i] = Integer.parseInt(stringTokenizer.nextToken());
        }
        // System.out.println(Arrays.toString(structure));
        str = br.readLine();
        stringTokenizer = new StringTokenizer(str, " ");
        for (int i = 0; i < N; i++) {
            value[i] = Integer.parseInt(stringTokenizer.nextToken());
            if (structure[i] == 0)
                q.addLast(value[i]);
        }
        // System.out.println(Arrays.toString(value));

        int M = Integer.parseInt(br.readLine());
        str = br.readLine();
        stringTokenizer = new StringTokenizer(str, " ");

        StringBuilder ans = new StringBuilder();
        // 수열의 길이 M번만큼 반복을 해야 합니다.
        // 시간초과 -> 큐만 따로 생각해야 함
        for (int i = 0; i < M; i++) {
            // 여행을 다닐 변수를 선언합니다. 수열 c의 값들이 여행을 시작하는 상황.
            int traveler = Integer.parseInt(stringTokenizer.nextToken());

            // 여행을 시작합니다.
            q.addFirst(traveler);
            traveler = q.pollLast();

            // 여행이 끝난 traveler 은 , ans 에 추가합니다.
            ans.append(traveler + " ");
        }
        System.out.println(ans);
    }
}