[python] 단계별로 풀어보기 - 12단계

 

 

 

 

 

 

계수 정렬 / 카운팅 정렬

시간 복잡도 : O(n+k) (k는 데이터의 최댓값)

=> 속도가 엄청 빠름. 퀵 정렬, 힙 정렬, 합병 정렬의 평균 시간 복잡도 => O(nlogn)

​

정렬 방법: 데이터가 몇번 나왔는지 count -> 받은 수가 몇 번 들어왔는지 빈도 계산 -> 등장 횟수를 누적 합으로 바꾸기 -> 입력받았던 정렬할 배열을 뒤에서 앞으로 순회하면서 정렬된 배열에 넣기. (넣어준 뒤에는 누적합 -1 해주기)

​

정리:

시간 복잡도는 훨씬 유리하지만, 엄청난 메모리 낭비를 야기할 수 있음. (배열에 포함된 최댓값 만큼 메모리가 필요함)

따라서, k가 엄청 크다면 차라리 퀵정렬, 힙 정렬, 합병 정렬을 쓰는 것이 나음.

또한, 데이터 값이 정수라는 전제가 있어야한다.

순서대로 정렬을 해 주는데, 각각의 숫자를 비교하지 않고, count만 한다는 점이 특이하게 느껴졌다.

​

​

​

​

​

다만 문제를 풀때는, 더 간단하게 코드를 짤 수 있다.

​

입력값 중, 어떤 데이터가 몇번이 나왔는지 count 하고

(ex)[5,2,3,1,4,2,3,5,1,7]이라는 배열을 받았다면, 1=>2번, 2=>2번, 3=>2번, 4 =>1번, 5=>2번, 7 =>1번)

​

배열의 index는 0부터 시작하니까, +1을 해준 뒤, 해당하는 곳에 각 숫자의 개수를 넣어 주고,

(ex)[0,2,2,2,1,2,0,1])

​

해당 인덱스에서 숫자의 수만큼 출력한다.

(ex) index0의 자리에는 0, index1의 자리에는 2, index2의 자리에는 2....이므로

출력: 1122334557)

 

 

 

 

---

 

12-1) 백준 2750번: 수 정렬하기

 

a = int(input())
b = []
for i in range(a):
    b.append(int(input()))
    
b.sort()

for j in b:
    print(j)

 

수를 입력받아, 배열 b에 저장하고, 정렬한 뒤 출력

​

 

 

 

 

 

12-2) 백준 2751번: 수 정렬하기2

 

import sys
a = int(sys.stdin.readline())
b = []

for _ in range(a):
    x =int(sys.stdin.readline())
    b.append(x)

for i in sorted(b):
    print(i)

 

1과 문제는 같지만, 1은 시간 복잡도가 O(n^2)이지만,

2번은 시간복잡도가 O(nlogn)이다.

원래 파이썬에 내장된 함수sort의 시간복잡도가 O(nlogn)이지만, 앞에 입력받고? 그런데에서 시간 복잡도가 늘었나보다. 그래서 구글링을 하다가 sys를 import해서 수를 받아오는 것이 더 효과적이다고 해서 그렇게 변경한 뒤, 제출하니 정답으로 떴다!

 

 

 

 

 

 

12-3) 백준 10989번: 수 정렬하기3

 

import sys
n = int(sys.stdin.readline())
b = [0] * 10001
for i in range(n):
    b[int(sys.stdin.readline())] += 1
for i in range(10001):
    if b[i] != 0:
        for j in range(b[i]):
            print(i)

 

맨 위에서 설명했듯,

문제를 예로 들어, 입력값을 list에 넣어보면 [5,2,3,1,4,2,3,5,1,7]

데이터가 몇번 나왔는지 count하면 1=>2번, 2=>2번, 3=>2번, 4 =>1번, 5=>2번, 7 =>1번

배열의 index는 0부터 시작하니까, +1을 해준 뒤, 해당하는 곳에각 숫자의 개수를 넣어 주고,([0,2,2,2,1,2,0,1])

숫자의 수만큼 출력한다.

 

 

 

 

 

 

12-4) 백준 2108번: 통계학

 

import sys
from collections import Counter

a = int(sys.stdin.readline())
b = []

for _ in range(a):
    x =int(sys.stdin.readline())
    b.append(x)

b.sort()

cnt = Counter(b)
modes = cnt.most_common()    
if len(b) > 1 :
    if modes[0][1] == modes[1][1]:
        mod = modes[1][0]
    else : 
        mod = modes[0][0]
else : 
    mod = modes[0][0]

print(round(sum(b)/a))
print(b[((a//2))])
print(mod)
print(max(b)-min(b))

 

평균, 중간값, 최대값과 최소값의 차를 구하는 것은 쉬웠는데,

빈도를 구하는 것이 조금 어려웠다.

most_common()함수를 쓴다.

그래서 이차원배열에 넣고, modes[0][1] 과 modes[1][1]의 위치에 있는 수를 비교한다

​

​

 

 

 

 

​​

12-5) 백준 1427번: 소트인사이드

 

a = str(input())
b = []
b = list(a)
b.sort()
b.reverse()
print(''.join(b))

 

​수를 str로 입력받아서 리스트에 넣고, 오름차순으로 정렬하고 다시 그것을 내림차순으로 정렬한다.

그리고 리스트에 넣었으니까, ''를 빼고 출력한다.

​

​

​

​

 

 

 

 

12-6) 백준 11650번: 좌표 정렬하기

 

M = int(input())
nums = []
for i in range(M):
    [a, b] = map(int, input().split())
    nums.append([a, b])

nums = sorted(nums)

for j in range(M):
    print(nums[j][0], nums[j][1])

 

​수를 차례로 입력받아서 리스트에 넣고, 정렬!

sorted만 해줘도 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬된다.

출력할때는,정렬된 것을 순서대로 [인덱스번호][0], [인덱스번호][1] 위치에 있는 것을 출력한다.

​

​

 

 

 

​

​

12-7) 백준 11651번: 좌표 정렬하기2

 

M = int(input())
nums = []
for i in range(M):
    [a, b] = map(int, input().split())
    nums.append([b, a])

nums = sorted(nums)

for j in range(M):
    print(nums[j][1], nums[j][0])

 

위와 같은 방식으로 푸는데 x,y의 위치를 바꿔서 입력받게 했다.

​

​

 

 

​

​

12-8) 백준 1181번: 단어 정렬

​

M = int(input())
nums = []
for i in range(M):
    a = str(input())
    nums.append(a)

num_list = list(set(nums))
num_list.sort()  #알파벳 순으로 정렬
num_list.sort(key=lambda x:len(x)) #길이 순으로 정렬 

for i in range(0, len(num_list)):
    print(num_list[i])

​

위와 같은 방식으로 입력을 받아서 배열에 저장하고, set을 이용하여 동일한 문자가 있다면 없애준다.

그 다음 sort를 통해 알파벳 순으로 정렬하고, 그 정렬 된 것을 파라미터 len을 사용하여 다시 정렬해준다.

​

​

 

​

​

12-9) 백준 10814번: 나이순 정렬

 

M = int(input())
nums = []
for i in range(M):
    [a, b] = list(input().split())
    nums.append([a, b])

nums.sort(key = lambda x:int(x[0]))

for i in range(M):
    print(nums[i][0], nums[i][1])

 

인덱스 0에 해당되는 것으만 정렬하고 (나이) 출력

만약 여기서 이름도 알파벳순으로 오도록 하고 싶다면

7번째 줄을 nums.sort(key = lambda x:(x[0], x[1])) 로 바꿔주면 된다.