Open seungriyou opened 6 months ago
https://leetcode.com/problems/distant-barcodes/ (similar to #70)
most frequent 한 순서대로 숫자를 채우기 위해서 max heap pq에 (-cnt, num)을 저장하고, pq의 길이가 2 이상일 동안 while 문을 돌며 2개의 원소를 연달아 pop 한다.
pq
(-cnt, num)
해당 원소들을 res에 기록하고, cnt 값을 업데이트하여 다시 pq에 넣는다.
res
cnt
pq에 원소가 1개 남아있는 경우, 이를 그냥 res에 추가한다.
물론, sorting을 heap으로 대체할 수 있기는 하다. 어차피 heap 구성 후 for문 돌며 heappop하는 것이나 sorting 하는 것이나 거기서 거기이므로 나는 sorting을 사용했다.
먼저 res 배열을 통해 칸을 만든다.
주어진 숫자들을 most frequent 한 순서대로 정렬하고, 그 순서대로 등장 횟수만큼 반복하며 res에 2칸 간격으로 채워나간다.
이때 관리하는 index i의 값이 res를 벗어난다면 1로 초기화 하여 second pass를 수행한다.
i
1
k = number of unique number
k
O(nlogk)
O(n + klogk)
O(n)
Approach
72 문제와 마찬가지로 (1) max heap 또는 (2) sorting 으로 풀어볼 수 있다.
Idea 1: Max Heap (빈 곳에서부터 채워나가기)
most frequent 한 순서대로 숫자를 채우기 위해서 max heap
pq에(-cnt, num)을 저장하고,pq의 길이가 2 이상일 동안 while 문을 돌며 2개의 원소를 연달아 pop 한다.해당 원소들을
res에 기록하고,cnt값을 업데이트하여 다시pq에 넣는다.pq에 원소가 1개 남아있는 경우, 이를 그냥res에 추가한다.Idea 2: Sorting (먼저 칸을 만들고 채워나가기)
먼저
res배열을 통해 칸을 만든다.주어진 숫자들을 most frequent 한 순서대로 정렬하고, 그 순서대로 등장 횟수만큼 반복하며
res에 2칸 간격으로 채워나간다.이때 관리하는 index
i의 값이res를 벗어난다면1로 초기화 하여 second pass를 수행한다.Complexity
O(nlogk)/ (sorting)O(n + klogk)O(n)