MergeSort
-
백준 2075 N번째 큰 수 - [알고리즘] [kotlin]알고리즘/백준 2023. 8. 8. 18:10
문제 내용 문제 분석 1. n*n 크기의 표가 있다. 2. n은 최대 1500으로 표의 최대 크기는 2250000 (2백만 이상)이다. 3. 각 수는 -10억 ~ 10억 의 범위를 갖는다. 4. 각 수는 바로 위에 배치된 수보다 크다. 5. n번째 큰 수를 찾아 출력한다. 아이디어 1. N번째 큰 수를 찾아야 하기 때문에 정렬으로 접근한다. 2. 모든 열은 정렬이 되어있는 상태이다. 3. mergeSort는 각 수를 쪼개서 정렬하며 올라오는 방식으로, 현 상태는 mergeSort의 중간단계로 볼 수 있다. 4. 각 열을 sort되어있다고 보고 mergeSort를 중간단계부터 구현한다. 5. n번째 index를 출력한다. 1. pq를 사용한다. 2. 값이 작을수록 중요도가 높게 설정한다. 3. pq의 크기..