창고에 바코드 행이 있다고 가정합니다. i번째 바코드는 바코드[i]입니다. 인접한 두 바코드가 동일하지 않도록 바코드를 재배열해야 합니다. 따라서 입력이 [1,1,1,2,2,2]이면 출력은 [2,1,2,1,2,1]입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- d라는 이름의 지도 하나 만들기
- 바코드 배열에 있는 숫자의 빈도를 d에 저장
- x :=빈 목록
- 모든 키-값 쌍을 x에 삽입
- i :=0
- res :=바코드와 길이가 같은 목록을 만들고 [0]을 채우십시오.
- 빈도에 따라 x 정렬
- 동안 i <결과의 길이
- result[i] :=x의 마지막 항목 요소
- x의 마지막 항목의 빈도 값 감소
- x의 마지막 요소의 빈도가 0이면 x에서 해당 항목을 삭제합니다.
- i를 2 증가
- i :=1
- 동안 i <결과의 길이
- result[i] :=x의 마지막 항목 요소
- x의 마지막 항목의 빈도 값 감소
- x의 마지막 요소의 빈도가 0이면 x에서 해당 항목을 삭제합니다.
- i를 2 증가
- 반환 결과
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution(object):
def rearrangeBarcodes(self, barcodes):
d = {}
for i in barcodes:
if i not in d:
d[i] = 1
else:
d[i]+=1
x = []
for a,b in d.items():
x.append([a,b])
i = 0
result = [0]*len(barcodes)
x = sorted(x,key=lambda v:v[1])
while i <len(result):
result[i] = x[-1][0]
x[-1][1]-=1
if x[-1][1]==0:
x.pop()
i+=2
i=1
while i <len(result):
result[i] = x[-1][0]
x[-1][1]-=1
if x[-1][1]==0:
x.pop()
i+=2
return result
ob = Solution()
print(ob.rearrangeBarcodes([1,1,1,2,2,2])) 입력
[1,1,1,2,2,2]
출력
[2, 1, 2, 1, 2, 1]