[알고리즘, 코드트리] 코드트리 오마카세 - java

  ※ 주의!! 이 풀이는 코드트리 해설을 강하게 참고하고 있습니다!!  

문제

문제가 상당히 길다. 전문을 보고 싶은 사람은 코드트리에서 확인하자.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

요약하자면 아래와 같다. 총 세 가지 동작을 수행해야 한다.

(1) 주방장의 초밥 만들기 : 주방장이 시각 t에 위치 x 앞에 있는 벨트 위에 name 이름을 부착한 회전 초밥을 하나 올려놓는다

(2) 손님 입장 : 이름이 name인 사람이 시각 t에 위치 x에 있는 의자로 가서 앉은 뒤 n개의 초밥을 먹을 때까지 기다리게 된다.

(3) 사진 촬영 : 시각 t에 코드트리 오마카세 집에 있는 사람 수와 남아 있는 초밥의 수를 공백을 사이에 두고 출력한다.

입력

• 주방장의 초밥 만들기
  • 100 t x name 형태로 공백을 사이에 두고 주어집니다. 이는 주방장이 시각 t에 위치 x 앞에 있는 벨트 위에 name 이름을 부착한 회전 초밥을 하나 올려 놓는다는 것을 의미합니다.
• 손님 입장
  • 오는 손님의 이름은 전부 다르며, 동일한 손님이 다시 방문하게 되는 경우는 없음을 가정해도 좋습니다.
  • 200 t x name n 형태로 공백을 사이에 두고 주어집니다. 이는 이름이 name인 사람이 시각 t에 위치 x에 있는 의자로 가서 앉은 뒤 n개의 초밥을 먹을 때까지 기다리게 됨을 의미합니다. n개의 초밥을 먹게 된 직후 자리를 떠나게 됩니다.
• 사진 촬영
  • 300 t 형태로 주어집니다. 이 경우 시각 t에 코드트리 오마카세 집에 있는 사람 수와 남아 있는 초밥의 수를 공백을 사이에 두고 출력합니다. 이 명령은 최소 1번 이상 주어진다고 가정해도 좋습니다.

출력

300 명령어에 대해 시각 t에 코드트리 오마카세 집에 있는 사람 수와 남아 있는 초밥의 수를 공백을 사이에 두고 한 줄에 하나씩 순서대로 출력합니다.

문제 풀이

관점의 전환이 필요한 문제이다. 이 문제에서는 초밥을 관리하기 위한 초밥 객체도 손님을 관리하기 위한 손님 객체도 필요 없다. 손님과 초밥을 직접 관리한다면 문제의 인풋 사이즈도 부담으로 다가와야 함을 느껴야 한다.

회전 초밥 벨트의 길이는 최대 10억, 시간은 10억 초, 명령 수는 10만이다.

따라서 초밥과 사람이 빠지고 들어가는 동작을 표현할 '쿼리'객체를 사용하여 문제를 풀 것이다. 

자료구조 정의 및 입출력

static int L, Q;
static class Query {
    public int cmd, t, x, n;
    public String name;

    public Query(int cmd, int t, int x, String name, int n) {
        this.cmd = cmd;
        this.t = t;
        this.x = x;
        this.name = name;
        this.n = n;
    }
}

// 명령 관리
public static List<Query> queries = new ArrayList<>();

// 사람 관리
public static Set<String> names = new HashSet<>();

// 각 사람마다 주어진 명령 관리
public static Map<String, List<Query>> p_queries = new HashMap<>();

// 각 사람마다 입장 시간 관리
public static Map<String, Integer> entry_time = new HashMap<>();

// 각 손님 위치 관리
public static Map<String, Integer> position = new HashMap<>();

// 퇴장 시간 관리
public static Map<String, Integer> exit_time = new HashMap<>();

L = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());

int command;
while(Q-- > 0) {
    int t = -1;
    int x = -1;
    int n = -1;
    String name = "";
    st = new StringTokenizer(br.readLine());

    command = Integer.parseInt(st.nextToken());

    switch(command) {
        case 100:
            t = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            name = st.nextToken();

            break;
        case 200:
            t = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            name = st.nextToken();
            n = Integer.parseInt(st.nextToken());

            break;
        case 300:
            t = Integer.parseInt(st.nextToken());

            break;
    }

    queries.add(new Query(command, t, x, name, n));

    // 사람별 주어진 쿼리 목록 관리
    if(command == 100) {
        p_queries.computeIfAbsent(name, k -> new ArrayList<>()).add(new Query(command, t, x, name, n));
    } 
    // 손님 입장 시간 및 위치 관리
    else if(command == 200) {
        names.add(name);
        entry_time.put(name, t);
        position.put(name, x);
    }
}

