정렬

파이썬에서 제공하는 정렬함수로는 sort, sorted가 있다.

 

• list.sort()
• list2 = sorted(list)
• sort(key=len, reverse=True)

 

#2

input을 사용할 경우 시간 및 메모리 초과가 나와 sys.stdin.readline을 활용하였다.

import sys

size = int(input())
l = list()

for i in range(size):
    k = int(sys.stdin.readline())
    l.append(k)

l2 = sorted(l)
        
for i in l2:
    print(i)

 

#3

카운팅 정렬을 활용한다.

size = int(input())
arr = []
for i in range(size):
    arr.append(int(input()))

count = [0]*(max(l)+1)

for num in arr:
    count[num] += 1

for i in range(1, len(count)):
    count[i] += count[i-1]
    
result = [0] * size

for num in arr:
    idx = count[num]
    count[num] -= 1
    result[idx-1] = num
    
for num in result:
    print(num)

 

메모리 초과가 떠 버렸다. 딕셔너리를 활용해보았다.

 

size = int(input())
arr = []
for i in range(size):
    arr.append(int(input()))

count_dict = {}

for num in arr:
    if num in count_dict:
        count_dict[num] += 1
    else:
        count_dict[num] = 1
            
result = []

for i in range(max(arr)+1):
    while i in count_dict and count_dict[i] != 0:
        result.append(i)
        count_dict[i] -= 1

for num in result:
    print(num)

 

또 메모리 초과다. ㅎㅎㅎㅎ

카운팅 정렬을 응용해보았다. 조금만 더 생각해보면 훨씬 쉽게 풀 수 있다는 것을 알게 되었다.

 

import sys

size = int(input())
b = [0] * 10001

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

 

#4

입력만 받을 수 있으면 쉽게 풀 수 있는 문제였다.

N, k = map(int, input().split())
l = list(map(int, input().split()))

l.sort(reverse=True)
print(l[k-1])

 

#5

최빈값(여러 개 있을 때에는 최빈값 중 두 번째로 작은 값)을 출력하는 함수만 기록하겠다.

l2를 통해 숫자의 개수를 세어주었고, l2의 최대값의 index를 두 개(하나라면 한 개) 가져와 해당 index에 대한 l의 원소값을 반환하였다.

def mode(l, size):
    if size == 1: return l[0]
    
    l2 = [1]
    count = 1
    for i in range(size-1):
        if l[i] == l[i+1]:
            count += 1
        else:
            count = 1
        l2.append(count)    
    
    temp = []
    max_val = max(l2)
    key1 = l2.index(max_val)
    temp.append(l[key1])
    
    l2.remove(l2[key1])
    
    max_val2 = max(l2)
    if max_val == max_val2:
        key2 = l2.index(max_val)+1
        temp.append(l[key2])
    
    j = len(temp)
    if j == 1:
        return temp[0]
    else:
        return temp[1]

 

#6

sort(reverse=True)를 사용하면 내림차순으로 정렬할 수 있다.

 

#7

sort의 default 연산은 x1 정렬 -> x1의 값이 같을 경우 x2 정렬이다.

즉 다음과 같이 정렬된다.

1 -1

1 1

2 2

3 3

3 4

 

#8

key=len을 사용할 경우 문자열 길이별로 정렬할 수 있다.

* sys.stdin.readline().strip()

-> sys.stdin.readline()의 경우 개행문자를 포함하기 때문에 strip()을 통해서 이를 제거할 필요가 있다.

 

#9

key=lambda x:x[1]을 사용할 경우 x2에 대해서만 정렬할 수 있다.

for x, y in l:

    print(x, y)

#10

dictionary를 활용해야 한다. 추후 공부하고 돌아오겠다.