해당 글은 항해99 클럽 코딩테스트 스터디에서 진행된 22일차(20241118) 비기너 문제에 대한
TIL(Today I Learned) 내용입니다.
문제 출처) https://leetcode.com/problems/take-gifts-from-the-richest-pile/description/
문제해결에 활용한 핵심포인트!
이 문제에서 주목해야할 부분은 다음과 같다.
1. 주요조건
-
gifts 집합 안의 가장 큰 수에 대해서, 1초마다 그 값의 제곱근(또는 제곱근의 내림)으로 그 값을 줄인다.
-
시간 제한(k초, 결국 횟수)이 있다.
-
매번 가장 큰 수의 선물 을 선택하여 줄인다.
2. 입력
- 파라미터로 주어지기 때문에 따로 Scanner 객체를 생성할 필요가 없다.
3. 원하는 출력
- 마지막으로 남은 선물들의 모든 총 합(sum)을 출력한다.
풀이방향
- 주어진 gifts배열에 대해서 해당 배열을 PriorityQueue 안에 넣으면 된다.
(1) 해당 문제에 유리한 구조 및 필요한 사항들 파악
-
특정 집합에 원소를 넣었을 때 자동으로 정렬되는 구조면 유리함
-> PriorityQueue, Collections.reverseOrder() 활용 가능
(특정 원소를 넣으면, 가장 큰 수가 맨 앞으로 가게 자동으로 정렬되어짐) -
가장 큰 수의 선물을 확인할 수 있는 함수와 해당 선물을 없애고 그 값의 제곱근(또는 제곱근의 내림)을 다시 넣어주는 함수가 있다면 유리함
-> peek(), poll(), add() 활용 가능
-> (int) Math.sqrt(N) : N의 제곱근의 값의 내림 (=결국 정수형으로 형변환하는것과 같음) -
출력에 원하는 것을 참고하면 반복문 실행결과 남는 maxHeap의 원소들의 합도 필요함
-> sum 변수 설정
-> 단, sum변수는 long으로 데이터타입 설정해야한다!
(그렇지 않고 int로 설정시, 나중에 testcase실행 중에 overflow가 발생하여 틀린다.)
(2) 반복문 실행 조건과 종료 조건에 대한 파악
-
실행 조건
(i) gifts 집합이 비어있지 않고,
(ii) 반복문 실행시간(turns)가 k(초)보다 작을 동안 -
종료 조건
(i) gifts 중 가장 큰 수가 1일 때
(ii) 반복문 실행 조건이 끝났을 때 (결국, 반복문이 k번 실행되었을 때)
