[Baekjoon] 13281_Look for the Winner!

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

---

< Look for the Winner! >

 

문제 풀이 

 

우승자가 결정 나는 조건

1) 투표수가 1일 때

2) 두 번째로 큰 투표수 + 남은 투표수 < 가장 큰 투표수

3) 후보자 한 명이 절반 넘는 표를 가졌을 때

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;

public class _13281_ { // Look for the Winner!

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
        
		int n = -1;
        
		HashMap<Character, Integer> map = new HashMap<>();
		String result = null;
		
		while ((n = Integer.parseInt(bf.readLine())) != 0) {
			st = new StringTokenizer(bf.readLine());
			int max = -1, idx = -1;
            
			for (int i = 0; i < n; i++) {
				char x = st.nextToken().charAt(0);
                
				if (map.containsKey(x)) {
					map.replace(x, map.get(x) + 1);
				} else {
					map.put(x, 1);
				}
				if (max < map.get(x)) {
					max = map.get(x);
					result = x + "";
				}
                
				if (n == 1) {
					idx = 1;
					break;
				}
				List<Integer> list = new ArrayList<>(map.values());
				Collections.sort(list, Collections.reverseOrder());
                
				if ((list.size() > 1 && list.get(0) > list.get(1) + (n - (i + 1)))
						|| (list.size() == 1 && i == n / 2)) {
					idx = i + 1;
					break;
				}
			}
			if (idx == -1) {
				bw.write("TIE\n");
			} else {
				bw.write(result + " " + idx + "\n");
			}
			map.clear();
		}
		bw.flush();
	}
}

변수)
n : 투표수
map : HashMap <후보자, 투표수>
result : 우승자
max, idx : 가장 많은 투표수, 우승자가 결정될 때의 투표수
x : 후보자
list : HashMap values -> ArrayList

 

n이 0이 아닐 때까지 다음 과정을 반복한다.

1) n만큼 투표 결과를 입력받아 HashMap에 저장하며 최다 득표 수와 최다 득표 후보자를 저장한다.

2) n이 1이라면 입력받은 후보자가 정답이므로 종료한다.

3) HashMap의 value 값을 ArrayList로 변환 후 내림차순으로 정렬한다.

4) ( 두 번째로 큰 투표수 + 남은 투표수 < 가장 큰 투표수 ) 또는 ( 후보자 한 명이 절반 넘는 표를 가졌을 때 ) 이 경우 우승자가 확정되므로 idx 값을 업데이트한 후 종료한다.

5) idx가 -1이라면 TIE를 출력하고 -1이 아니라면 result와 idx를 출력한다.

---

---