[ 백준2910 - 빈도 정렬- Java ]

문제 분석

정렬

시간 복잡도

정렬을 이용하면 NlogN이 됩니다!

구현

1. ZippedNum 클래스 정의

class ZippedNum{
        int cnt; // 숫자의 등장 횟수
        int num; // 배열 내부의 숫자
        int firstCome; // 숫자의 첫 등장 시점 (배열에서의 인덱스)
}

만약 {1,1,1,1,2,2,2,2,3,3,3} 을 ZippedNum으로 표현한다면

{
	ZippedNum(cnt : 3, num : 1, firstCome : 0),
	ZippedNum(cnt : 4, num : 2, firstCome : 4),
	ZippedNum(cnt : 3, num : 3, firstCome : 7)
}

로 표현 할 수 있다.

2. { Key : C(배열 내부의 숫자), Value : ZippedNum } 를 가지는 HashMap 정의

ZippedNum을 만들어주기 위해서 HashMap을 만들고

for(int i = 0 ; i < arr.length; i++){
	zippedNumbers.putIfAbsent(arr[i], new ZippedNum(0,arr[i],i)); 
    	// 숫자가 존재하지 않으면 새로운 객체 생성하고 
        // 첫 등장이기 때문에 현재의 i값을 ZippedNum의 firstCome으로 지정
        
	ZippedNum zippedNum = zippedNumbers.get(arr[i]);
	zippedNum.cnt++;       
	zippedNumbers.put(arr[i], zippedNum);
    	// 이미 존재하는 숫자라면 등장 횟수만 1을 더한다.
}

다음과 같이 HashMap에 ZippedNum을 넣는다.

3. ZippedNum 클래스에 정의 되어 있는 cnt, firstCome을 이용해서 HashMap의 Value들을 정렬

// HashMap의 value들을 정렬을 위해서 List로 변환
List<ZippedNum> zippedNumbersList = new ArrayList<>(zippedNumbers.values()); 

zippedNumbersList.sort(new Comparator<ZippedNum>() {
	@Override
	public int compare(ZippedNum o1, ZippedNum o2) {
    		
    		if (o1.cnt == o2.cnt) {
	        	//만약, 등장 횟수가 같다면 등장 횟수가 빠른 것을 앞으로
			return Integer.compare(o1.firstCome, o2.firstCome);
		} else {
        		//만약, 등장 횟수가 많은 순서대로
			return -Integer.compare(o1.cnt, o2.cnt);
		}
	}
});

4. 정렬된 ZippedNum 를 담고 있는 리스트를 순회하며 정답 출력

        for (ZippedNum zippedNum : zippedNumbersList) {
            for(int i = 0 ; i < zippedNum.cnt; i++){
                System.out.print(zippedNum.num + " ");
            }
        }

헤맸던 부분

"만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다."

이 부분을 만족시키도록 코드를 작성하는 것이 생각보다 어려웠다...😅

등장 횟수를 계산해 나갈때 만약, 이전에 등장하지 않고 처음 등장 하는 수라면 그때의 idx값을 같이 저장 하는 방식으로 해결 할 수 있었다.

이 말이 이해되지 않는다면, 위의 구현의 2번 항목을 다시 한번 살펴보면 좋을 것 같다..

다른 사람들의 접근 방법

LinkedHashMap + Stable Sort의 성질 활용

Q1) Java Linked HashMap 과 LinkedHashMap의 차이를 설명 할 수 있으신가요?
A1) 정답

Q2) Java의 sorting은 Stable Sort일까요?
A2) 정답

2가지 질문에 대한 답을 모르시겠다면, 위의 위의 2개의 궁금증을 해소하신 후에 풀이를 보시면 큰 도움이 될 것 같습니다~~!!

정답 코드

얻은 것

• stable sort에 대한 복습
• Java의 LinkedHashMap

전체 코드 [ 내 코드 ]

https://github.com/eden6187/algorithm-study/blob/master/src/baekjoon/boj2910/Main.java

느낀점

Arrays.sort() / Collections.sort()를 쓸 줄 안다고 정렬을 했다고 생각하는 것은 잘못된 생각입니다...

참조

문제 출처
LinkedHashMap 출처
Java Sorting 출처