백준_단계별로 풀어보기_13단계_정렬

배열의 원소를 순서대로 나열하는 알고리즘을 배워 봅시다.

정렬 단계 (acmicpc.net)

정렬 단계

---

■ 백준 2750 수 정렬하기_브론즈 2

- 시간 복잡도가 O(n²)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 삽입 정렬, 거품 정렬 등이 있습니다.

import sys
arr = []
idx = 0
for _ in range(int(input())):
    n = int(sys.stdin.readline())
    for i in range(len(arr)):
        if n > arr[i]: idx = i+1
        elif n < arr[0]:
            idx = 0
            break
    arr.insert(idx, n)
print(*arr, sep='\n')

 

■ 백준 2587 대푯값 2_브론즈 2

- 5개의 수의 평균과 중앙값을 구하는 문제

import sys
arr = sorted([int(x) for x in sys.stdin])
print(sum(arr)//5)
print(arr[2])

 

■ 백준 25305 커트라인_브론즈 2

- k번째로 큰 수를 구하는 문제

n, k = map(int, input().split())
x_li = sorted(list(map(int, input().split())), reverse=True)
print(x_li[k-1])

 

■ 백준 2751 수 정렬하기 2_실버 5

- 시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다.
- 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다.

import sys
n_li = []
for _ in range(int(input())):
    n_li.append(int(sys.stdin.readline()))
print(*sorted(n_li), sep='\n')

 

■ 백준 10989 수 정렬하기 3_브론즈 1

- 수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다.

# import sys
# arr = []
# for _ in range(int(input())):
#     arr.append(int(sys.stdin.readline()))
# count_arr = [0] * (max(arr)+1)
# for i in arr:
#     count_arr[i] += 1
# for i in range(len(count_arr)):
#     if count_arr[i] > 0:
#         print(*([i]*count_arr[i]), sep="\n")

#수정코드: 기존 코드는 n이 천만개를 가질 수도 있는 리스트를 만들려고 해서 메모리초과가 떴다.
import sys
count_arr = [0] * 10001
for _ in range(int(input())):
    count_arr[int(sys.stdin.readline())] += 1
for i in range(len(count_arr)):
    for _ in range(count_arr[i]):
        print(i)

 

■ 백준 1427 소트인사이드_실버 5

- 숫자를 정렬하는 문제

n_arr = [int(x) for x in input()]
n_arr.sort(reverse=True)
print("".join(str(x) for x in n_arr))

 

■ 백준 11650 좌표 정렬하기_실버 5

- 좌표를 정렬하는 문제

import sys
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(int(input()))]
arr.sort()
for i in arr: print(*i)

#고수코드: 각 좌표별로 정렬하고 문자열 출력
import sys
l = sys.stdin.readlines()[1:]
l.sort(key=lambda x: int(x.split()[1]))
l.sort(key=lambda x: int(x.split()[0]))
sys.stdout.write(''.join(l))

 

■ 백준 11651 좌표 정렬하기 2_실버 5

- 좌표를 다른 순서로 정렬하는 문제

import sys
li = sys.stdin.readlines()[1:]
li.sort(key=lambda x: int(x.split()[0]))
li.sort(key=lambda x: int(x.split()[1]))
sys.stdout.write("".join(li))

 

■ 백준 1181 단어 정렬_실버 5

- 단어의 순서를 정의하여 정렬하는 문제

# # [Psuedo code]
# # len()으로 길이를 저장하여 길이순으로 정렬 (value 정렬?)
# # key 정렬
# import sys
# w_dict = dict()
# for i in range(int(input())):
#     word = sys.stdin.readline().rstrip()
#     if word in w_dict: pass
#     else: w_dict[word] = len(word)
# w_dict = sorted(w_dict.items())
# for key, value in sorted(w_dict, key=lambda item: item[1]):
#     print(key)

# 고수코드: 카운트 정렬 매커니즘 사용(단어 길이별로 저장, 각 요소별 정렬)
import sys
input = sys.stdin.readline
word_set_list = [set() for _ in range(51)] # 집합 51개를 가지는 리스트 생성
 
n = int(input())
for _ in range(n):
    word = input().rstrip()
    word_set_list[len(word)].add(word)

for word_set in word_set_list:
    if len(word_set) == 0:
        continue
    word_set = sorted(word_set)
    print('\n'.join(word_set))

 

■ 백준 10814 나이순 정렬_실버 5

- 값이 같은 원소의 전후관계가 바뀌지 않는 정렬 알고리즘을 안정 정렬(stable sort)이라고 합니다.

# import sys
# member_list = [list() for _ in range(201)]
# for _ in range(int(input())):
#     age, name = sys.stdin.readline().split()
#     member_list[int(age)].append(name)
# for m in range(len(member_list)):
#     if len(member_list[m]) == 0:
#         continue
#     else:
#         for i in member_list[m]:
#             print(m, i)

#고수코드: 람다를 활용해보자!
import sys
name_list = sys.stdin.readlines()[1:]
name_list.sort(key=lambda iD : int(iD.split()[0]))
print("".join(name_list))

 

■ 백준 18870 좌표 압축_실버 2

- 만약 정확한 값이 필요 없고 값의 대소 관계만 필요하다면, 모든 수를 0 이상 N 미만의 수로 바꿀 수 있습니다.

# input()
# arr = list(map(int, input().split()))
# sorting = sorted(list(set(arr)))
# for i in arr:
#     print(sorting.index(i), end=" ")

#수정코드: 인덱스말고 딕셔너리를 애용하자
input()
arr = list(map(int, input().split()))
sorted_arr = sorted(list(set(arr)))
sorted_dict = {k:idx for idx, k in enumerate(sorted_arr)}
print(" ".join(str(sorted_dict[x]) for x in arr))