해당 글은 항해99 클럽 코딩테스트 스터디에서 진행된 24일차(20241120) 비기너 문제에 대한
TIL(Today I Learned) 내용입니다.
문제 출처) https://www.acmicpc.net/problem/1417
문제해결에 활용한 핵심포인트!
이 문제에서 주목해야할 부분은 다음과 같다.
1. 주요조건
-
국회의원 후보는 N명이고, N명 각각의 득표수를 알 수 있다. (마을 주민 총 인구 수 M명)
-
다솜이는 기호 1번 이다. 다솜이는 사람들의 마음을 읽어서 자신을 찍지 않으려는 사람을 돈으로 매수해서 국회의원에 당선이 되게 하려고 한다. (돈으로 매수한 사람은 반드시 다솜이를 찍는다고 가정한다.)
-
다른 모든 사람의 득표수 보다 많은 득표수를 가질 때, 그 사람이 국회의원에 당선된다.
2. 입력
- 첫째 줄에 후보의 수 N이 주어진다.
- 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다.
3. 원하는 출력
- 다솜이가 매수해야하는 사람의 최솟값
풀이방향
(1) 해당 문제에 유리한 구조 및 필요한 사항들 파악
-
특정 집합에 원소를 넣었을 때 자동으로 정렬되는 구조면 유리함
-> PriorityQueue, Collections.reverseOrder() 활용 가능
(특정 원소를 넣으면, 가장 큰 수가 맨 앞으로 가게 자동으로 정렬되어짐)
-> 결국, 다솜 제외한 후보들의 득표수 집합에서 가장 많이 득표한 후보와의 비교가 필요하므로! -
가장 큰 득표수를 확인할 수 있는 함수와 해당 득표수를 없애고 그 값에 -1을 하고 결과값을 다시 넣어주는 함수가 있다면 유리함
-> peek(), poll(), add()/offer() 활용 가능 -
출력에 원하는 것을 참고하면 반복문 실행결과, 조건을 만족하기 위해 실행되야하는 최솟값도 필요함
-> count 변수 설정
(2) 반복문 실행 조건과 종료 조건에 대한 파악
-
실행 조건 : and
(i) 1번후보(다솜)제외 나머지 후보들의 득표수 집합이 비어있지 않고,
(ii) 해당 집합에서 가장 큰 득표수가 1번후보(다솜)보다 더 많거나 같은 경우 -
종료 조건 : or
(i) 1번후보(다솜)제외 나머지 후보들의 득표수 집합이 없을 때 or
(ii) 해당 집합에서 가장 큰 득표수가 1번후보(다솜)보다 더 적은 경우
더 알아보기
- "N은 50보다 작거나 같은 자연수이고, 득표수는 100보다 작거나 같은 자연수이다." 라는 조건은 왜 필요할까
-> 강사님답변) 문제에서 분기 처리를 해준 것.. 문제 푸는 우리의 고려사항을 줄여줌
