[백준] 2910번: 빈도 정렬 - python

https://www.acmicpc.net/problem/2910

2910번: 빈도 정렬

 

 

 

배열을 2개 선언하고 

선택정렬로 동작을 수행했으나..

아래와 같은 출력을 보였다.

n, c = map(int ,input().split())

arr = list(map(int, input().split()))

number = []
cnt_list = []
for i in range(n):
    cnt = 0
    if arr[i] not in number:
        number.append(arr[i])
        for j in range(i, n):
            if arr[i] == arr[j]:
                cnt+=1
        cnt_list.append(cnt)

for i in range(len(number)-1):
    for j in range(i, len(number)):
        if cnt_list[i] < cnt_list[j]:
            tmp = cnt_list[i]
            cnt_list[i] = cnt_list[j]
            cnt_list[j] = tmp
            
            tmp = number[i]
            number[i] = number[j]
            number[j] = tmp

for i in range(len(number)):
    for j in range(cnt_list[i]):
        print(number[i], end=" ")

9 77
11 33 11 77 54 11 25 25 33

11 11 11 33 33 25 25 54 77

으로 처음부터 끝까지 중복으로 값을 비교해 교환하는 것에는 순차적으로 되어있는 값이 변경될 수 있는 문제가 있었다. 여기서 생각한게 버블정렬로 구현하여 값의 변경을 줄이고자 코드를 다시 작성하였다.

 

n, c = map(int ,input().split())

arr = list(map(int, input().split()))

number = []
cnt_list = []
for i in range(n):
    cnt = 0
    if arr[i] not in number:
        number.append(arr[i])
        for j in range(i, n):
            if arr[i] == arr[j]:
                cnt+=1
        cnt_list.append(cnt)


for i in range(len(number)-1):
    for j in range(len(number)-i-1):
        if cnt_list[j] < cnt_list[j+1]:
            tmp = cnt_list[j+1]
            cnt_list[j+1] = cnt_list[j]
            cnt_list[j] = tmp
            
            tmp = number[j+1]
            number[j+1] = number[j]
            number[j] = tmp

for i in range(len(number)):
    for j in range(cnt_list[i]):
        print(number[i], end=" ")

 

그 결과 원하는 

11 11 11 33 33 25 25 77 54  이 잘 출력되었다.