[백준/Java] #24511 queuestack - 시간초과 해결

 

 

문제

 

 

 

 

 

코드

 

시간 초과 때문에 여러 번 시도한 문제다ㅠㅠ

처음 작성했던 코드는 다음과 같다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();

int N = Integer.parseInt(br.readLine());
StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");

ArrayList<Collection> list = new ArrayList<>();

for (int i = 0; i < N; i++) {
    if (st1.nextToken().equals("0")) {
        Queue<String> q = new ArrayDeque<>();
        q.offer(st2.nextToken());
        list.add(q);
    } else {
        Stack<String> stack = new Stack<>();
        stack.push(st2.nextToken());
        list.add(stack);
    }
}

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

for (int i = 0; i < M; i++) {
    String pop = st1.nextToken();
    for (int j = 0; j < list.size(); j++) {
        Collection c = list.get(j);
        if (c instanceof Stack<?>) {
            Stack<String> stack = (Stack<String>) c;
            stack.push(pop);
            pop = stack.pop();
        } else {
            Queue<String> queue = (Queue<String>) c;
            queue.offer(pop);
            pop = queue.poll();
        }
    }
    sb.append(pop).append(" ");
}
System.out.println(sb);

 

큰 생각 없이 문제에서 주어진 그대로 냅다 코드를 작성했고 그 결과 당연히 시간초과 😂

말 그대로 스택과 큐를 만들고 거기에 주어진 수도 다 넣고 빼고..ㅎ

 

 

그리고 두 번째로 복잡함을 조금 더 줄여 작성한 코드

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();

int N = Integer.parseInt(br.readLine());

StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");

int[] arrCollection = new int[N];
String[] arr = new String[N];

for (int i = 0; i < N; i++) {
    arrCollection[i] = Integer.parseInt(st1.nextToken());
    arr[i] = st2.nextToken();
}

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

for (int i = 0; i < M; i++) {
    String pop = st1.nextToken();

    for (int j = 0; j < arrCollection.length; j++) {
        if (arrCollection[j] == 0) {
            String tmp = arr[j];
            arr[j] = pop;
            pop = tmp;
        }
    }
    sb.append(pop).append(" ");
}
System.out.println(sb);

 

스택과 큐를 판별할 수 있는 배열 arrCollection과 stackqueue에 담긴 원소를 가진 배열 arr를 만들었다.

queue인 경우엔 해당 인덱스의 arr 값과 입력받은 수를 바꾸고, stack인 경우 입력받은 수를 그대로 둔다. (String pop에 저장)

그리고 마지막으로 pop을 출력하는데, 이 역시 시간 초과였다.

 

 

많은 고민 후 최종적으로 성공한 코드..

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();

int N = Integer.parseInt(br.readLine()); //queuestack 개수

StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");

Deque<String> d = new ArrayDeque<>();

for (int i = 0; i < N; i++) {
    String stackOrQueue = st1.nextToken();
    String val = st2.nextToken();
    if (stackOrQueue.equals("0")) {
        d.offer(val); //queue인 경우에만 deque에 넣음
    }
}

int M = Integer.parseInt(br.readLine()); //queuestack에 삽입할 원소의 수
st1 = new StringTokenizer(br.readLine(), " ");

for (int i = 0; i < M; i++) {
    d.offerFirst(st1.nextToken());
    sb.append(d.pollLast()).append(" ");
}
System.out.println(sb);

 

 

주어진 예제 1을 기준으로 생각해 봤을 때(2, 4, 7을 차례로 삽입)

 

큐인 경우에만 덱에 값을 넣는다. 👉🏻 [1, 4]

삽입할 원소를 덱의 앞에 넣는다. 👉🏻 [2, 1, 4]

덱의 마지막 값을 뺀다. 👉🏻 [2, 1] / 4 출력

 

위의 과정을 차례로 반복하면

2 입력 👉🏻 [2, 1] / 4 출력

4 입력 👉🏻 [4, 2] / 1 출력

7 입력 👉🏻 [7, 4] / 2 출력

이렇게 된다.

 

queue, stack의 조건을 바꾸어 시뮬레이션 해봐도 해결이 가능하다.