[코딩테스트 재활 프로젝트] 1일차 더맵게 / 기능 개발

코딩테스트 재활 프로젝트를 시작했다.

과연 코딩테스트 기회라도 주어질지 모르겠지만 일단은 시작해본다.

 

---

1. 기능개발

프로그래머스 - 기능개발

이 문제의 핵심은 단순히 큐나 스택을 사용하는 것이 아니라 어떤 값을 기준으로 현재 배포 그룹을 판단할 것인가? 를 묻는 문제라고 생각한다.

먼저 각 기능이 배포되기까지 필요한 일수를 계산한다.

예를 들어 다음과 같다고 하자.

1 2 3 2

각 기능이 독립적으로 배포 가능한 날짜는 이렇게 되지만, 실제로는 앞의 기능이 먼저 배포되어야 하기 때문에 배포 그룹은

[1] [2] [3, 2]

가 된다.

따라서 정답은

1 1 2

이다.

처음에는 이 값을 stack에 넣어서 가장 최근에 들어온 값과 비교하면 되지 않을까 생각했다.

그런데 7, 5, 6 같은 경우를 생각해보니 문제가 있었다.

7
5
6 ← top

현재 그룹에서 중요한 값은 가장 최근에 들어온 6이 아니라 **이 그룹에서 가장 늦게 배포되는 7**이다.

따라서 stack.top()을 기준으로 판단하는 방식은 적절하지 않았다.

그렇다면 현재 그룹에서 가장 큰 값을 빠르게 확인하면 되겠다는 생각이 들어 priority_queue로 변경했다.

priority_queue<int> pq;

priority_queue의 top()은 현재 그룹의 최대값이기 때문에,

7 5 6

에서는 7을 기준으로 다음 기능을 판단할 수 있다.

그리고 8이 등장한다면

7 5 6 8

기존 그룹의 최대 배포일인 7보다 8이 크기 때문에 기존 그룹을 종료하고 새로운 배포 그룹을 시작하면 된다.

이 방식으로 정답을 맞혔다.

그런데 여기서 한 번 더 생각해보니 Priority Queue조차 필요하지 않았다.

내가 실제로 필요한 것은 지금까지 들어온 모든 배포일이 아니라,

현재 배포 그룹에서 가장 늦게 배포되는 날짜 하나

뿐이었다.

따라서 굳이 모든 값을 priority_queue에 넣어 최댓값을 관리할 필요 없이 int maxDay 하나만 유지하면 된다.

Priority Queue
O(N log N)

→

최대 배포일 변수 하나
O(N)

결국 오늘 이 문제에서 가장 중요했던 것은 어떤 자료구조를 선택하는 것이 아니라,

"이 문제를 풀기 위해 내가 계속 유지해야 하는 상태가 무엇인가?"

를 찾는 것이었다.

처음에는 자료구조를 사용해서 해결했지만, 문제를 다시 바라보면서 필요한 상태를 하나의 변수로 압축할 수 있었다.

오랜만에 코딩테스트를 풀다 보니 이런 사고 과정 자체가 꽤 재미있었다.

---

2. 더 맵게

프로그래머스 - 더 맵게

두 번째 문제는 힙을 사용해야겠다는 생각 자체는 비교적 쉽게 떠올릴 수 있는 문제였다.

핵심은 최소 힙에서 가장 작은 두 개의 값만 계속 꺼내서 사용한다는 것이다.

모든 음식의 스코빌 지수를 K 이상으로 만들어야 하기 때문에, 현재 가장 맵지 않은 두 음식을 선택해서 다음과 같이 합성한다.

섞은 음식의 스코빌 지수
= 가장 맵지 않은 음식의 스코빌 지수
+ (두 번째로 맵지 않은 음식의 스코빌 지수 × 2)

따라서 최소 힙을 사용하면 매번 가장 작은 두 값을 쉽게 가져올 수 있다.

1 2 3 9 10
↑ ↑

여기서 1과 2를 꺼내서 합성하고 다시 힙에 넣는다.

이 과정을 모든 음식이 K 이상이 될 때까지 반복하면 된다.

그런데 문제를 읽으면서 조금 고민했던 부분이 있었다.

예를 들어 스코빌 지수가

1 1 2 3

이라면 1, 1을 합성할 때

"두 번째로 맵지 않은 음식의 스코빌 지수"

는 1인가 2인가?

처음에는 문장을 다시 생각해봤는데, 이 문제에서는 1이다.

현재 음식들을 순서대로 보면

1번째 음식 → 1
2번째 음식 → 1
3번째 음식 → 2
4번째 음식 → 3

이고, 가장 맵지 않은 두 음식은 첫 번째 1과 두 번째 1이기 때문이다.

여기서 중요한 것은 같은 스코빌 지수를 가진 음식이라고 해서 중복을 제거하면 안 된다는 것이다.

1, 1은 스코빌 지수가 같을 뿐 서로 다른 음식이므로 둘을 모두 사용해서 합성해야 한다.

만약 중복을 제거한다면 음식의 개수 자체가 달라지기 때문에 문제의 조건을 훼손하게 된다.

결국 이 문제에서 중요한 것은

항상 현재 상태에서 가장 작은 두 값을 선택해야 한다.

는 것을 파악하는 것이었다.

기능개발에서는 현재 그룹의 최대값을 계속 확인해야 했다면, 더 맵게에서는 전체 데이터에서 최소값 2개를 계속 꺼내야 한다.

비슷하게 자료구조를 사용하는 문제처럼 보이지만, 필요한 상태와 값을 선택하는 기준은 완전히 다르다.

---

Day 1을 마치며

"이 문제에서 내가 계속 가지고 있어야 하는 정보가 무엇이지?"