[Java] 프로그래머스 [자비스앤빌런즈 2022 코딩테스트] 선거

import java.util.HashMap;

public class Solution {
	
	public static int[] solution(int[][] orders) {
		int[] answer = {};
		int studentCnt = orders.length; // 5
		int tempCnt = 0; // 후보의 현재 특표 수를 담을 임시 변수
        
		HashMap<Integer, Integer> nomineeHm; // 후보 번호 : 득표 수 담을 해시맵
		HashMap<Integer, Integer> dropHm = new HashMap<>(); // 탈락한 후보 번호 담을 해시맵
        
		int halfNum = 0; // 반수
        
		answer = new int[2]; // 회차, 후보 번호
        
		if (studentCnt % 2 == 0) {
			halfNum = studentCnt / 2; // 짝수일 경우 반수는 (학생 수 / 2)
		} else {
			halfNum = (studentCnt + 1) / 2; // 홀수일 경우 반수는 ((학생 수 + 1) / 2)
		}
        
		int checkCnt = 0; // 선거 카운트
        
		int rowNum = 0; // 탈락한 학생을 제외한 0순위 후보를 가져오기 위한 변수 (0부터 증가하며 체크)
        
		for (int j = 0; j < studentCnt; j++) { // 선거 회수 증가를 위한 반복문
        	
			nomineeHm = new HashMap<>();
        	
			for (int k = 0; k < studentCnt; k++) {
        		
				if (dropHm.get(k) != null) continue; // 후보에서 탈락한 학생이 있다면 그 학생을 제외하고 후보 등록
        		
				nomineeHm.put(k, 0); // 후보 등록 // 표를 얻지 못했더라도, 탈락된 후보가 아니라면 이번 회차의 당선 또는 탈락의 대상이 됨
			}
        	
			for (int i = 0; i < studentCnt; i++) { // 행
        		
				rowNum = 0; // 0순위 후보
        		
				while (dropHm.get(orders[i][rowNum]) != null) { // 0순위 후보가 탈락한 학생이라면 그 다음 순위 학생 체크 (탈락하지 않은 최대 우선 순위까지 체크)
					rowNum++;
					if (rowNum > studentCnt - 1) break;
				}
        		
				tempCnt = nomineeHm.get(orders[i][rowNum]);
				nomineeHm.put(orders[i][rowNum], tempCnt + 1); // 후보의 득표 수 증가
			}
        	
			checkCnt++; // 선거 카운트 증가
        	
			int[] dropNum = new int[2]; // 이번 회차에서 탈락할 후보의 번호, 득표 수를 담을 배열
        	
			dropNum[1] = studentCnt; // 5
        	
			for (int i = 0; i < studentCnt; i++) {
        		
				if (nomineeHm.get(i) == null) { // 이미 탈락한 후보라면 continue
					continue;
				} else { // 정상 후보라면
        			
					if (nomineeHm.get(i) >= halfNum) { // 반수를 넘었다면 최종 당선 후보(단, 반수를 넘은 학생이 2명 이상일 경우 후보 번호가 큰 학생이 당선 => 작은 번호부터 체크하기 때문에 이후에 반수를 넘은 다른 학생이 있다면 최종 당선 후보 변경)
						answer[0] = checkCnt; // 최종 선거 회차 담기
						answer[1] = i; // 당선 후보 번호 담기
					} else {
        				
						if (nomineeHm.get(i) < dropNum[1]) { // 현재 후보보다 득표 수가 적다면 탈락 후보 변경
							dropNum[0] = i;
							dropNum[1] = nomineeHm.get(i);
						}
					}
				}
			}
        	
			if (answer[0] == checkCnt) { // 최종 선거 회차가 담겼다면
				System.out.println(answer[0] + " " + answer[1]);
				return answer; // 선거 회차, 당선 번호 리턴
			}
        	
			dropHm.put(dropNum[0], 1); // 탈락한 후보의 번호 담기
		}
        
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] orders = {{2,3,4,0,1}, {1,4,3,2,0}, {4,1,0,2,3}, {3,2,1,4,0}, {0,3,2,1,4}}; // 4, 3
//		int[][] orders = {{2,1,0,3}, {3,2,0,1}, {3,0,2,1}, {2,3,0,1}}; // 1, 3
//		int[][] orders = {{2,1,0,3,4}, {4,2,0,1,3}, {3,0,4,2,1}, {2,4,3,0,1}, {4,1,3,2,0}}; // 4, 4 // {{2,1,3,4}, {4,2,1,3}, {3,4,2,1}, {2,4,3,1}, {4,1,3,2}} // 1차에 0 탈락 // {{2,3,4}, {4,2,3}, {3,4,2}, {2,4,3}, {4,3,2}} // 2차에 1 탈락 // {{2,4}, {4,2}, {4,2}, {2,4}, {4,2}} // 3차에 3 탈락 // 4차에 4 당선
		
		System.out.println(solution(orders));
	}
}

선거 회차 수가 증가할 때마다 탈락 또는 당선이 결정된다.

득표 수가 반수를 넘은 학생이 있다면 그 학생이 당선 후보가 되며, 반수를 넘은 학생이 2명 이상일 경우

번호가 더 뒤인 학생이 당선되는 룰을 따른다. 당선자가 결정되면 선거를 종료한다.

 

★이미 탈락한 후보가 아니라면, 표를 얻지 못했을 경우에도 이번 선거의 후보이며,

득표 수를 0으로 체크해야 한다는 점을 놓치면 안된다.★

 

프로그래머스 자비스앤빌런즈 2022 코딩테스트 선거 문제 풀이 Java