[CodingTest] 프로그래머스 Programmers 스택&큐 level 2 프린터

문제

나의 풀이

예제에 대해서는 값이 잘 나오는데 timelimit으로 통과가 되지 않는다 .. ㅠ 풀이와 생각 자체는 맞는 것 같은데 시간복잡도 때문인 것 같아서 어떻게 고쳐야할지 고민이다 .. 테스트 케이스가 두개 밖에 없어서 무척 답답하다 ㅠㅠㅠ 

우선 위 풀이는,

1) 우선순위가 높은 순서로 정렬하고 tmp배열에 넣는다. 

2) priorities 리스트의 인덱스를 indexs 리스트로 표현한다.

3) priorities가 tmp이면, 즉, 우선순위가 높은 순대로 내림차순한 것과 동일하다면, 제대로 정렬되었음을 확인하고 while문을 빠져나온다.

4) 첫번째 원소보다 큰 원소가 priorities에 존재한다면, 아직 정렬이 되지 않았다고 판단하고, index 배열과 priorities배열에 각각 pop후 push 해준다.

5) location의 인덱스를 indexs 리스트에서 찾아 리턴한다.

 

타임리밋 해결을 위한 시도 #1

타임리밋을 해결하기 위해 코드를 고쳐보던 중, 잘못된 점을 발견하였다.

priorities = [1, 2, 3, 8,1]

location = 0 

을 테스트해보았을 때, 

위 예시를 실행시킬 경우 처음 짠 코드는 

[8,3,2,1,1]로 정렬되지 못하므로 무한 루프를 돈다.

타임리밋해결을 위한 시도 후의 본 예시의 값은 다음과 같다. (예시를 찾는 데만도 엄청 오래걸렸다 ㅠ 테스트 케이스가 다양했으면 좋겠다..) 

예시에 대한 출력값

[2,3,8,1,1]->[3,8,1,1,2]->[8,1,1,2,3]이 되어 최종적으로 [8,1,1,2,3]으로 정렬되며, 3을 반환한다.

여기까지 완벽한 풀이라고 생각했는데, 다른 분의 코드를 실행했을 때, 위의 예시에 대해 값이 5가 나왔다 ㅠ정말 이해할 수 없다 ㅠㅠㅠ

 

 

나는 바보다... 하나가 출력된 이후에 대해서 생각하지 않았다... 그냥 저 순서대로 출력되는줄... 한번 출력 후에도 다음 출력을 위해서 다시 정렬되는 것이었는데 그 경우는 생각하지 못했다 ㅋㅋㅋ 하하ㅏㅏ 

 

기능개발이랑 합해서 이틀 내내 푼 것 같은데 이제서야 문제점을 발견했다ㅋㅋ 코딩 실력에 현타가 오고 ... 사실 너무 슬프다 ... ㅋㅋ ㅋㅋㅋ 내가 코테 준비를 할 수 있을까..?... 이틀 내내 풀어도 못푸는걸 ...