출처: https://www.acmicpc.net/problem/1417
Team: 현범, 효권,준희,예지
문제
당선 되기 위해 최소한의 인원을 매수해라!
다솜이는 선거에 출마한다. 다솜이는 마음을 읽는 기계를 사용해 사람들이 누구를 찍을지 미리 알 수 있다고 한다. 기계를 사용해 자신을 포함한 다른 후보자들의 득표수를 알고있다. 부패한 다솜이는 사람들을 돈으로 매수해 자신이 뽑히게 만들 것이다. 다솜이가 최소한의 인원만 매수할 수 있도록 돕는 프로그램을 작성해야한다.
입출력 예제
입출력을 이해해보자.
먼저,
첫째 줄에는 다솜이가 출마하는 선거에 지원하는 후보자들의 수(N)를 입력받는다.
둘째 줄부터 N번째 줄까지 다솜이를 포함한 후보자들의 예상 득표수를 입력한다.
다솜이는 무조건 기호 1번이고, 후보자는 최대 50명 까지, 득표수는 100 이하의 정수값이다.
아래의 표를 통해 해결해야할 과제 이해해보자
| N 명의 후보자 | 각 후보자의 예상 득표수 (적중률 100%) |
| 1번 후보자 다솜이 | 5 |
| 2번 후보자 홍길동 | 10 |
| N번 후보자 삼지창 | 8 |
위의 예시 표를 살펴보면,
다솜이는 먼저 가장 많은 득표수를 받고있는 홍길동의 표를 매수해야한다.
다솜이가 홍길동의 지지자 3명을 매수하면,
| N 명의 후보자 | 각 후보자의 예상 득표수 (적중률 100%) |
| 1번 후보자 다솜이 | 8 (홍길동 3표매수) |
| 2번 후보자 홍길동 | 7 |
| N번 후보자 삼지창 | 8 |
가장 유력한 후보자였던 홍길동의 표는 이길 수 있게되었다.
하지만 아직 삼지창이 남아있다. 이대로라면 삼지창과 동표이기 때문에 다솜이는 삼지창의 표도 1개 매수해야한다.
| N 명의 후보자 | 각 후보자의 예상 득표수 (적중률 100%) |
| 1번 후보자 다솜이 | 9 (홍길동 3표 매수 + 삼지창 1표 매수) |
| 2번 후보자 홍길동 | 7 |
| N번 후보자 삼지창 | 7 |
따라서 다솜이는 총 4표를 매수해 선거에서 당선될 수 있을 것이다.
Main
사용 알고리즘
"그리디 알고리즘"
그리디 알고리즘에 대해선, 이전에 발표를 했었던 내용이기 때문에 간단한 개념만 설명할 것이다.
그리디 알고리즘은 알고리즘의 한 이름이라기 보단, 알고리즘을 접근하는 하나의 방식이다.
하지만 그리디 알고리즘에는 치명적인 한계가 존재한다. 아래의 그림을 통해 설명하겠다.
우리의 목표가 가장 최저의 값을 찾는 것이라고 가정했을 때, 특정 상황 (S) 이 주어졌을 때,
오른쪽 그림에서는 S 상황에서의 가장 좋은 선택이 실제로도 가장 최적의 값을 도출했지만,
왼쪽 그림에서는 S 상황에서의 가장 좋은 선택이 실제로 가장 좋은 선택은 아니다.
이렇게 그리디 알고리즘은 문제의 주어진 상황이 어떠하냐에 따라 최적값을 내놓을 가능성이 달라지게 된다.
따라서, 문제를 해결할 때 해당 문제가 그리디 알고리즘을 통해 최적의 값을 도출할 수 있을지 고민한 후에 사용해야한다.
How
다솜이를 포함한 후보자 1~N 명 존재, 만약 i 번째 후보자가 다솜이보다 득표수가 높다면,
for (N명의 후보자 중 i 번째 후보자가 다솜이의 득표수보다 작을 때까지){
다솜이의 득표수 +1, 다솜이보다 표가 많은 후보자의 득표수 -1
};
이와 같은 방법으로 문제를 풀 생각이다.
우려가 되는 점은, 다솜이의 득표수가 2명 이상의 다른 후보자의 득표수와 동점이 될 때인데, 누구의 표를 매수할지 선언해주지 않는다면 오류가 생길 것 같다. 아래는 지금까지 만든 수식을 코드화 한 것이다.
중간 과정
public static void main(String[] args) {
System.out.println(" 전체 후보자 수와 각 후보자의 득표수를 입력하시오 ");
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 전체 후보자의 수 입력받기
int [] cd = new int [N]; //N 명의 후보자 만큼 후보자를 입력받을 배열
int sum = 0; // 매수를 위해 필요한 표의 수를 저장하기 위해 사용하는 변수
for (int i = 0; i<cd.length; i++){ // 입력받은 전체 후보자의 수만큼 후보자의 득표수 입력받기
cd[i] = sc.nextInt();
for (int j = 1; j<cd.length; j++){
if (cd[0] <= cd[j]){
cd[0] +=1;
cd[j] -=1;
sum ++;
}
}
}
System.out.println("--------");
for (int u =0; u<cd.length; u++){
System.out.println( cd[u]+ " 번째 후보자의 득표수: " + cd[u]);
}
System.out.println( "매수해야하는 표 수: "+ sum);
}
}
해당 코드는 문제를 풀던 중간에 겪은 시행착오가 담겨있다.
우선 위의 코드를 실행했을 때 결과를 보겠다.
입력값은 예제 입력문과 비교하기 위해 각 후보자의 득표수를 5, 6, 7 개로 지정했다.
3 명의 후보자와 다솜이의 득표수는 5개, 나머지 각 후보자의 득표수는 7 개와 6 개인 상황인데,
출력문을 살펴보면 다솜이가 2번 후보자의 표 2 개를 매수해 선거에서 당선되는 것으로 코드가 정상 작동하는 것처럼 보인다.
하지만, 입력값을 예제 입력문과 동일하게 바꿔보겠다.
앞서 설명한 예제 입출력을 살펴보면 다솜이가 매수해야할 '최소' 표의 수는 2 개이다. 하지만 코드의 실행 결과는 매수해야할 표의 수가 3개이다. 문제에서 제시한 '최소' 로 매수해야한다 라는 조건을 만족하지 못한 것이다
어떻게 이런 출력 결과가 만들어졌는가?
코드의 실행 순서를 살펴보겠다.
먼저 바깥쪽 for 문 (이하 for.1 문) 은
사용자에게 입력받은 후보자의 수 만큼 각 후보자의 득표 수를 입력받아 'cd' 라는 배열에 저장하는 실행문이다.
for.1 문이 실행되는 만큼 안쪽 for 문 (이하 for.2 문) 이 실행되게 되는데,
for.2 문은 변수 j 가 1 부터 시작하고, 전체 후보자의 수만큼 실행된다.
(for.2 문의 변수 j 를 1 로 준 이유는, 'cd[]' 에 저장된 후보자들의 득표수 중 'cd[0]' 은 다솜이의 득표수이기 때문에, 다솜이를 제외한 후보자들의 득표수를 검토하기 위해 j 변수를 1로 주었다.)
for.2 문 안에 있는 if 문은 'cd[0]' (기호 1번 다솜이의 득표수) 보다 'cd[j]' (기호 2번 후보자 ~ 기호 N 번 후보자의 득표수) 가 높다면 실행되는 문인데,
'cd[0]' 를 +1 하고, 'cd[j]' 를 -1 한다. 이후 if 문이 실행되었다면 sum 변수를 +1 하며 실행을 끝낸다.
결과적으로 for.2 에서 실질적인 계산이 이루어지는 것인데,
j 번째 후보자가 다솜이와 같거나 더 많은 득표수를 가지고 있다면 해당 후보자의 득표수는 -1 이 되고, 다솜이의 득표수는 +1 이 되는 것이다.
이렇게 되면 아래와 같은 상황이 발생한다.
1. 3명의 후보자 득표수 (1번 다솜이 : 5 , 2번 후보자 : 7, 3번 후보자 : 7 )
2. 2번 후보자의 득표수 1개 뻇기 (각 후보자의 득표수: 6, 6, 7)
3. 2번 후보자의 득표수 1개 뻇기 (각 후보자의 득표수: 7, 5, 7)
4. 3번 후보자의 득표수 1개 뺏기 (각 후보자의 득표수: 8, 5, 6)
위에서 노란색 으로 표시된 부분이 문제의 발생 원인이다.
2번째 실행 결과 (6,6,7) 에서 2번 후보자의 득표수를 한번 더 뺏는 것이 아니라, 3번 후보자의 투표수를 1개 뺏었다면 각 후보자의 득표수는 (7,6,6) 이 되므로 조건에 성립되는 결과를 만들어냈을 것이다.
결과적으로 3번째 실행 과정을 수정해야한다.
해결방안
해당 문제점을 해결하기 위해 여러가지 시도를 해봤지만
다솜이와 다른 후보자의 투표수가 같을 경우와 다솜이의 투표수가 다른 후보자의 투표수보다 적을 때가 동시에 발생되는 경우를 서로 분리할 방법을 떠올리지 못했다.
(조건을 잘못줬었나..)
그래서 선택한 방법은 다솜이를 제외한 후보자들의 득표수를 내림차순 정렬하여, 연산을 했다.
(물론 내 머리에서 나온 방법은 아니지만..)
배열을 내림차순으로 정렬하는 메서드는 'Arrays.sort()' 를 사용했다.
해당 메서드를 사용할 때 String 값을 담은 배열은 간단하게 사용가능한데, int 형의 배열은 배열을 선언할 때 Integer 형태로 선언해야 한다.
아래는 전체 코드이다.
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class ElectionOfDasom {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(" 전체 후보자의 수를 입력한 뒤, 각 후보자의 투표수를 입력하시오 ");
int N = sc.nextInt(); //전체 후보자의 수 입력
int Dasom = sc.nextInt(); //다솜이의 득표수 따로 받기
Integer cd[] = new Integer[N-1]; // 이후 내림 차순 정렬을 받기 위해 Integer 타입의 배열 선언
int sum = 0; //매수해야 하는 사람 수
for(int i = 0; i < cd.length; i++){ // 다솜이의 투표수를 제외한 전체 후보자의 투표수를 입력받음
cd[i] = sc.nextInt();
}
for (int j = 0; j < cd.length; j++){ // 다솜이를 제외한 후보자들의 투표수를 비교하기 위한 반복문
Arrays.sort(cd, Collections.reverseOrder()); // 다솜이를 제외한 후보자들의 투표수를 내림 차순 정렬
if(N == 1 || cd[0] < Dasom) {
// 만약 전체 후보자가 다솜이 혼자이거나, 전체 후보자 중 가장 득표수가 많은 사람 (cd[0]) 이 다솜이보다 득표수가 낮다면 반복문 바로 중단
break;
}else{
Dasom++;
cd[0]--;
sum++;
}
}
System.out.println("----------매수 투표 결과----------");
System.out.println("다솜이의 투표수: " + Dasom);
System.out.println("2번 ~ " + N + " 번 후보자의 투표수: "+ Arrays.toString(cd));
System.out.println("다솜이가 매수해야할 투표수: " + sum);
}
}
핵심이 되는 for 문을 기준으로 코드를 살펴보겠다
우선 첫번째 for 문은 단순히 후보자의 수만큼 입력값을 받는 반복문이다.
두번째 for 문이 중요한데,
반복 조건은 다솜이를 제외한 후보자의 수만큼 반복하도록 선언했다.
이후, 앞선 for 문 에서 입력 받은 cd [] 를 내림 차순으로 정렬한다.
해당 과정을 거치면 아래의 예시와 같이 for 문 실행 될 때마다 index 0번째는 가장 득표수가 많은 후보자의 표 수가 되는것이다.
예시
Dasom : x 개
cd [ 0~cd.length ] : 10, 9, 6, 4, .., 1
그 다음 if 문을 선언했다.
if 문의 조건으로는 만약 전체 후보자가 1명이거나, 다솜이를 제외한 후보자들 중 0번째 index 를 가진 득표수 (가장 많은 득표수)가 다솜이의 득표수보다 적다면 반복문을 종료한다. (지금 다시보니 break 를 안 줬어도 상관 없었을거같네..?)
이후 else 문을 선언해, 위에서 조건이 성립하지 않는다면 다솜이의 투표수를 1개 더하고, cd [0] (득표수가 가장 많은 표)
를 1개 빼는 형식으로 조건문을 마무리했다.
아래는 실행 결과이다
아쉬운 점은 백준에 해당 코드를 제출했을 때 코드가 틀렸다고 떴다.
예시 입출력과 모든 조건을 만족했다고 생각되는데, 왜 틀렸는지는 찾지 못했다.
참고 사이트
https://coding-factory.tistory.com/549
[Java] 자바 배열 정렬하기(오름차순, 내림차순) Arrays.sort()
자바에서 배열이나 리스트를 정렬하려고 한다면 java.util.Arrays 클래스의 sort() 메서드를 사용하시면 따로 정렬 로직을 짜지 않아도 한번의 메소드 호출로 간편하게 배열이나 리스트를 정렬할 수
coding-factory.tistory.com
'Team 발표 과제' 카테고리의 다른 글
| 백준 (자바) 17608번 막대기 (3) | 2024.10.03 |
|---|---|
| 백준 (자바)문제 7785번 "회사에 있는 사람" (0) | 2024.10.03 |
| No 2775번 부녀회장이 될테야 (0) | 2024.10.02 |
| 백준 30802번 웰컴 키트 (0) | 2024.10.02 |
| 백준 2839번 설탕배달 (1) | 2024.10.01 |
