백준 1417 국회의원 선거 / 문제풀이 java

남순식·2022년 11월 30일
2

백준 실버 5 티어 문제
국회의원 선거 입니다.

우선순위큐를 알고있다면 더 쉬웠을것 같기도하고
하지만 우선순위큐 공부를 진행하지 않았기 때문에
배열만 가지고 문제를 풀었다.

일단 다솜이는 나쁜녀석이다.
간략하게 설명하면
다솜이는 기호 1번으로 출마하였고
N명의 후보자들이 있다.
다솜이는 재능으로 마을사람들의 마음을 읽어
N명의 후보자의 득표수를 미리 알 수 있었고
자신이 당선되기 위해
마을사람들을 돈으로 매수하기로하였다..
따라서
최소 몇명을 매수하여야 당선될 수 있는지 를 구하면 되는 문제였다.

생각해보기

최댓값을 구하라고하면 고민도안하고 죄다 매수하면 될일이다.
최솟값을 구하는 경우는 한가지뿐이기에 정답을 구할 수 있다.

그럼 다시 최솟값을 구하는 방식을 생각해보자

다솜이가 몇표던 마을사람들의 마음을 다읽은 시점에서 중요한 것은
1순위가 누구인지다.
자신이라면 매수할일도 없고
만약 다른사람이라면 그사람을 뽑을 마을사람부터 매수를 시작하면 된다.

그렇다고 그사람표만 뺏으면 될것인가 생각해보자
다솜이가 현재 2등이라면 그렇다.
허나 다른상황이라면 그렇지않다.
원래 1등 득표수를 빼앗아 나에게 투표하게만들었을 때
1등이 내려오면서 당시에 2등이었던 사람이 1등으로 바뀔수 있다.
그럼 그땐 다솜이가 바뀐 1등의 득표수를 빼앗아 오면된다.
이부분을 고려하고 메서드를 만들었다.

public int winCnt (int[] vote) {

        int count = 0;
        int maxIdx = 0;
        for (int i = 0; i < vote.length; i++) {
            if (vote[maxIdx] < vote[i]){
                maxIdx = i;
            }
        }
        while (vote[maxIdx] != 0){
            for (int i = 0; i < vote.length; i++) {
                if (vote[maxIdx] <= vote[i]) {
                    maxIdx = i;
                }
            }
            if (maxIdx == 0){
                return count;
            }
            vote[0]++;
            vote[maxIdx]--;
            count++;
        }
        return count;
    }

바뀌는 1등에게 투표할 사람들을 매수하기위해
계속해서 1등이 누군지 체크해 주며
체크를 한시점에서 1등인 사람에게서 표를 가져오면서
자신이 1등이 될때까지 반복하면 문제 해결이다.

주어진 N명의 후보가 적어서 풀수 있었던거 같다.
만일 제한이 더 컸으면 복잡도를 생각해보았을때 틀렸다고 할 수 있다.
따라서
풀었지만 복잡도를 고려하여 나중에 다시 한번 풀어봐야 한다고 생각한다.

profile
java 주니어

2개의 댓글

comment-user-thumbnail
2022년 11월 30일

스마트해요 ^^

1개의 답글