해당 글은 항해99 클럽 코딩테스트 스터디에서 진행된 20일차(20241116) 비기너 문제에 대한
TIL(Today I Learned) 내용입니다.
문제 출처) https://www.acmicpc.net/problem/2075
문제해결에 활용한 핵심포인트!
이 문제에서 주목해야할 부분은 다음과 같다.
조건1) 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다
조건2) 입력으로 주어지는 것은 N개의 줄에는 각 줄마다 N개의 수, 출력으로 원하는 것은 "N번째 큰 수"
문제 상황에서 활용하기에 적합한 구조에 대해 고려하기
-
조건1 에 의해 이미 정렬이 되어있는 상태의 구조를 활용하면 좋을 것이라고 판단
-> PriorityQueue를 통해 최소힙을 구현가능하다.
-> 특히, PriorityQueue는 요소(element)를 넣으면 자동으로 정렬해주는 기능이 있다! -
조건2 에 의해 어떤 집합/배열 구조의 길이를 N으로 제한하면 출력에 유리할 것이라고 판단 가능
-> PriorityQueue에 요소를 넣되, 결국 원하는 것은 N번째 큰 수 이므로, 그 길이가 N을 초과하면 제일 위의 것(제일 작은 수)을 제거하는 로직을 추가한다.
-> 이 때, size()와 poll() 함수를 활용하면 편하다.
풀이방향
- 풀이방향1) 처음엔 단순히 가변배열인 arraylist를 활용해서 단순히 넣고,
Collections.sort() 함수를 활용하여 정렬한 후,
인덱스(N-1)을 이용해서 뽑으면 된다고 생각했다.
-> 시간 초과!!!!!!
- 풀이방향2) 위에 설명한 것처럼, 조건1, 조건2를 고려하여 코드를 짜면 풀이방향1을 간소화할 수 있다!
한걸음 한걸음