다 까먹어 버린 알고리즘..! 1일 1코테로 코테 습관을 쌓는 챌린지가 있어서 도전해봤다.
1주차는 매일 클리어 할 수 있었다.
문제별로 제한시간이 있는데 난이도에 따라서 30분에서 1시간정도 푸는걸 제안한다.
내가 참가한 난이도는 미들러로 실버 골드 사이에 문제가 나온다고 한다.
다만 첫째주라 그런지 대부분 실버쯤 되는 난이도였다!
물론... 오랜만에 하니까 가물가물해서 옆에 있는 힌트를 열고 봤다 😭
매일 월요일마다는, 코테 관련해서 강의가 있는데 해당과 같은 방법을 추천해주셨다.
- 문제의 입력과 , 출력을 바탕으로 로직을 작성한다.
- 이후 코딩하면 결과를 해당 언어로 입력하는 것 뿐이다.
문제 : 정수 배열 nums과 정수가 주어지면 가장 빈번한 요소를k 반환합니다 . **어떤 순서** 로든 답을 반환할 수 있습니다.
//입력 : nums - 점수배열, int k 가장 빈번한 순위 k번째 까지?
//로직 : 숫자가 나올 때 마다 카운팅일 하고
// 최종적으로 그 카운트가 높은 순서대로 K번째까지 출력
// 답은 유일무이하다 ! -> K번째에 해당하는 빈번도를 숫자가 중복될일은 없다-!
// 어떤 방법을 사용하든 HashMap -> 숫자 카운팅 put()
// 연산이 O(1) -> O(n) 의 시간복잡도
// 1. 정렬
// sort() O(N log N)
// 순서대로 선택 O(K)
// O(N log N)
// 2. 우선순위 큐 (min - heap)
// 반복문을 통해서 PriorittyQueue add -> O(log K) -> N
// O(N log k)
// 결과 반환은 O(K log K)
//그럼 항상 2번이 좋은가? 그건 또 아니다. 구현 난이도에 따라 다를 수 있다.
//출력 : int 리스트 형태로 반환 5일간 해당과 같은 방법으로 진행하였다. 사실 O(N) 같은 시간까지는 파악하기 힘들었지만, 정렬 출력 정리하고, 로직을 정리하고 나니 코드를 치는데 명확해진 장점이 있었다.