명령에 따라서 주어진 input 형태를 저장하고 Query 저장 리스트에 넣는다. 

명령이 '100(초밥이 벨트 위로 올라옴)'이라면 사람별로 주어진 쿼리 목록(p_queires)에 따로 저장해야 한다. 현재 코드에서는 Map에서 주어진 name에 해당되는 ArrayList가 존재하지 않는다면 새로운 ArrayList를 선언하고 거기에 Query를 저장하고 있다.

명령이 '200(사람이 입장함)'이라면 현재 입장해있음을 의미하기 위해 손님을 Set에 저장하고 손님의 입장시간과 위치를 각각 별도의 Map에 저장한다.

 

이렇게 모든 Query를 전부 한 번에 입력받는다.

초밥을 먹어보자

// 각 사람마다 자신의 이름이 적힌 조합을 언제 먹게 되는지 계산
// 해당 정보를 기존 Query에 추가
for(String name : names) {
    // 해당 사람 퇴장시간 관리
    exit_time.put(name, 0);

    for(Query q : p_queries.get(name)) {
        int time_to_remove = 0;
        
        // 만약 초밥이 사람이 등장하기 전에 미리 주어진 상황이면
        if(q.t < entry_time.get(name)) {
            // entry_time 때의 스시 위치를 계산
            int t_sushi_x = (q.x + (entry_time.get(name) - q.t)) % L;
            // 몇 초가 더 지나야 만나는지 계산
            int additional_time = (position.get(name) - t_sushi_x + L) % L;

            time_to_remove = entry_time.get(name) + additional_time;
        }
        // 초밥이 사람이 등장한 이후에 주어졌다면
        else {
            // 몇 초가 더 지나야 만나는지 계산
            int additional_time = (position.get(name) - q.x + L) % L;
            time_to_remove = q.t + additional_time;
        }

        // 초밥이 사라지는 시간 중 가장 늦은 시간을 업데이트
        exit_time.put(name, Math.max(exit_time.get(name), time_to_remove));

        // 초밥이 사라지는 111번 쿼리를 추가
        queries.add(new Query(111, time_to_remove, -1, name, -1));
    }
}

주어진 Query를 읽어 들이면서 각 사람마다 언제 초밥을 먹게 되는지를 계산할 것이다. 계산된 내용을 기존 Query에 추가하자.

 

입출력에서 벨트에 존재하게 될 name을 Set에 저장했었다. Set에서 name을 하나씩 꺼내어 계산에 활용할 것이다. 

 

이 name으로 사람별로 쿼리를 저장했던 map에서 쿼리 리스트를 꺼내온다. 쿼리리스트를 모두 순회하면서 초밥이 사라지는 시간을 계산하여 이를 "{time_to_remove} 초에 {name}이라는 사람이 초밥을 먹었다."라는 새로운 쿼리로 저장할 것이다.

 

time_to_remove 계산 과정

두 가지 상황이 존재한다. 초밥이 사람이 입장하기 전에 벨트에 존재하는 상황과 사람이 입장한 후에 초밥이 벨트 위에 올라오는 상황이다.

// 만약 초밥이 사람이 등장하기 전에 미리 주어진 상황이면
if(q.t < entry_time.get(name)) {
    // entry_time 때의 스시 위치를 계산
    int t_sushi_x = (q.x + (entry_time.get(name) - q.t)) % L;
    // 몇 초가 더 지나야 만나는지 계산
    int additional_time = (position.get(name) - t_sushi_x + L) % L;

    time_to_remove = entry_time.get(name) + additional_time;
}
// 초밥이 사람이 등장한 이후에 주어졌다면
else {
    // 몇 초가 더 지나야 만나는지 계산
    int additional_time = (position.get(name) - q.x + L) % L;
    time_to_remove = q.t + additional_time;
}

원리는 두 가지 상황 모두 비슷하다. 'name이라는 이름을 가진 사람이 존재하는 위치로 초밥이 언제 도착할 것인가'를 계산하면 된다.

 

따라서 초밥이 미리 주어진 상황에서는 사람이 입장했을 때의 위치를 계산하여 그 위치를 기준으로 계산할 것이고, 초밥이 나중에 주어진 상황에서는 초밥이 올라온 위치를 기준으로 계산할 것이다.

 

