백준 [2065] 나룻배

단순 큐 문제여서 쉽게 생각했다가 한번 꼬이니 쭉 꼬여서 당황한 문제

 

처음엔 왼쪽과 오른쪽 큐를 만들어 독립적으로 관리했는데 이렇게 되다보니

현재 방향이 왼쪽이냐 오른쪽이냐 구분하는 코드로 너무 길어져서

큐 배열 2개로 만들어서 0, 1로 관리했다.

 

전체 코드 (스압 주의)

 

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

class TimeTable {
    int order;      // 입력된 순서
    int arriveTime; // 도착한 시간

    public TimeTable(int order, int arriveTime) {
        this.order = order;
        this.arriveTime = arriveTime;
    }

    public int getOrder() {
        return order;
    }

    public int getArriveTime() {
        return arriveTime;
    }
}

class Main {
    static int M, t, N;
    static int currentTime = 0;
    static int currentPosition = 0;     // 0 : left, 1 : right
    static Queue<TimeTable>[] timeQ = new LinkedList[2];
    static Queue<TimeTable> ship = new LinkedList<>();
    static int[] answer;

    public static void main(String[] args) throws Exception {
        input();
        solve();
        print();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        answer = new int[N + 1];

        for (int i = 0; i < 2; i++)
            timeQ[i] = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int arriveTime = Integer.parseInt(st.nextToken());
            String position = st.nextToken();
            // 배가 처음 움직이는 시간은 첫 입력에서 받는 도착 시간
            if(i == 0)
                currentTime = arriveTime;
            // 왼쪽, 오른쪽 타임테이블 큐 만듬
            if (position.equals("left"))
                timeQ[0].add(new TimeTable(i, arriveTime));
            else
                timeQ[1].add(new TimeTable(i, arriveTime));
        }
    }

    private static void solve() {
        while (!(timeQ[0].isEmpty() && timeQ[1].isEmpty())) {
            if (!tryLoad()) {
                waitPassenger();
                tryLoad();
            }
            moveShip();
        }
    }

    // 현재 방향에서 도착한 승객 싣음
    private static boolean tryLoad() {
        if(timeQ[currentPosition].isEmpty())
            return false;

        while (!timeQ[currentPosition].isEmpty()) {
            TimeTable timeTable = timeQ[currentPosition].peek();
            // 아직 도착하지 않았으면 태우지 않음
            if (timeTable.getArriveTime() > currentTime)
                break;
            ship.add(timeTable);
            timeQ[currentPosition].remove();
            // 최대 인원 수용시 승객 그만 싣음
            if(ship.size() == M)
                return true;
        }
        return !ship.isEmpty();
    }

    // 배를 반대쪽으로 움직임
    private static void moveShip() {
        currentTime += t;
        while (!ship.isEmpty()) {
            TimeTable timeTable = ship.poll();
            answer[timeTable.getOrder()] = currentTime;
        }
        currentPosition ^= 1;
    }

    private static void waitPassenger() {
        // 왼쪽 방향엔 더이상 승객이 없을 때
        if (timeQ[0].isEmpty()) {
            currentTime = refreshTime(timeQ[1].peek().getArriveTime());
            return;
        }
        // 오른쪽 방향엔 더이상 승객이 없을 때
        else if (timeQ[1].isEmpty()) {
            currentTime = refreshTime(timeQ[0].peek().getArriveTime());
            return;
        }
        // 양방향에서 웨이팅이 있을 경우 가장 빠른 쪽으로 감
        TimeTable current = timeQ[currentPosition].peek();
        TimeTable opposite = timeQ[currentPosition ^ 1].peek();
        if (current.getArriveTime() <= opposite.arriveTime)
            currentTime = refreshTime(current.getArriveTime());
        else
            currentTime = refreshTime(opposite.getArriveTime());
    }

    // 만약 웨이팅 시간이 현재 시간보다 길다면 웨이팅 시간으로 갱신
    private static int refreshTime(int arriveTime) {
        if(currentTime > arriveTime)
            return currentTime;
        return arriveTime;
    }

    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < N; i++)
            bw.write(answer[i] + "\n");
        bw.flush();
    }
}

 

1. 객체 정의

먼저, 입력에 대한 객체를 만들어서 그 객체를 원소로 하는 큐를 만들었다.

class TimeTable {
    int order;      // 입력된 순서
    int arriveTime; // 도착한 시간

    public TimeTable(int order, int arriveTime) {
        this.order = order;
        this.arriveTime = arriveTime;
    }

    public int getOrder() {
        return order;
    }

    public int getArriveTime() {
        return arriveTime;
    }
}

 

여기서 order 멤버변수가 있는데,

이걸 추가한 이유는 도착한 승객이 M명을 넘는 상황에서는

