글 읽기 - 정렬 순서 질문

(追記) (追記ここまで)

정렬 순서 질문

11652번 - 카드

zeus20240228 1년 전 1

첫 번째 코드는 key가 작은순으로 정렬을 하고 Value가 큰 순서대로 정렬
두 번째 코드는 Value가 큰 순서대로 정렬을 하고 key가 작은순서로 정렬

왜 첫 번째 코드는 통과하는데 두 번째 코드는 틀릴까요?

import java.util.*;
import java.io.*;
public class Main {
 public static void main(String[] args) throws IOException{
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 int n = Integer.parseInt(br.readLine());
 Map<Long, Integer> map = new HashMap<>();
 while (n-->0){
 long input = Long.parseLong(br.readLine());
 map.put(input, map.getOrDefault(input, 0) + 1);
 }
 System.out.println( map.entrySet().stream()
 .sorted((e1, e2) -> e1.getKey().compareTo(e2.getKey()))
 .sorted((e1, e2) -> -e1.getValue().compareTo(e2.getValue()))
 .findFirst().get().getKey());
 }
}
----------------------------------------------------------------------------------------
import java.util.*;
import java.io.*;
public class Main {
 public static void main(String[] args) throws IOException{
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 int n = Integer.parseInt(br.readLine());
 Map<Long, Integer> map = new HashMap<>();
 while (n-->0){
 long input = Long.parseLong(br.readLine());
 map.put(input, map.getOrDefault(input, 0) + 1);
 }
 System.out.println( map.entrySet().stream()
 .sorted((e1, e2) -> -e1.getValue().compareTo(e2.getValue()))
 .sorted((e1, e2) -> e1.getKey().compareTo(e2.getKey())).findFirst().get().getKey());
 }
}

unta 1년 전 1

정렬 우선순위가 달라지기 때문입니다.

전자의 경우 Value 기준으로 내림차순, Value가 같은 경우 Key가 작은 게 먼저 옵니다.

후자의 경우 Key 기준으로 오름차순, Key가 같은 경우 Value가 큰 게 먼저 옵니다.

즉, 두 정렬 방법의 결과가 다를 수 있습니다.

unta 1년 전 1

추가로 정렬을 두 번 이상 적용하여 정렬의 우선순위를 정하는 것은 정렬이 안정적(stable)인 경우에만 사용할 수 있습니다.

정렬이 안정적이지 않을 경우(unstable) 아래 풀이와 같이 한 번의 정렬로 정렬 우선순위를 구현할 수 있습니다.
[풀이] https://www.acmicpc.net/source...

안정/불안정 정렬은 아래 글을 읽어보시면 좋을 것 같습니다.
[Stable Sort, Unstable Sort] https://mindock.github.io/algo...

감사합니다.

zeus20240228 1년 전 0

이 코드는 뭐가 문제일까요?

한번의 정렬에서 value가 같으면 key가 작은 순서대로
value가 다르면 큰 순서대로 정렬 하고 있습니다!

import java.util.*;
public class Main {
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 int n = sc.nextInt();
 Map<Long, Integer> map = new HashMap<>();
 for (int i = 0; i < n; i++) {
 long input = sc.nextLong();
 map.put(input, map.getOrDefault(input, 0) + 1);
 }
 ArrayList<Map.Entry<Long, Integer>> list = new ArrayList<>(map.entrySet());
 Collections.sort(list, new Comparator<Map.Entry<Long, Integer>>() {
 @Override
 public int compare(Map.Entry<Long, Integer> o1, Map.Entry<Long, Integer> o2) {
 if(o1.getValue() > o2.getValue()) return -1;
 else if(o1.getValue() == o2.getValue()){
 if(o1.getKey() > o2.getKey()) return 1;
 else if(o1.getKey() == o2.getKey()) return 0;
 else return -1;
 }
 return 1;
 }
 });
 System.out.println(list.get(0).getKey());
 }
}