https://www.codetree.ai/training-field/frequent-problems/problems/codetree-omakase
1. 문제 요약
L칸으로 이루어진 벨트가 있으며, 각 칸 앞에는 의자가 있다.
벨트는 1초에 한 칸씩 시계방향으로 회전한다.
처음에는 벨트 위에 초밥이 없고, 의자도 모두 비어있다.
이때 3가지 명령이 주어질 수 있다.
1) 주방장의 초밥 만들기
특정 시각 t에 벨트 위치 x 위에 name 이름의 초밥을 하나 올린다.
이는 시각 t의 벨트 회전이 일어난 직후 수행된다.
(같은 위치에 여러 초밥이 있을 수 있고, 그 초밥의 이름이 같아도 상관없음)
2) 손님 입장
특정 시각 t에 벨트 위치 x 앞의 의자에 name 이름의 손님이 앉는다.
(해당 위치 의자에는 사람이 없었다고 가정)
이것도 시각 t의 벨트 회전이 일어난 직후 수행된다.
이때부터 위치 x에 오는, 자신의 이름이 적힌 초밥을 n개 먹고 떠난다.
앉자마자 자신 앞에 해당 초밥이 있다면 바로 먹는다.
여러 개 있는 경우에도 동시에 모두 먹는다. 먹는 시간은 고려하지 않는다.
(오는 손님의 이름은 모두 다르며, 같은 손님은 다시 방문하지 않음)
3) 사진 촬영
특정 시각 t에 현재 상태를 촬영한다.
이는 시각 t의 벨트 회전, 손님의 초밥 먹기 이후 수행된다.
현재 남은 사람 수와 초밥의 수를 출력한다.
이 명령은 최소 한 번 이상 주어진다.
초밥 벨트의 길이 L은 최대 10억
명령의 개수 Q는 최대 10만
진행 시간 t는 최대 10억
서로 다른 이름의 수는 최대 15000
이름의 길이는 최대 30, 소문자 알파벳으로만 이루어진다
각 명령의 t는 모두 다르며, 오름차순으로 주어진다.
시간이 무한히 흐르면 모든 초밥은 사라지고, 손님도 정확히 n개의 초밥을 먹고 떠난다.
2. 문제 접근
벨트의 길이가 최대 10억이기 때문에 벨트를 모두 구현하면 공간복잡도가 넘친다.
마찬가지로 시간도 최대 10억이기 때문에 시간을 1씩 흐르게하면 시간복잡도가 넘친다.
공간복잡도를 해소하기 위해서 해시맵(HashMap)을 사용한다.
시간복잡도를 해소하기 위해서 명령이 있는 시각만 고려한다.
공간복잡도
사람의 이름을 key로 하는 해시맵을 사용해, 초밥의 정보와 손님의 정보를 각각 기록한다.
초밥을 먹는 여부는 현재 시각과 초밥이 들어온 시각의 차이와 초밥의 최초 위치를 이용해 나머지 연산으로 구할 수 있다.
(벨트의 위치는 0부터 L-1까지 주어지기 때문에 깔끔하게 수행됨)
시간복잡도
명령의 개수가 최대 10만이기 때문에, 로 문제를 해결해야 한다.
그런데 명령은 하나하나 모두 훑어야 할 것이므로 결국 각 명령을 에 해결해야 한다.
고려할 점
시간이 무한히 흐르면 모든 초밥은 사라지고, 손님도 정확히 n개의 초밥을 먹고 떠난다.
이는 손님이 떠난 이후로는 해당 손님의 초밥이 새로 생기지 않으며, 각 손님에게 n개의 초밥이 정확히 생성된다는 것을 암시한다.
문제 해결 방법
각 초밥이 어떤 시간에 사라지는 지를 기반으로 한다.
그리고 각 초밥이 사라질 때, 해당하는 손님의 n값을 1씩 뺀다.
만약 n 값이 0이 된다면 손님이 떠나게 하면 된다.
다만 초밥이 사라지는 시간도 따로 기록해서 모든 시간을 훑지 않도록 해야 한다.
초밥은 손님 입장 전 생성되는 경우, 손님 입장 후 생성되는 경우가 있다.
입정 전 생성되는 경우에는 어떤 시간에 사라질 지 알 수 없다. 이 경우의 초밥은 손님 입장 시 시간을 계산하도록 한다.
입장 후 생성되는 경우는 초밥 생성 시 시간을 계산한다.
3. 풀이
각 연산에서는 다음과 같은 작업을 수행해야 한다.
주방장의 초밥 만들기
초밥 정보를 기록한다.
만약 해당 손님이 입장해있다면 초밥이 사라지는 시간도 기록한다.
만약 손님 입장 전이라면 불가능한 시간(ex.-1)으로 기록하고 추후 계산한다.
초밥 개수를 1 증가시킨다.
손님 입장
손님 정보를 기록한다.
해당 손님의 초밥을 훑어 초밥이 사라지는 시간을 기록한다.
손님 수를 1 증가시킨다.
사진 촬영
현재 시간까지 사라지는 초밥을 모두 처리한다.
손님이 n개의 초밥을 먹은 경우에는 손님을 떠나게 한다.
(초밥 개수, 손님 수 감소)
다음과 같은 자료구조를 사용한다.
- 초밥 정보를 기록하는
HashMap: Key는 이름, Value는 초밥 정보를 받는ArrayList - 손님 정보를 기록하는
HashMap: Key는 이름, Value는 손님 정보 - 초밥이 사라지는 시간을 기록하는
PriorityQueue: 작은 시간부터 얻어진다(시간의 오름차순). - 해당 시간에 초밥을 먹는 사람을 기록하는
HashMap: Key는 시간, Value는 이름의ArrayList
변수로 현재 초밥 개수, 현재 사람 수를 사용한다.
이러한 방식으로 접근하면 PriorityQueue를 사용해서 각 초밥이 사라지는 시간을 받기 때문에 시간복잡도는 이 될 것이다.
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
static final int TBD = -1;
static HashMap<String, ArrayList<int[]>> sushi;
static HashMap<String, int[]> customer;
static PriorityQueue<Integer> sushiRemoveTime;
static HashMap<Integer, ArrayList<String>> customerEatSushi;
static int L, Q;
static int sushiCount, customerCount;
// 주방장의 초밥 만들기
public static void makeSushi(int t, int x, String name) {
// 해당 손님이 없다고 가정하면 사라지는 시간을 TBD로 넣는다.
int[] sushiInfo = {t, x, TBD};
// 해당 손님의 정보가 이미 있다면 사라지는 시간을 계산하여 넣는다.
if (customer.containsKey(name)) {
// 손님의 위치
int customerPos = customer.get(name)[1];
// 만나는 데 남은 시간 계산
int timeRemained = customerPos - x;
// 만약 손님의 위치가 더 크다면 단순히 빼서 얻을 수 있지만,
// 만약 초밥의 위치가 더 큰 음수라면 해당 값에 L을 더해야 한다.
if (timeRemained < 0) {
timeRemained += L;
}
int removeTime = t+timeRemained;
sushiInfo[2] = removeTime;
// 추가로 사라지는 시간과 해당하는 이름을 기록해놓는다.
// 해당 초에 정보가 없다면 맵과 우선순위 큐에 정보 새로 추가
if (!customerEatSushi.containsKey(removeTime)) {
ArrayList<String> names = new ArrayList<>();
names.add(name);
customerEatSushi.put(removeTime, names);
sushiRemoveTime.add(removeTime);
}
// 이미 정보가 있다면 꺼내서 맵에 이름만 추가
else {
ArrayList<String> names = customerEatSushi.get(removeTime);
names.add(name);
customerEatSushi.put(removeTime, names);
}
}
// 만약 해당 손님의 초밥이 하나도 없다면 새로 key를 추가
if (!sushi.containsKey(name)) {
ArrayList<int[]> infos = new ArrayList<>();
infos.add(sushiInfo);
sushi.put(name, infos);
}
// 해당 손님의 초밥이 이미 있다면 value에만 값을 추가
else {
ArrayList<int[]> infos = sushi.get(name);
infos.add(sushiInfo);
sushi.put(name, infos);
}
// 초밥 개수 추가
sushiCount++;
}
// 손님 입장
public static void enterCustomer(int t, int x, String name, int n) {
// 손님 정보 기록
int[] customerInfo = {t, x, n};
// 만약 손님에 해당하는 스시가 있다면 스시가 사라지는 시간 계산
if (sushi.containsKey(name)) {
ArrayList<int[]> newSushiInfos = new ArrayList<>();
// 각 스시를 모두 훑으며 진행
for (int[] nowSushi : sushi.get(name)) {
int sushiStartTime = nowSushi[0];
int sushiStartPos = nowSushi[1];
int sushiNowPos = (sushiStartPos + (t - sushiStartTime)) % L;
// 만나는 데 남은 시간 계산
int timeRemained = x - sushiNowPos;
// 만약 손님의 위치가 더 크다면 단순히 빼서 얻을 수 있지만,
// 만약 초밥의 위치가 더 큰 음수라면 해당 값에 L을 더해야 한다.
if (timeRemained < 0) {
timeRemained += L;
}
int removeTime = t+timeRemained;
int[] sushiInfo = {sushiStartTime, sushiStartPos, removeTime};
newSushiInfos.add(sushiInfo);
// 추가로 사라지는 시간과 해당하는 이름을 기록해놓는다.
// 해당 초에 정보가 없다면 맵과 우선순위 큐에 정보 새로 추가
if (!customerEatSushi.containsKey(removeTime)) {
ArrayList<String> names = new ArrayList<>();
names.add(name);
customerEatSushi.put(removeTime, names);
sushiRemoveTime.add(removeTime);
}
// 이미 정보가 있다면 꺼내서 맵에 이름만 추가
else {
ArrayList<String> names = customerEatSushi.get(removeTime);
names.add(name);
customerEatSushi.put(removeTime, names);
}
}
// 초밥 정보 업데이트
sushi.put(name, newSushiInfos);
}
// 손님 정보 추가
customer.put(name, customerInfo);
// 손님 수 증가
customerCount++;
}
// 사진 촬영
public static void takePicture(int t) {
while (!sushiRemoveTime.isEmpty()) {
int now = sushiRemoveTime.peek();
// t보다 크다면 넘김
if (now > t) break;
// 우선순위 큐의 값이 t와 같거나 작다면 계속 진행
else {
sushiRemoveTime.poll();
// 해당 시간에 초밥을 먹는 모든 사람들에 대해 진행
for (String name : customerEatSushi.get(now)) {
// 각 초밥에 해당하는 사람의 먹어야 하는 개수를 낮춤, 초밥 개수도 낮춤
int[] customerInfo = customer.get(name);
customerInfo[2]--;
sushiCount--;
customer.put(name, customerInfo);
// 만약 먹어야 하는 개수가 0이 된다면 손님을 제거하고 손님 수를 낮춤
if (customerInfo[2] == 0) {
customer.remove(name);
customerCount--;
}
}
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 벨트 길이 L, 명령 개수 Q 입력 받기
StringTokenizer st1 = new StringTokenizer(br.readLine());
L = Integer.parseInt(st1.nextToken());
Q = Integer.parseInt(st1.nextToken());
// 현재 손님 수와 초밥 개수 초기화
customerCount = 0;
sushiCount = 0;
// 사용할 자료구조 할당
sushi = new HashMap<>(); // {이름, [만든 시간, 그 때 위치, 사라질 시간]의 리스트}
customer = new HashMap<>(); // {이름, [들어온 시간, 위치, 먹어야 하는 개수]의 리스트}
sushiRemoveTime = new PriorityQueue<>(); // 초밥이 삭제되는 시간을 오름차순을 기록
customerEatSushi = new HashMap<>(); //{시간, 해당 초밥을 먹는 이름의 리스트}
// 명령을 입력 받으며 수행
for (int ord = 0; ord < Q; ord++) {
StringTokenizer stOrd = new StringTokenizer(br.readLine());
int ordNum = Integer.parseInt(stOrd.nextToken());
// 주방장의 초밥 만들기
// 100 t x name
if (ordNum == 100) {
int t = Integer.parseInt(stOrd.nextToken());
int x = Integer.parseInt(stOrd.nextToken());
String name = stOrd.nextToken();
makeSushi(t, x, name);
}
// 손님 입장
// 200 t x name n
else if (ordNum == 200) {
int t = Integer.parseInt(stOrd.nextToken());
int x = Integer.parseInt(stOrd.nextToken());
String name = stOrd.nextToken();
int n = Integer.parseInt(stOrd.nextToken());
enterCustomer(t, x, name, n);
}
// 사진 촬영
// 300 t
else {
int t = Integer.parseInt(stOrd.nextToken());
takePicture(t);
sb.append(customerCount+" "+sushiCount+"\n");
}
}
// 정답 출력
System.out.println(sb);
}
}4. 회고
시간이 무한히 흘렀을 때 모든 초밥이 사라지고, 손님이 정확히 n개의 초밥을 먹는다는 조건이 중요했는데, 이 조건을 제대로 이해하지 못해서 오래 고민했다.
이 조건 덕분에 모든 초밥과 손님이 사라진다는 것을 알 수 있고, 따라서 초밥이 사라지는 시간을 기반으로 문제를 해결할 수 있다.
