[프로그래머스] 뒤에 있는 큰 수 찾기

		for (int i = 0; i < numbers.length; i++) {
			for (int j = i + 1; j < numbers.length; j++) {
				if (numbers[i] < numbers[j]) {
					numbers[i] = numbers[j];
					break;
				}
			}
		}

처음에는 위와 같이 이중 for문을 사용하여 풀었다.

하지만 시간복잡도는 O(N^2) (N = 1,000,000) 로 당연히 시간 초과가 났다.

 

아래 코드와 같이 우선 순위 큐를 사용하여, 문제를 풀 수 있었다.

유사한 문제로는 백준 알고리즘의 [오큰수] 라는 문제가 있다. 

 

다른 블로그의 풀이를 참고하였고, 예전에 백준에서 푼 기억이 있는데 도저히 방법이 생각 안났다.

import java.util.PriorityQueue;

class Solution {
	public int[] solution(int[] numbers) {
		
		// 작은 숫자부터 큐 우선순위로 넣는다
		PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);

		for (int i = 0; i < numbers.length; i++) {
			int v = numbers[i];

			// 큐가 비어있지 않고, 큐에서 꺼난 값이 현재 인덱스의 값보다 작으면 실행
			// 큐에 들어있다는 것은 앞순서에서 넣었고 아직 정해지지 않은 것
			// 현재 인덱스의 값과 현재 큐에 들어있는 값을 비교한다
			while (!q.isEmpty() && q.peek()[1] < v) {
				// Queue에 넣은 numbers의 값들은 이미 사용했기 때문에
				// 값을 변경해도 상관없다
				numbers[q.poll()[0]] = v;
			}
			
			// 큐에 넣는다
			q.add(new int[] { i, v });
		}

		// 아직도 큐에 남아있다는 것은 오른쪽에 자기보다 큰 수가 없기 때문에
		// -1로 값 지정
		while (!q.isEmpty()) {
			numbers[q.poll()[0]] = -1;
		}

		return numbers;
	}
}

 

 

유사 문제

https://www.acmicpc.net/problem/17298

17298번: 오큰수