계산 과정에서 L(초밥 회전 벨트의 길이)을 더하고 모듈러 연산을 하는 것에 주의하자. '원형' 벨트라는 환경에서 자주 사용되는 계산 테크닉이다. 계산 값이 음수임을 방지하기 위해서 L을 더해주고 L로 모듈러 연산하면 원형을 고려할 수 있다.

exit_time 저장

time_to_remove를 계산하였다면 초밥이 사라지는 시간 중 가장 늦은 시간을 exit_time으로 저장할 것이다. 따라서 계산이 진행됨에 따라(현재까지 저장된 쿼리는 모두 시간(t)에 대한 오름차순으로 정렬되어 있음이 보장된다) exit_time이 계속해서 업데이트될 것이고 마지막으로 초밥을 먹은 시간이 해당 name이 매장을 떠난 시점이 된다. 

 

exit_time은 추후에 손님이 매장을 떠나는 시점이 된다(이 역시도 시간이 무한히 흘렀을 때 만들어진 모든 초밥은 손님에 의해 다 사라지며, 손님 역시 정확히 n개의 초밥을 먹고 코드트리 오마카세를 떠나게 됨이 보장된다).

초밥을 먹었음을 의미하는 query 저장

// 초밥이 사라지는 111번 쿼리를 추가
queries.add(new Query(111, time_to_removed, -1, name, -1));

초밥이 사라지는 것을 의미하기 위해 전체 query List에 111 command로 {name} 손님이 초밥을 먹어 초밥이 사라지는 쿼리를 추가한다.

다 먹은 손님은 퇴장하자

// 사람마다 초밥을 마지막으로 먹은 시간 t를 계산하여 그 사람이 해당 t 때 오마카세를 떠났음을 쿼리로 저장
for(String name : names) {
    queries.add(new Query(222, exit_time.get(name), -1, name, -1));
}

방금 모든 쿼리를 순회하면서 {name}이라는 손님이 언제 마지막 초밥을 먹는지를 저장하였다. 이를 활용하여 {name} 사람이 t 초에 퇴장하였음을 의미하는 쿼리를 query List에 222 command로 저장한다.

전체 쿼리를 시간(t) 순으로 정렬하자

// 전체 Query를 시간순으로 정렬하되 t가 일치한다면 문제 조건상 사진 촬영에 해당하는 300이 가장 늦게 실행
queries.sort((q1, q2)-> cmp(q1, q2) ? -1 : 1);

새로 추가된 111 command 쿼리와 222 command 쿼리를 query List에 정상적으로 반영하기 위해서 qurey List를 시간순으로 정렬할 것이다.

비교 함수 _ cmp()

public static boolean cmp(Query q1, Query q2) {
    if(q1.t != q2.t)
        return q1.t < q2.t;
    return q1.cmd < q2.cmd;
}

q1이 q2의 시간을 우선적으로 비교한다. 만약 두 시간이 같다면 q1과 q2의 command를 우선순위로 비교한다.

정렬된 query List를 순회하면서 손님 수와 초밥 수를 단순 계산하자

int people_num = 0;
int sushi_num = 0;
for(Query query: queries) {
    // System.out.println("query cmd : " + query.cmd + " | query t : " + query.t);
    if(query.cmd == 100)
        sushi_num++;
    else if(query.cmd == 111)
        sushi_num--;
    else if(query.cmd == 200)
        people_num++;
    else if(query.cmd == 222)
        people_num--;
    else
        sb.append(people_num).append(" ").append(sushi_num).append("\n");
}

시간순으로 정렬되어 있음이 보장되므로 전체 query List를 순회하면서 수행하는 단순 계산으로 초밥 수와 손님 수를 구할 수 있다.

전체 코드

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

public class Main {

    static int L, Q;
    static class Query {
        public int cmd, t, x, n;
        public String name;

        public Query(int cmd, int t, int x, String name, int n) {
            this.cmd = cmd;
            this.t = t;
            this.x = x;
            this.name = name;
            this.n = n;
        }
    }

    // 명령 관리
    public static List<Query> queries = new ArrayList<>();

    // 사람 관리
    public static Set<String> names = new HashSet<>();

    // 각 사람마다 주어진 명령 관리
    public static Map<String, List<Query>> p_queries = new HashMap<>();

    // 각 사람마다 입장 시간 관리
    public static Map<String, Integer> entry_time = new HashMap<>();

