[코딩테스트] 백준 - 항해99클럽 코딩테스트 스터디 21일차 : 센티와 마법의 뿅망치

해당 글은 항해99 클럽 코딩테스트 스터디에서 진행된 21일차(20241117) 비기너 문제에 대한
TIL(Today I Learned) 내용입니다.

	문제 출처) https://www.acmicpc.net/problem/19638
    

---

문제해결에 활용한 핵심포인트!

이 문제에서 주목해야할 부분은 다음과 같다.

1. 주요조건

• 뿅망치에 맞은 사람의 키가 ⌊ 뿅망치에 맞은 사람의 키 / 2 ⌋로 변한다.
  (단, 키가 1인 경우 뿅망치의 영향을 받지 않는다.)

• 마법의 뿅망치 횟수 제한이 있다.

• 매번 가장 키가 큰 거인 가운데 하나를 때린다.
  
  

2. 입력

• 첫 번째 줄
  : 센티를 제외한 거인의 나라의 인구수 N (1 ≤ N ≤ 105)과 센티의 키를 나타내는 정수 Hcenti (1 ≤ Hcenti ≤ 2 × 109), 마법의 뿅망치의 횟수 제한 T (1 ≤ T ≤ 105)가 빈칸을 사이에 두고 주어진다.
  -> N Hcenti T

• 두 번째 줄
  : N개의 줄에 각 거인의 키를 나타내는 정수 H (1 ≤ H ≤ 2 × 109)가 주어진다.

3. 원하는 출력

• 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있을까?
  • (i) 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우,
    : 첫 번째 줄에 YES를 출력, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수를 출력
  • (ii) 거인의 나라에서 센티보다 키가 크거나 같은 거인이 있는 경우,
    : 첫 번째 줄에 NO를 출력, 두 번째 줄에 마법의 뿅망치 사용 이후 거인의 나라에서 키가 가장 큰 거인의 키를 출력

풀이방향

(1) 해당 문제에 유리한 구조 및 필요한 사항들 파악

• 특정 집합에 원소를 넣었을 때 자동으로 정렬되는 구조면 유리함
  -> PriorityQueue, Collections.reverseOrder() 활용 가능

• 가장 큰 키의 거인을 확인할 수 있는 함수와 해당 거인의 키를 없애고 키/2 값을 다시 넣어주는 함수가 있다면 유리함
  -> peek(), poll(), add() 활용 가능

• 출력에 원하는 것 중 (i)를 참고하면 뿅망치의 실제 사용횟수를 세는 변수도 필요함
  -> usedChance

(2) 뿅망치사용 반복문 실행 조건과 종료 조건에 대한 파악

• 실행 조건
  (i) 거인들의 키 집합이 비어있지 않고,
  (ii) 뿅망치 사용횟수가 남아있을 때

• 종료 조건
  (i) 가장 큰 거인의 키가 1일 때
  (ii) 가장 큰 키의 거인이 센티의 키보다 작을 때
  (iii) 반복문 실행 조건이 끝났을 때 (결국, 뿅망치 사용횟수가 남아있지 않을 때)

주의사항

• 처음엔 센티키가 1이면 무조건 "NO"임을 알아서, 따로 조건문을 분리하였지만,
  추가적으로 뿅망치횟수 적용 후의 가장 큰 거인의 키를 출력으로 요구하기 때문에
  결국은 위의 결국은 위의 조건들 안에 포함되어있다!!