[프로그래머스] 64062번 - 징검다리 건너기 (Java)
⬛ 문제 https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr ⬛ 풀이 N은 최대 200,000이고 완전 탐색시 O(N^2)이므로 시간초과가 발생한다. 이전에 푼 무지의 먹방라이브 문제와 매우 비슷하다고 느꼈고 이 역시 우선순위큐를 활용하여 해결하였다. 프로그램 전체 로직은 다음과 같다. 1. 우선순위큐에 int[] {디딤돌 횟수, 인덱스}를 저장하고 디딤돌 횟수로 오름차순 정렬한다. 2. 거리를 저장하는 dist 배열을 선언하고 1로 초기화한다. (dist[i]는 stones[i]까지 필요한 거리, 마지막 도착지도 고려해야하므..
Algorithm/프로그래머스
2021. 9. 24.
