백준 24511 queuestack[JAVA]

문제 해석

• 문제를 이해하는데 진짜 오랜 시간이 걸렸다...
• 내가 생각하기에 하나의 원소를 가지는 자료구조라는 것이 중요한 포인트 같다.
• 처음엔 배열이 보이니까 한 배열이 자료구조 하나인 게 더 익숙하다보니 그런 식으로 해석하려하니 꽤 헤맸다.
• 암튼, 문제 해석하자면 아래의 같다.
• 첫째 줄에 자료구조의 개수 N개를 입력받는다.
• 두번째 줄에는 N개 만큼 각각 하나의 원소를 가지는 자료구조 형태를 입력받는다.
  • 0 : queue (큐; FIFO)
  • 1 : stack (스택; LIFO)
• 세번째 줄에는 각각 자리에 해당하는 하나의 원소(수)를 가지는 자료구조들이 가지고 있는 원소들을 입력받는다. (예를 들어 1 2 3 4 -> 첫번째 자료구조가 가지는 원소는 1이 되는 것이다.)
• 네번째 줄에는 각각 자리에 해당하는 자료구조들에게 각각 들어갈 원소의 개수이고, 다섯번째줄부터는 첫번째 자료구조에 들어가는 원소들을 입력받는다.
• 그 후로는 첫번째 자료구조에서 POP된 원소를 다음 자료구조에 넣어준다. (이 과정을 N번만큼 반복)
• 간단하게 설명하자면 아래와 같다.
  
• 단!!! 마지막 Xn의 리턴 값을 출력한다.

코드

1

import java.io.*;
import java.util.LinkedList;
import java.util.StringTokenizer;


public class Main {

    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()); // 자료구조 개수

        LinkedList<Structure> queueStack = new LinkedList<>(); // 자료구조 배열

        StringTokenizer st = new StringTokenizer(br.readLine());

        //각각 자료구조의 개수만큼 어떠한 자료구조를 가지는지 입력받기(큐 or 스택)
        for(int i = 0; i < N; i++){
            // 일단 자료구조형태값만 받는다. (값은 일단 0으로 설정 값은 1이상이므로 0을 가질 수 X)
            queueStack.addLast(new Structure(Integer.parseInt(st.nextToken()), 0));
        }

        st = new StringTokenizer(br.readLine());
        //각각의 자료구조가 가지는 값 입력받기(하나의 원소밖에 가지지 못함)
        for(int i = 0; i < N; i++){
            queueStack.get(i).setValue(Integer.parseInt(st.nextToken()));
        }

        int M = Integer.parseInt(br.readLine()); // 삽입할 수열의 길이

        st = new StringTokenizer(br.readLine());
        br.close();
        // 수열을 삽입한다.
        while(M --> 0){
            int moveValue = Integer.parseInt(st.nextToken());

            for(int i = 0; i< N; i++){
                if(queueStack.get(i).getType() == 0){ // 자료구조가 큐이면
                    int tmpValue = queueStack.get(i).getValue();
                    queueStack.get(i).setValue(moveValue);
                    moveValue = tmpValue;
                }
                //스택의 경우는 바뀌지 않으니 따로 안해줘도 된다.
            }
            sb.append(moveValue).append(" ");
        }

        System.out.println(sb);
    }
}

class Structure{
    int type; // 큐인지 스택인지
    int value; //가지고 있는 하나의 원소

    public Structure(int type, int value) {
        this.type = type;
        this.value = value;
    }

    public void setType(int type) {
        this.type = type;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public int getType() {
        return type;
    }

    public int getValue() {
        return value;
    }
}
        

• 시간초과가 나왔다 while -> for문으로 O(N^2)의 시간복잡도를 가지는데 이로 인해 시간초과가 나오는 것 같다. 입력 값이 100 000, 1 000 000 000 이기 때문에... 시간초과가 나올 것인게 확실했는데 생각을 못했다...

2

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;


public class Main {

    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()); // 자료구조 개수

        int[] typeArr = new int[N]; // 자료구조 배열

        StringTokenizer st = new StringTokenizer(br.readLine());

        //각각 자료구조의 개수만큼 어떠한 자료구조를 가지는지 입력받기(큐 or 스택)
        for(int i = 0; i < N; i++){
            // 일단 자료구조형태값만 받는다.
            typeArr[i] = Integer.parseInt(st.nextToken());
        }

        Deque<Integer> deque = new ArrayDeque<>();

        st = new StringTokenizer(br.readLine());
        //각각의 자료구조가 가지는 값 입력받기(하나의 원소밖에 가지지 못함)
        for(int i = 0; i < N; i++){
            //스택은 들어가자마자 나오기 때문에 자료형이 큐인 것만 저장한다.
            int num = Integer.parseInt(st.nextToken());
            if(typeArr[i] == 0){
                deque.addLast(num);
            }
        }

        int M = Integer.parseInt(br.readLine()); // 삽입할 수열의 길이

        st = new StringTokenizer(br.readLine());
        br.close();
        // 수열을 삽입한다.
        while(M --> 0){
            int moveValue = Integer.parseInt(st.nextToken());
            // 만약 큐만 없고 스택으로 이루어졌다고 해도 바로 빼기 때문에 (pollLast()) 문제가 되지 않는다.
            // => 첫번째에 넣고 마지막을 뺀다. (큐의 자료구조를 가진 큰 큐로 가정해서 풀면 되는 문제)
            deque.addFirst(moveValue);
            sb.append(deque.pollLast()).append(" ");
        }

        System.out.println(sb);
    }
}
        

• 큐인 것만 저장했다. (그랬더니 따로 큐인지 스택인지 비교해야하는 로직을 지울 수 있었고 그로 인해 이중반복문을 지울 수 있었다.)

결과

1

2

느낀 점

• 처음에는 문제 해석하는데 있어서 많이 헤맸지만 그래도 풀고나니 진짜 문제해석만큼 어려운 문제는 아니라는 생각이 들었다. (생각보다 쉬운 문제였다..ㅎㅎ)