해당 객체가 몇번째 승객인지 헷갈리기 때문에 추가했다.

 

2. 변수 정의와 입력 

딱히 특별한건 없다.

자바를 모르는 사람들을 위해

br.readLine은 해당 줄에 대한 문자열을 읽는다는 것이고

st.nextToken은 해당 줄의 문자열에 공백들이 있는 경우, 공백을 기준으로 파싱해 넣어주는 식이다.

 

currentPosition이 0이면 왼쪽, 1이면 오른쪽이다.

    static int M, t, N;
    static int currentTime = 0;			// 현재 시간
    static int currentPosition = 0;     // 0 : left, 1 : right
    static Queue<TimeTable>[] timeQ = new LinkedList[2];
    static Queue<TimeTable> ship = new LinkedList<>();
    static int[] answer;
    
    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        answer = new int[N + 1];

        for (int i = 0; i < 2; i++)
            timeQ[i] = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int arriveTime = Integer.parseInt(st.nextToken());
            String position = st.nextToken();
            // 배가 처음 움직이는 시간은 첫 입력에서 받는 도착 시간
            if(i == 0)
                currentTime = arriveTime;
            // 왼쪽, 오른쪽 타임테이블 큐 만듬
            if (position.equals("left"))
                timeQ[0].add(new TimeTable(i, arriveTime));
            else
                timeQ[1].add(new TimeTable(i, arriveTime));
        }
    }

 

3. TimeTable 큐 비우기

왼쪽 TimeTable과 오른쪽 TimeTable이 모두 빌 때 까지 돌린다.

    private static void solve() {
        while (!(timeQ[0].isEmpty() && timeQ[1].isEmpty())) {
            if (!tryLoad()) {
                waitPassenger();
                tryLoad();
            }
            moveShip();
        }
    }

밑에 설명하겠지만 간단히 설명하면 다음과 같다.

1. 승객을 태울 수 있는지 확인

2. 못태우면 올 때 까지 기다림

3. 왔으면 태운다.

4. 배를 움직인다.

 

4. tryLoad

 

현재 방향에서 온 손님들을 M명까지 태운다.

    // 현재 방향에서 도착한 승객 싣음
    private static boolean tryLoad() {
        if(timeQ[currentPosition].isEmpty())
            return false;

        while (!timeQ[currentPosition].isEmpty()) {
            TimeTable timeTable = timeQ[currentPosition].peek();
            // 아직 도착하지 않았으면 태우지 않음
            if (timeTable.getArriveTime() > currentTime)
                break;
            ship.add(timeTable);
            timeQ[currentPosition].remove();
            // 최대 인원 수용시 승객 그만 싣음
            if(ship.size() == M)
                return true;
        }
        return !ship.isEmpty();
    }

승객을 태울 수 있다면 true, 승객이 0명이라면 false를 반환한다.

이 외에도 해당 방향에 승객이 모두 온 상태라면(큐가 비어있음) false 반환

 

 

5. waitPassenger

 

먼저, 해당 방향에 승객이 없다면 반대쪽 방향을 본다.

양방향에 승객 도착 정보가 있다면 가장 빨리 오는 시간에 맞춤

 

    private static void waitPassenger() {
        // 왼쪽 방향엔 더이상 승객이 없을 때
        if (timeQ[0].isEmpty()) {
            currentTime = refreshTime(timeQ[1].peek().getArriveTime());
            return;
        }
        // 오른쪽 방향엔 더이상 승객이 없을 때
        else if (timeQ[1].isEmpty()) {
            currentTime = refreshTime(timeQ[0].peek().getArriveTime());
            return;
        }
        // 양방향에서 웨이팅이 있을 경우 가장 빠른 쪽으로 감
        TimeTable current = timeQ[currentPosition].peek();
        TimeTable opposite = timeQ[currentPosition ^ 1].peek();
        if (current.getArriveTime() <= opposite.arriveTime)
            currentTime = refreshTime(current.getArriveTime());
        else
            currentTime = refreshTime(opposite.getArriveTime());
    }

 

코드를 보면 refreshTime이란 메소드가 있는데

별건 아니고 currentTime이 도착 시간보다 작다면 currentTime을 갱신해준다.

currentTime < getArriveTime()

 

 

6. moveShip

배를 움직이게 하는 메소드.

이 메소드가 실행되면 currentTime을 t만큼 늘린다.

여기서 poll은 큐의 상단을 pop하면서 그 값을 반환한다.

즉, peek과 remove를 같이 수행

    // 배를 반대쪽으로 움직임
    private static void moveShip() {
        currentTime += t;
        while (!ship.isEmpty()) {
            TimeTable timeTable = ship.poll();
            answer[timeTable.getOrder()] = currentTime;
        }
        currentPosition ^= 1;
    }