mondegreen

어떤 자료 구조를 써야할지 고민을 좀 했다. 최악의 경우 십만 개의 도시를 처리해야 하기 때문에 한 번의 반복문 순회로 끝내야 한다고 생각했다. 배열이나 리스트를 사용하기에는 recently used를 처리하기 위해 배열의 인덱스를 당겨줘야 하는 비효율이 있었다. 반대로 링크드리스트를 활용한다면 인덱슬 당기는 처리는 효율적이겠으나 해당 도시가 어느 인덱스에 있는지 처음부터 다 순회해봐야 하는 것이라 또 비효율이 발생했다. 해시맵과 큐를 사용하고자 했으나 큐도 마찬가지로 순서를 당기기 어려웠다. 이를 해결하기 위한 자료구조는 트리맵이라고 생각했고 키에 순서(인덱스)를 넣고 값에 도시이름을 넣어서 존재하는 경우 해당 키를 삭제하고 다시 인덱스와 도시를 map에 넣어줬다. 이를 활용해서 캐시가 다 찼을 경우 ..

문제를 읽고 먼저 높은 숫자를 줄여나가야 한다고 판단했다. 이를 구현하기 위해 우선순위 큐를 생각해보았지만 같은 작업량을 가진 여러 개의 작업을 n을 하나씩 줄여가며 처리해야 하니 조금 비효율적이라고 생각했다. 이를 보완하기 위해 해시맵을 떠올렸지만 그 안에서 정렬을 매번 수행하느니 트리맵을 사용하자는 결론에 다다랐다. 트리 맵은 자주 사용하지 않아서 메소드가 익숙하지 않아 이건 찾아가며 로직을 구현했다. 만약 남아있는 근무시간과 동일한 작업량을 가진 작업의 수를 비교했을 때 남아 있는 근무 시간(n)이 더 크거나 같다면 해당 작업량의 키를 삭제하고 하나 작은 작업량을 가진 작업 수에 더해주고 n 역시 그 수만큼 줄여준다. 반대로 n이 더 작다면 n 만큼 값을 줄여주고 하나 작은 작업량의 작업 수에 n..