LC1054: Distant Barcodes

https://leetcode.com/problems/distant-barcodes

  • 쉬운듯 하면서도, 우습게 보았다가 계속 틀린 바코드 문제이다.
  • 처음 시도한 풀이는 기존 지그재그 풀던 식의, 최대 최소 번갈아 가져오기.
    • $[1,2,2,3]$이 입력으로 들어오면 어느 쪽으로 시작하든 겹친다.
  • 결국은 비율이 중요하다는 것을 알게 된다. 제일 빈도 높은 놈들을 먼저 세워놓고 빈도 낮은 녀석들을 사이에 넣는 식이다. 이러면 겹치는게 나오지 않는다.
  • 빈도 순 정렬에는 hash로 카운트 한뒤, set이나 multimap을 활용할 수 있다는게 포인트. set이나 multimap이나 성능차이는 거의 없다.