https://programmers.co.kr/learn/courses/30/lessons/64063
-
flow
1.) 효율성 테스트가 있고 간단한 태스크 처럼 보여 최적화가 상당히 어려울 것이라 예상하긴 했지만 일단 가장 간단하게 먼저 풀어보았다.
단순히 index 순서대로 1~k 까지 element 를 갖는 리스트(room)를 초기화 선언 해주고, 원하는 방번호가 들어오면 같은 index 의 값을 확인하고 값이 index 와 같다면 (실제로 index+1 = room[index]) answer에 값을 추가하고 room[index] 값을 1 더한 상태로 만들어준다. 그리고 index와 값이 같지 않은 경우 index += 1 씩 해주면서 value가 index랑 같은 위치를 찾아준다. (value 전부 최종 index+1 값 맞춰줌)
2.) 이렇게 했더니 정확도는 맞지만 당연히 효율성에서 전부 시간초과가 떴다. 그래서 다음 방안으로 생각한 것이 이분탐색이었다.. 뭔가 원하는 room_number에서 index와 값이 맞지 않을때 (즉 이미 선점된 경우) 다음 방을 찾을 때 min, max, mid 를 이용해 찾으면 더 효율적이지 않을까 단순히 생각했었다. 근데 형태를 바꿔가면서 해봐도 효율성이 전부 꽝이었다. (생각해보면 대부분 다음 index가 초기 index 즉, min 값과 가까이 있을텐데 오히려 이분탐색이 더 느릴 수 있는 경우이다. (시간복잡도가 빨라도 앞에 계수가 차이나는 느낌?)
3.) 이분탐색도 버리고, 찾으면 room[index] 값을 늘려주는게 아니라 0값을 넣어 선점했다고 표시를 하는 방식으로 해봐도 안되다가 room[index] 값 갱신 방식을 트리의 부모 자식 관계처럼 만들면 되지 않을까 생각했다. 즉, index 와 값이 같아질 때까지 room[index]를 참조해 나아가고 최종 index+1 값으로 갱신하는 방법이었다. 어떻게 보면 특정 index에서 last 값을 기억하고 있다고 봐도 될 것 같다. 그래서 탐색시간이 줄어 될거라 생각했지만 왠걸 효율성 테스트가 계속 문제가 났다.
4.) 멘탈이 너덜해질 찰나 떠오른 게 애초에 k값과 room_number length 값이 많이 차이가 나는 점에서 뭔가 손해를 보고 있다고 느꼈다. 그래서 처음에 k값만큼 선언 초기화 해주지 말고 root_number 순서대로 새로 생성하는? 그런 느낌으로 만들자는 생각이 들었다. hash map 같은 것을 생각하다가 python의 dictionary 를 이용하기로 다짐했다. (hashmap이나 dict 이나..)
이전 알고리즘 틀은 유지한 채 dict 을 이용한 결과 몇몇 효율성 테스트들이 통과되었다! 근데 기뻐할 시간 없이 대체 그럼 아직도 실패하는 경우는 어떻게 최적화하지라는 생각이 들었다.. 독창적인 생각은 안들고 최대한 반복문을 줄여보자 하면서 바꿔보아도 한계가 있어 결국 다른 reference를 찾아보게 되었다. 그런데 알고리즘 줄기가 거의 비슷한데 내가 while 문 안에서 반복을 돌린 것을 재귀함수를 통해 만들어준 코드가 통과하는 것을 보았다. 즉시 변경 결과 눈에 띄게 성능이 개선 되었고, 코드를 통과시켜 다른 분들의 코드를 더 볼 수 있었다.
5.) 결과적으로 참고한 코드에서 recursion limit을 거는데 다른 깔끔한 코드를 보다 보니 기존 재귀함수에서 값을 갱신해주는 과정이 생각보다 비효율적이었다는 느낌이 들었다. 예를들어 길이가 엄청 긴데 room_number = [1 1 1 1 1 1 ...] 이란 요청을 생각해보자. 그럼 재귀함수에서는 죽어라 재귀돌리면서 일일이 함수콜하고 최종 값 갱신을 해주게 된다. 좀 더 깔끔해 보이는 코드에서는 이런 점을 visit list를 만들어 최종 index를 찾았을 때, 한꺼번에 값을 갱신해주는 방식을 통해 개선한 것을 보여주었다. 이번 알고리즘 문제는 꽤나 얻은 경험이 많은 것 같은 느낌이다. -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level4/A64063.py -
reference
https://post.naver.com/viewer/postView.nhn?volumeNo=27889711&memberNo=33264526
