[2019 KAKAO BLIND RECRUITMENT] 무지의 먹방 라이브(시행착오 포함)

https://www.welcomekakao.com/learn/courses/30/lessons/42891

코딩테스트 연습 - 무지의 먹방 라이브 | 프로그래머스

 

가장 까다로웠던 문제이다. 정확성은 쉽게 통과할 수 있지만, 효율성에 대해서는 통과하기가 어렵다.

또한, 정답과 유사한 아이디어를 생각한다고 해도, 자료구조를 쓰는 방식에 따라서 효율성 테스트를 통과할 수 있을지 없을지가 결정된다.

 

 

---

이 문제의 정확성 테스트를 통과하기 위해서는, 쉽게 매초마다 Action을 취해주면서 최종적으로 방송 중지 시간 이후에 먹어야 할 음식의 순서를 결정해주면 된다. 이 부분은 간단하게 구현할 수 있다.

 

 

하지만, 중요한 것은 효율성 테스트를 통과하기 위해서는 매초마다 Action을 취하면 안된다. 주어진 음식들의 소요 시간을 보고, 주어진 방송 중지 시간으로 빠르게 접근해야 한다.

 

---

 

방송 중지 시간으로 빠르게 접근하기 위해서는, 음식 소요 시간들을 정렬할 필요가 있다. 음식 소요 시간들을 오름차순 순으로 정렬한다. 가장 작은 값 * 음식들의 갯수를 이용해서 방송 중지 시간으로 빠르게 접근해야 한다.

 

 

가장 작은 값과 음식들의 갯수를 이용하는 이유는,

 

1. 가장 작은 소요 시간을 가진 음식이 먼저 사라진다.

2. 음식이 사라지면서 탐색해야 할 음식들의 갯수가 변경된다.

3. 음식들의 갯수가 달라지면, 특정 음식을 섭취할 때 걸리는 시간이 변경된다.

 

 

 

가장 작은 값 * 음식들의 갯수의 값을 누적하다가 k보다가 커진다면 동작을 중지하고, k에서 누적된 값을 뺀 다음에 모듈(mod) 연산으로 방송 중지 이후 먹어야 할 음식을 찾으면 된다.

 

해설과 똑같은 아이디어로 문제를 접근했지만, 효율성 테스트에서 시간 초과가 발생했다.

 

---

 

시행착오를 겪은 방법은 다음과 같다.

 

1. 우선순위큐를 이용해서 음식 소요 시간들을 정렬, Set 자료구조로 음식 인덱스 저장

2. 반복문을 만들고 우선순위큐의 가장 작은 값을 Pop + Set 자료구조에서 인덱스 삭제 + 시간 누적 계산

3. 누적된 시간이 k보다 커질 경우 동작을 중지

4. Set 자료구조에서 방송 중지 이후 먹어야 할 음식 찾기

 

 

위의 방식은 시간 초과외에는 문제될 것이 없다.

 

이 것을 파악하기 위해서는, 시간복잡도에 대한 배경지식이 있으면 더 좋다. 우선 음식 소요시간들을 정렬한 것은 크게 문제가 되지 않는다. 하지만, Set 자료구조를 사용한 것과, Pop 연산을 사용한 것은 시간 복잡도를 증가시킨다. 

 

 

효율성 테스트에서 food_times의 원소들이 많으므로, Pop 연산이나 Set에서 삭제 연산은 시간 초과를 발생시킬 수 있다.

 

 

따라서, 문제를 해결하기 위해서는 최소한의 자료구조, 연산이 필요하다.

 

 

---

 

아래의 방법은 효율성 테스트를 통과한 방법이다.

 

1. vector<pair<int, int>> 자료구조로 음식들의 소요 시간을 정렬

2. 기존의 값 삭제할 필요도 없고, 삭제하면 시간초과가 발생. 따라서, 기존의 값을 유지한 채로, 시간 누적 계산

3. 누적된 시간이 k보다 커질 경우에 멈춘 벡터의 인덱스의 시작부터 벡터의 끝까지는 앞으로 탐색해야 할 벡터의 원소들을 의미, 따라서 assign 함수를 통해서 새로운 벡터에 해당 원소들을 넣어준다.

4. 새로운 벡터를 index 기준으로 정렬해서, 방송 중지 이후 먹어야 할 음식 찾기

 

 

---

 

위의 방식으로 접근하면 문제를 풀 수 있다!

 

* 문제를 해결할 때, 항상 최소한의 자료구조 및 연산을 생각하도록 하는 습관을 들여야 한다.

 

 

문제의 정답 코드를 원하시는 분은,

댓글을 달아주세요!