[구름톤 챌린지 5일차] 이진수 정렬

이번 문제는 지금까지 풀어왔던 구름톤 챌린지 문제 중에서 가장 난이도가 높았다고 느꼈다. 문제를 요약하자면 N개의 숫자들을 입력 받고 그 숫자들을 2진수로 변환 했을때 1이 가장 많은 수부터 내림차순으로 정렬하고, 1의 개수가 같은 숫자가 있을 경우 10진수 값으로 내림차순 하는 문제이다.

이 문제를 풀기 위해 우선 2진수로 변환했을때 1의 갯수 별로 10진수 숫자들을 저장한다. 이때 사용한 자료구조는 TreeMap이다. key값은(1의 개수는) 1부터 20까지 있고 각 key에 해당하는 10진수들을 value인 ArrayList에 담는다.

그 다음으로 TreeMap을 역순으로 정렬한다.(1->을 20->1로)

그리고 TreeMap에서 key마다 저장되어 있는 ArrayList를 내림차순으로 정렬한 후, 저장된 숫자들을 순서대로 꺼내어 resultList에 추가한다.

마지막으로 resultList에서 K-1 번째 값을 읽어 출력한다.

시간복잡도는 TreeMap에 값을 입력할때마다 O(log N)의 시간이 걸려서 N개의 값을 저장하는데 O(N log N)의 시간이 걸리고,
TreeMap을 역순으로 정렬하는데 최대 20개의 key를 정렬하므로 O(1)의 시간이 걸린다고 본다.
ArrayList의 수를 정렬하는데 총 O(N log N)의 시간이 걸린다.
ArrayList의 값들을 순서대로 저장하고 마지막으로 결과값을 출력하는데 O(n)의 시간이 걸리므로 이 문제 풀이에서 계산된 총 시간복잡도는 O(N log N)이라고 생각한다.

부족한 지식으로 인해 계산에 오류가 있을 수 있다. 참고해서 봐주시면 좋을거 같다.

 

배운점

TreeMap에 대해서 알게 되었고 Collections.sort()를 통해 list를 역순으로 정렬하는 방법을 알았다. Integer.bitCount()를 통해 2진수로 변환했을때 1의 개수를 구하는 법을 알았다.

느낀점

chatGPT3.5를 활용하여 궁금했던 부분을 쉽게 해결할 수 있었다. 가령 자바로 코딩테스트를 준비한 지 오래지 않았는데 몰랐던 메소드들을 활용하여 문제를 생각했던 대로 풀 수 있었다. 이런 점에서 볼 때 chatGPT가 코딩하는데 큰 도움이 되는거 같다.

어려운 점

아직 자바로 코딩테스트를 준비한 지 얼마 되지 않아 여전히 생각을 코드로 구현하는데 시간이 많이 소요된다는 점이 아쉽다.

 

p.s: Comparable 인터페이스를 상속 받아서 comparTo()를 구현해준다면 간단하게 풀 수 있다.