해설 글이 아닙니다.
제가 놓쳤던 부분, 기억할 팁 등을 정리합니다.
- 신규 아이디 추천 - LEVEL 1
어떤 배열에서 특정 원소들을 여러번 제거해야하는 경우에는
다른 배열로 복사하는 방식으로 O(N) 처리할 수 있음.
- 메뉴 리뉴얼 - LEVEL 2
- 순위 검색 - LEVEL 2
언어, 직군, 경력, 소울푸드가 각각 4, 3, 3, 3 가지로 나뉘므로
이를 4차원배열로 저장할 수도 있겠지만
각 속성들의 index를 idx1, idx2, idx3, idx4로 나타낸다고 하면,
일차원 배열을 통해 idx127 + idx29 + idx3*3 + idx4 이런식으로 더 간편하게 저장할 수 있다.
속도 면에서도 참조가 지속적으로 일어나면 느려지므로, 훨씬 좋은 방법인듯 하다.
- 합승 택시 요금 - LEVEL 3
솔직히 알고리즘이 다른 문제들에 비해서 덜 쓰여서 그렇지
응용력 측정하는 측면에서는 엄청 쉬웠다.
- 광고 삽입 - LEVEL 3
play_time의 최대 second가 360000이 아니었다면, LEVEL 4 였을 문제.
그냥 각 초마다 몇명의 시청자가 보고 있는지 O(N)에 기록한 후
누적합이나 스위핑으로 모든 second를 순회하며 최대 누적시청시간을 기록해서 반환하면 되는 문제.
만약 second가 매우 커졌다면, 다음의 사실을 추론해야함
각 시청자가 시청을 시작하거나 끝내는 시간을 event라고 하면,
공익광고의 시작시간은 event의 원소이다.
왜냐하면, event가 오른쪽이나 왼쪽으로 조금씩 움직여도 변화가 없는 부분중에 우리가 찾는 답이 있다고 했을 때,
왼쪽으로 조금씩 움직여도 시청자의 누적시간에는 변화가 없으므로
우리는 가장 왼쪽에 있는 답을 반환해야 하므로 우리가 찾는 답이 아님이 증명된다.
즉, 각 event 마다 공익광고가 시작할 지, 끝날 지를 모두 고려해주어야 한다.
구현할 때 기억해야 할 것은 움직일 때 마다
다음 공익광고가 끝나는 시간이 되는 event가 현재 공익광고가 끝나는 시간과의 거리에 가까운지,
다음 공익광고가 시작하는 시간이 되는 event가 현재 공익광고가 시작하는 시간과의 거리에 가까운지
따져가면서 더 가까운 event마다 순회를 해야한다는 것.
- 카드 짝 맞추기 - LEVEL 3
모든 상황을 비트마스킹으로 해결하려고 했으나
비트마스킹은 0과 1로만 이루어져 있기에, 두 가지 경우의 상태만 기록할 수 있다.
때문에 앞면의 카드인지, 뒷면의 카드인지, 찾은 카드인지를 모두 기록하기에는 상당히 자료구조가 방대해진다.
만약 이 풀이가 정석 풀이라면 난이도가 더 올라갔어야 했지만,
카드의 종류가 최대 6개라는 점에서 눈치를 챘어야했다.
permutation을 통해 찾을 카드의 순서를 먼저 정하고(6!)
그 카드를 찾는 bfs를 돌려도 충분히 상황을 시간내에 해결할 수 있다.