[2022 하계 모각코] 5주차 1회 계획 및 결과

5주차 1회 계획 : 컬렉션 프레임워크(collection framework(Queue)) 공부

---

이번 주차 계획

• Queue 개념 정리
• Queue 를 활용한 문제 풀이

---

• Queue

Queue는  Stack과는  달리  선입선출(혹은 후입후출)  자료구조이다.  스택은  먼저  넣은  것은  가장  바닥에  깔리게  되어  맨  마지막에  꺼낼  수  있다.  어떻게  생각해보면  물병같은  것이다.  입구와  출구가  같아서  가장  바닥에  있는  것을  꺼내려면  가장  위에  있는  것부터  꺼내야  한다.  반면에  Queue는  입구의  반대편에  출구가  있다.  그래서  가장  처음에  넣은  것은  가장  처음으로  꺼내볼  수  있다(FIFO, First In First Out).

큐와 스택의 차이는 분명하기에 헷갈리지 않도록 하자.

자바에서 Queue를 쓰는 방법은 Collection FrameWork에서 불러다 쓰는 방법이다.

---

오늘 큐 공부는 여기를 보며 했다.

 

백준에서 큐라는 문제를 풀었다.사진에서 위는 컬렉션 프레임웤 Queue를 가지고 푼 것이고, 아래는 직접 Queue를 구현해서 풀었다.

아래 더보기를 누르면 위 문제의 소스코드를 확인 할 수 있다.

위는 Queue를 가지고서, 아래는 직접 구현한 Queue로 풀이한 코드이다.

Collection FrameWork 이용.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
    static int sToi(String s){return Integer.parseInt(s);}

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Queue<Integer> que = new LinkedList<>();

        int ConductCnt = sToi(br.readLine());
        String command;
        int X = -1;
        for (int i=0; i<ConductCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            command = st.nextToken();
            if (st.hasMoreTokens()) {
                X = sToi(st.nextToken());
            }
            int tmp = -1;
            switch (command) {
                case "push":
                    que.add(X);
                    break;
                case "pop":
                    tmp = (que.isEmpty()) ? -1 : que.poll();
                    bw.write(tmp + "\n");
                    break;
                case "size":
                    bw.write(que.size() + "\n");
                    break;
                case "empty":
                    bw.write(((que.isEmpty()) ? 1 : 0)+"\n");
                    break;
                case "front":
                    tmp = (que.isEmpty()) ? -1 : que.peek();
                    bw.write(tmp+"\n");
                    break;
                case "back":
                    X = (que.isEmpty()) ? -1 : X;
                    bw.write(X+"\n");
                default:
                    break;
            }
        }
        bw.flush();
        bw.close();
    }
}

구현.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

class SimulQueue{
    ArrayList<Integer> simulQueue = new ArrayList<>();

    private boolean IsEmpty(){
        return (simulQueue.size()==0) ? true : false;
    }

    public void PUSH(int x){
        simulQueue.add(x);
        return;
    }

    public Integer POP(){
        if (simulQueue.isEmpty()){
            return -1;
        }
        return simulQueue.remove(0);
    }

    public Integer SIZE(){
        return simulQueue.size();
    }

    public Integer EMPTY(){
        return (simulQueue.isEmpty()) ? 1 : 0;
    }

    public Integer FRONT(){
        return (simulQueue.isEmpty()) ? -1 : simulQueue.get(0);
    }
    public Integer BACK(){
        return (simulQueue.isEmpty()) ? -1 : simulQueue.get(simulQueue.size()-1);
    }

}


public class Main{
    static int sToi(String s){return Integer.parseInt(s);}

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        SimulQueue sq = new SimulQueue();

        int ConductCnt = sToi(br.readLine());
        String command;
        int num=0;
        for (int i=0; i<ConductCnt; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            command = st.nextToken();
            if (st.hasMoreTokens()){
                num = sToi(st.nextToken());
            }

            switch (command){
                case "push":
                    sq.PUSH(num);
                    break;
                case "pop":
                    bw.write(sq.POP()+"\n");
                    break;
                case "size":
                    bw.write(sq.SIZE()+"\n");
                    break;
                case "empty":
                    bw.write(sq.EMPTY()+"\n");
                    break;
                case "front":
                    bw.write(sq.FRONT()+"\n");
                    break;
                case "back":
                    bw.write(sq.BACK()+"\n");
                default:
                    break;
            }
        }
        bw.flush();
        bw.close();
    }
}

위: 구현, 아래: 라이브러리 이용

하지만 직접 구현한 것보단 많은 사람들이 이용하는 라이브러리를 이용하는 것이 더 빠름이 이 문제를 통해 증명됐다.

---

큐를 응용해 푸는 문제.

요세푸스 문제는 큐를 응용해 푸는 문제라고 해서 풀어보았다. 하지만 이 문제는 큐의 어떤 특성을 이용하는 것인지 잘 파악하지 못했다. 그래서 그나마 생각난 아이디어인 완전탐색으로 풀이 했다. 다른 사람의 채점 결과를 보니 큐나 Deque를 이용한 사람은 보통 200~400 ms 가 나오는 듯 했다. 좀 더 느린 경우도 있었으니 이 경우는 최적화가 잘 된 케이스인 것 같다. 공부해서 나도 수행시간을 줄인 코드를 짜보고 싶었다.

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main{

    public static void main(String[] args) throws Exception {
        StringJoiner sj = new StringJoiner(", ","<",">");
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();
        int idx = 0;

        boolean[] check = new boolean[n];
        int rotate = 0;
        int cnt = 0;
        for (;;) {
            if (!check[idx]){cnt += 1;}

            if (cnt == k){
                check[idx] = true;
                cnt = 0;
                rotate += 1;
                sj.add((idx+1)+"");
            }else if(cnt < k){
                idx += 1;
                if (idx >= n){idx %= n;}
            }

            if (rotate == n){break;}
        }
        bw.write(sj.toString());
        bw.flush();
        bw.close();
    }
}