LeetCode - Distant Barcodes(1054)

Sort - Medium

In a warehouse, there is a row of barcodes, where the ith barcode is barcodes[i].

Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.
(답은 일단 무조건 존재한다 -> 안되는 경우는 제외)

Example 1:

Input: barcodes = [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

Example 2:

Input: barcodes = [1,1,1,1,2,2,3,3]
Output: [1,3,1,3,1,2,1,2]

Constraints:

∙ 1 <= barcodes.length <= 10000
∙ 1 <= barcodes[i] <= 10000

---

시간 초과(조합, 순열 메서드 메모리 주의)

from itertools import permutations

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        
        permu = list(permutations(barcodes, len(barcodes)))
        
        for i in range(len(permu)):
            c = 0
            for j in range(len(permu[i]) - 1):
                if permu[i][j] == permu[i][j + 1]:
                    break
                c += 1
                
            if c == len(permu[i]) - 1:
                return list(permu[i])

참고 솔루션
Runtime: 404 ms / Memory : 16.4 MB
Time: O(N * logN) / Space : O(1)

from collections import Counter

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        
        i, n = 0, len(barcodes)
        answer = [0] * n
        
        for x, y in collections.Counter(barcodes).most_common():
        # collections.Counter(list) : (원소, 원소의 빈도)
        # most_common(): 빈도를 기준으로 정렬된 상태
        # x : 바코드 숫자, y : 바코드 숫자의 출현 빈도
            for z in range(y):
                answer[i] = x
                i += 2
                if i >= n: 
                    i = 1
                    
        return answer
                
                    

---

참고

https://www.daleseo.com/python-collections-counter/
https://xingxingpark.com/Leetcode-1054-Distant-Barcodes/
(Greedy + Heap) https://leetcode.ca/2018-10-19-1054-Distant-Barcodes/