[프로그래머스] Lv4 - 선입 선출 스케줄링

Published on 2018 Aug 25 16:44:25
Last Updated on 2018 Aug 26 11:43:59

프로그래머스 레벨4 - 선입 선출 스케줄링

간만에 엄청 고생해서 푼 문제였다.

백준같은 사이트는 시간 제한이 1초, 2초 이런식으로 걸려있지만.. 프로그래머스는 그렇지 않았기에 매우 신경써서 풀이를 찾아야 했다. 추측해보기로는 ‘모범답안 소요시간의 2~3배까지 허용’ 이런식으로 채점되는건 아닐까 싶었음.

개인적으로 이 문제에서 생각할 수 있는 풀이는 3개 정도였다.

1) 제일 무식하게 풀기

2) 비교적 최적화된 풀이

3) 모범답안이랑 거의 비슷하게 시간 걸리는 풀이

1번이면 몰라도, 2번 정도면 문제에서 요구하는 제한 사항을 꽉 채워서 돌려봐도 30ms 수준에서 답을 얻을 수 있었다.

그런데도 통과하지 못했고 며칠을 삽질했다. (효율성 케이스가 6개 있었는데 그 중 딱 1개만 통과할 수 있었다)

결국은 지인 분이 “파라메트릭 서치 써보는게 어때요?” 라고 하셔서 코드를 다 지우고 새로 짰다.

가까스로 모든 케이스를 통과할 수 있었고, ‘이정도면 됐지’라고 생각이 들 때는 충분히 더 좋은 케이스가 없을지 의심해봐야된다는 교훈을 얻은 시간이었다.

풀이

아래 코드는 Java 기준으로 3~6ms 정도의 시간이 걸린다.

풀이 코드