    // 각 손님 위치 관리
    public static Map<String, Integer> position = new HashMap<>();

    // 퇴장 시간 관리
    public static Map<String, Integer> exit_time = new HashMap<>();

    public static boolean cmp(Query q1, Query q2) {
        if(q1.t != q2.t)
            return q1.t < q2.t;
        return q1.cmd < q2.cmd;
    }

    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        L = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        int command;
        while(Q-- > 0) {
            int t = -1;
            int x = -1;
            int n = -1;
            String name = "";
            st = new StringTokenizer(br.readLine());

            command = Integer.parseInt(st.nextToken());

            switch(command) {
                case 100:
                    t = Integer.parseInt(st.nextToken());
                    x = Integer.parseInt(st.nextToken());
                    name = st.nextToken();

                    break;
                case 200:
                    t = Integer.parseInt(st.nextToken());
                    x = Integer.parseInt(st.nextToken());
                    name = st.nextToken();
                    n = Integer.parseInt(st.nextToken());

                    break;
                case 300:
                    t = Integer.parseInt(st.nextToken());

                    break;
            }

            queries.add(new Query(command, t, x, name, n));

            // 사람별 주어진 초밥 목록 관리
            if(command == 100) {
                p_queries.computeIfAbsent(name, k -> new ArrayList<>()).add(new Query(command, t, x, name, n));
            } 
            // 손님 입장 시간 및 위치 관리
            else if(command == 200) {
                names.add(name);
                entry_time.put(name, t);
                position.put(name, x);
            }
        }

        // 각 사람마다 자신의 이름이 적힌 조합을 언제 먹게 되는지 계산
        // 해당 정보를 기존 Query에 추가
        for(String name : names) {
            // 해당 사람 퇴장시간 관리
            exit_time.put(name, 0);

            for(Query q : p_queries.get(name)) {
                // 만약 초밥이 사람이 등장하기 전에 미리 주어진 상황이면
                int time_to_removed = 0;
                if(q.t < entry_time.get(name)) {
                    // entry_time 때의 스시 위치를 계산
                    int t_sushi_x = (q.x + (entry_time.get(name) - q.t)) % L;
                    // 몇 초가 더 지나야 만나는지 계산
                    int additional_time = (position.get(name) - t_sushi_x + L) % L;

                    time_to_removed = entry_time.get(name) + additional_time;
                }
                // 초밥이 사람이 등장한 이후에 주어졌다면
                else {
                    // 몇 초가 더 지나야 만나는지 계산
                    int additional_time = (position.get(name) - q.x + L) % L;
                    time_to_removed = q.t + additional_time;
                }

                // 초밥이 사라지는 시간 중 가장 늦은 시간을 업데이트
                exit_time.put(name, Math.max(exit_time.get(name), time_to_removed));

                // 초밥이 사라지는 111번 쿼리를 추가
                queries.add(new Query(111, time_to_removed, -1, name, -1));
            }
        }

        // 사람마다 초밥을 마지막으로 먹은 시간 t를 계산하여 그 사람이 해당 t 때 오마카세를 떠났음을 쿼리로 저장
        for(String name : names) {
            queries.add(new Query(222, exit_time.get(name), -1, name, -1));
        }

        // 전체 Query를 시간순으로 정렬하되 t가 일치한다면 문제 조건상 사진 촬영에 해당하는 300이 가장 늦게 실행
        // 이후 순서대로 보면서 사람, 초밥 수를 count
        queries.sort((q1, q2)-> cmp(q1, q2) ? -1 : 1);

        int people_num = 0;
        int sushi_num = 0;
        for(Query query: queries) {
            // System.out.println("query cmd : " + query.cmd + " | query t : " + query.t);
            if(query.cmd == 100)
                sushi_num++;
            else if(query.cmd == 111)
                sushi_num--;
            else if(query.cmd == 200)
                people_num++;
            else if(query.cmd == 222)
                people_num--;
            else
                sb.append(people_num).append(" ").append(sushi_num).append("\n");
        }

        System.out.println(sb);
    }
}

문제 풀이 소요 시간 : X

정말 어렵게 풀었다. 손님과 초밥을 관리한다는 관점에서는 아마 못 푸는 문제이지 않을까 싶다. '쿼리'라는 객체를 생각해 낼 수 있다면 쉽겠지만 이런 간접적인 객체의 형태를 시험장에서 잡아내기는 어려울 것 같다. 좋은 훈련이 된 문제이다.