https://www.acmicpc.net/problem/2910
문제
위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다.
창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 N개로 이루어진 수열이고, 숫자는 모두 C보다 작거나 같다. 창영이는 이 숫자를 자주 등장하는 빈도순대로 정렬하려고 한다.
만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.
이렇게 정렬하는 방법을 빈도 정렬이라고 한다.
수열이 주어졌을 때, 빈도 정렬을 하는 프로그램을 작성하시오.
입력
첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000)
둘째 줄에 메시지 수열이 주어진다.
출력
첫째 줄에 입력으로 주어진 수열을 빈도 정렬한 다음 출력한다.
문제 해석
문제를 처음 보았을 때, ArrayList로 풀어야하나 생각했다. 하지만 ArrayList는 값(key) 에 따른 빈도(value)를 저장할 수 없기 때문에, HashMap을 생각해야 했다.
만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.
이 부분을 위해, 빈도수가 같다면 먼저 등장한 숫자가 앞으로 나오도록 해야한다.
따라서 일반 HashMap이 아닌, 순서를 저장할 수 있는 LinkedHashMap 을 사용할 것이다.
전체적인 흐름은
입력 N 과 C를 처음에 입력받는다.
<Integer, Integer>를 갖는 LinkedHashMap인 map을 생성하여 문자열(수열)을 StringTokenizer 로 끊어서 문자열을 입력받도록 한다.
문자열로 입력을 받았기 때문에 문자열을 정수로 변환해주고, 그 때의 값을 map에 집어 넣을 때 기존 값(Key)이 있는지 없는지 검사를 하고 만약 있다면 Value에 + 1 하며 저장하고, 존재하지 않는다면 값을 1로 추가한다.
map에 저장된 Key를 모두 ArrayList에 저장하고, Value 값을 기준으로 내림차순 해준다. (빈도가 많을수록 앞에 오기 때문이다)
Collections.sort(list, comparator);의 형태로 사용한다.
comparable은 나(this)를 기준으로 comapreTo 메소드에 상대를 넣어 비교를 했다면,
comparator는 비교대상 2개를 가지고 판단을 한다.
int compare(T o1, T o2) 로 두 객체의 특정 값을 연산해서 음수가 나오면, o1의 객체가 작다고 판단, 양수가 나오면 o2의 객체가 작다고 판단한다.
정렬된 리스트를 Iterator 를 통해 StringBuilder sb 에 저장하고 출력한다.
여기서
Iterator는 컬렉션 프레임워크(Collection Framework)에서 값을 가져오거나 삭제할 때 사용하는데 , 컬렉션 프레임워크는 List, Set, Map, Queue 등을 말한다.
- 해쉬맵에 키와 빈도수 저장(이 때, 기존 값과 비교)
- 해쉬맵에 저장된 모든 키를 리스트에 저장
- 리스트안에 저장된 키들을 빈도수에 따라 내림차순 정렬
- 키 출력
풀이
import java.io.*;
import java.util.*;
public class prob2910 {
public static void main(String[] args) throws IOException {
//백준 풀때는 Scanner 보단 BufferedReader 사용
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력을 위한 StringBuilder
StringBuilder sb = new StringBuilder();
//문자열 끊어서 받기 위한 StringTokenizer
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
//LinkedHashMap 생성
HashMap<Integer, Integer> map = new LinkedHashMap<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
//문자열 숫자 변환
int num = Integer.parseInt(st.nextToken());
// 해시맵 안에 num이 있으면 기존 값에 +1을 해주어 저장
// 존재하지 않으면 새로 값을 추가
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
// 키를 모두 ArrayList에 저장
List<Integer> list = new ArrayList<>(map.keySet());
// ArrayList에 저장된 값 기준 내림차순으로 정렬
//비교를 위해 Collections 클래스의 sort 메소드 이용
Collections.sort(list, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
//list.get(b) 와 list.get(a)의 위치가 바뀌면 오름차순이 됨
return Integer.compare(map.get(b), map.get(a));
}
});
//Iterator로 순회하여 출력
Iterator<Integer> it = list.iterator();
//Iterator it 에 다음 값이 없을때까지 반복하여 sb에 저장
while (it.hasNext()) {
Integer element = it.next();
for (int i = 0; i < map.get(element); i++) {
sb.append(element + " ");
}
}
System.out.println(sb);
}
}