[스택큐] 프린터 - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/42587

코딩테스트 연습 - 프린터

우선 문제의 내용을 그대로 훝어보면 다음과 같습니다

 

4개의 문서에 대한 중요도가 다음과 같이 있을 때 다음과 같이 구성된다.

 

현재 바라보고 있는 0번째 문서는 중요도가 2, 하지만 뒤에 3이라는 중요도가 더 큰 문서가 있으므로 맨 뒤로 옮겨줍니다

 

그 다음으로 문서를 바라봅니다

마찬가지로 중요도가 높지 않으므로 맨 뒤로 옮겨줍니다

 

 

이 중 가장 중요도가 큰 녀석이 남으므로

이 녀석을 빼서 정답 리스트에 넣어줍니다

이렇게 순차적으로 빼서 넣어주는 방식으로 하면

[2, 3, 0, 1] 순으로 정답 리스트에 들어가게 됩니다

이 중 location이 2인 녀셕의 경우를 뽑으라고 하면

[2, 3, 0, 1]중 2에 해당하는 인덱스를 뽑아주면 되고 X번째는 +1을 해주면 되니 이렇게 풀면 정답이 나옵니다

 

def solution(priorities, location):  
	documents = list(range(len(priorities)))
	i = 0; lists = [];
	## 문서 삽입 -> O(n^2) -> 최악의 경우
	# [1, 2, 3, 4, 5]를 생각해보자 
	while True : 
		## 가장 중요도가 높은 것을 찾은 경우
		if priorities[i] == max(priorities) : 
			doc = documents.pop(0); pri = priorities.pop(0);
			lists.append(doc)
			## 모든 문서 정보를 찾은 경우
			if priorities == [] : break
		else : 
			doc = documents.pop(0)
			documents.append(doc)
			pri = priorities.pop(0)
			priorities.append(pri)

	answer = lists.index(location)+1
	return answer

Level 2의 문제라 그런가 데이터가 크지 않아 짧은 시간 내에 문제를 풀긴 했지만

실제로 pop(), append() 연산자의 cost가 상당히 큰 편

 

또한

[1, 2, 3, 4, 5]

처럼 오름차순인 경우

최악의 경우 O(n^2)이다.