해당 글은 항해99 클럽 코딩테스트 스터디에서 진행된 25일차(20241121) 비기너 문제에 대한
TIL(Today I Learned) 내용입니다.
문제 출처) https://school.programmers.co.kr/learn/courses/30/lessons/42626
문제해결에 활용한 핵심포인트!
이 문제에서 주목해야할 부분은 다음과 같다.
1. 주요조건
-
모든 음식의 스코빌 지수를 K 이상 만들고자 한다.
-
스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 섞어 새로운 음식을 만든다.
- 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
-
모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복한다.
-
모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 한다.
-
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 한다.
2. 입력
- 파라미터로 주어져 따로 Scanner 객체가 필요없다.
3. 원하는 답안
-
(i) 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수 return
-
(ii) 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1 return
풀이방향
(1) 해당 문제에 유리한 구조 및 필요한 사항들 파악
-
특정 집합에 원소를 넣었을 때 자동으로 정렬되는 구조면 유리함
-> PriorityQueue 활용 가능
(특정 원소를 넣으면, 가장 작은 수가 맨 앞으로 가게 자동으로 정렬되어짐)
-> 결국, 가장 작은 스코빌 지수와 그 다음으로 작은 스코빌지수에 대한 정보가 필요함 -
가장 작은 스코빌지수를 확인할 수 있는 함수와 해당 스코빌 지수와 그 다음으로 작은 스코빌 지수를 집합에서 빼내고, 그 계산 결과값을 다시 집합에 넣어주는 함수가 있다면 유리함
-> peek(), poll(), add()/offer() 활용 가능 -
출력에 원하는 것을 참고하면 반복문 실행결과, 조건을 만족하기 위해 실행되야하는 최솟값도 필요함
-> answer 변수 설정
(2) 반복문 실행 조건과 종료 조건에 대한 파악
-
실행 조건 : and
(i) 스코빌지수 집합 길이(원소개수)가 1보다 클 때 동안
(ii) 집합 내 가장 작은 스코빌 지수가 K보다 작은 동안
-> 반복문 한번 진행시 answer++ -
종료 조건 : or
(i) 스코빌지수 집합 길이(원소개수)가 1이 되거나
(ii) 가장 작은 스코빌 지수가 K이상이라면
-> 결국 위의 두 조건은 while 반복문이 진행된다면, 결국 자동으로 둘 중 하나가 성립되어 반복문이 끝난다. (따라서, 따로 코드로 구현할 필요는 없다)
(3) 추가 확인 필요 사항
-
반복문이 멈추더라도, 확인해야하는 사항이 있다.
-
바로, scoville 집합의 길이(원소개수)가 1인데, 그 값이 K보다 작을 수 있는 경우이다.
-
그 경우는 위의 문제 조건에 의하면, 결국 모든 scoville 지수를 이용하더라도 결국 모든음식의 스코빌지수를 K값 이상으로 만드는데 실패한 경우다. 이 때는 answer = -1로 한다.
