백준 17298 오큰수 자바스크립트

 

입력 크기에서 힌트를 얻는 편이다.

n이 1000000까지 들어온다는 것은 시간복잡도 O(n)으로 해결해야 1초로 끊을 수 있다는 뜻이다.

그러므로 배열을 선형으로 한번만 순회하면서 해결할 수 있는 방법을 생각해 보는 것이 좋겠다.

 

 

배열이 계속 내림차순 이라면 오큰수는 나올 수 없다. 반대로 배열이 오름차순이라면 맨 마지막 수를 제외한 모든 수는 자신의 앞에 수를 오큰수로 가질 것이다.

이를 토대로 생각해보면, 현재 내가 순회하는 숫자를 기준으로 내림 차순이 이어지면 오큰수는 알 수 없고,

나보다 큰 수가 나왔다면, 그 수는 여태 오큰수를 알 수 없던 모든 수의 오큰수 '후보'가 되는 것이다.

 

이제 해결법을 떠올릴 수 있다. 내림차순이라면 현재 순회하는 수의 정보를(값, 인덱스) 잠시 저장해두고, 오름차순일 때는 저장된 값들 중에서 오큰수의 조건을 만족하는 값들을 갱신해주면 되는 것이다.

여기서 쉽게 떠올릴 수 있는 구조가 바로 스택 이다. 근데 난 문제를 풀 때는 생각이 안났고 최소힙이 생각났다.

최소힙에서 조건에 맞을때마다 요소룰 빼면서 오큰수를 갱신해주면 된다.

스택도 이와 동일하게 생각하면 된다.

 

const readline = require('readline');
const rl = readline.createInterface({
	input:process.stdin,
	output:process.stdout
})

const input = [];
rl.on('line', (line)=>{
	input.push(line);
}).on('close', () =>{

	const n = Number(input[0]);
	const arr = input[1].split(' ').map(Number);
	const ans = Array(n).fill(0);
	const q = [];


	for(let i = 0; i < n; i++){
		const j = i+1;
		if(j === n)
			break;
		if(arr[j] <= arr[i]){
			q.push([i, arr[i]]);
		}
		else{
			ans[i] = arr[j];
			q.sort((a,b) => a[1] - b[1])
			while(q.length > 0){
				if(q[0][1] < arr[j]){
					ans[q[0][0]] = arr[j];
					q.shift();
				}
				else
					break;
			}

		}
	}

	for(let i = 0; i < ans.length; i++){
		if(ans[i] === 0)
			ans[i] = -1;
	}


	console.log(ans.join(' '));

})

 

이 코드는 sort연산에서 O(nlogn)이 나오기 때문에 시간초과가 뜬다.

그래서 우선순위 큐를 직접 구현하면 통과가 된다. (코드가 길어서 올리진 않았다) 물론 오래 걸린다. 거의 꼴지 수준이다. 요소를 뺄 때 log(n)이 걸려서 그럴 것이다. 아마 몇없는 우선순위 큐로 통과한 사람중 하나인 것 같다. 그러니까 O(1)의 스택을 사용하도록 하자.