self.winter.(06). 정렬, pair _백준[1427, 2108, 10814, 11650, 11651, 18870]

🧐 백준 1427 (단일 숫자 분리하기)

🤫  solution_1427

num_str_list = list(input())  # ['5', '0', '0', '6', '1', '3', '0', '0', '9']
print(*sorted(num_str_list, reverse = True), sep = "")

2143 => 1234처럼 만들어야 하므로 먼저 str로 받고 원소 각각을 비교하면 된다.

 

🧐 백준 2108 (통계학 _ statistics 라이브러리 이용)

🤫 해결의 실마리 

🤔 수학 통계 내장함수 statistics (https://python.flowdas.com/library/statistics.html)
이 문제의 경우, 최빈값을 구하기 위해 count함수를 사용하게 될 경우, 이로 인해 시간초과가 걸리게 된다.
따라서 아래의 통계학관련 statistics 라이브러리의 multimode()함수를 이용해 최빈값을 구해준다.

statistics --- 수학 통계 함수 — 파이썬 설명서 주석판

🤫  solution_2108

import statistics as st

num = [int(input()) for _ in range(int(input()))]

mode =st.multimode(num)
if len(mode) > 1:
    mode.remove(min(mode))

print(int(sum(num)/len(num)))
print(round(st.median(num)))
print(min(mode))
print(max(num) - min(num))

 

 

 

🧐 백준 10814,11650, 11651 (C++의 pair와 같은 자료구조가 필요해!)  ★★★★★

🤫 해결의 실마리 1. python의 sort는 stable 정렬을 한다.

파이썬은 기본적으로 stable_sort이기에 나이 기준 정렬을 해도 가입한 순서는 그대로!

🤫 해결의 실마리 2.  2차원 리스트의 경우, 하나의 for문으로 접근할 수 있다! 

파이썬은 다음과 같이 2차원 배열의 경우, 한번에 요소에 접근할 수 있다.

arr = list(input().split() for _ in range(int(input())))

for x, y in arr:
    print(x, y)  => arr[0][0], arr[0][1]

🤔 Algorithm 과정 
굳이 int로 받지 않아도 어차피 '20' < '21' 이므로 정렬한 person리스트를 for문을 이용해 접근한다.
이때, 정렬할 때, key = lambda식을 이용해 a[0], 즉 나이를 기준으로 정렬하는 방법을 사용한다.
 

🤫  solution_10814

# 파이썬의 sort함수는 기본적으로 stable정렬을 한다.

person = list(input().split() for _ in range(int(input())))

# str로 받아도 원소값을 int로 받아 비교가 가능하다.
for x, y in sorted(person, key = lambda a: int(a[0])):
    print(x, y)

10814와 마찬가지로 해결 

🤫  solution_11650

num = [list(map(int, input().split())) for _ in range(int(input()))]
# num에는 다음과 같은 형태로 저장됨
# [[3, 4], [1, 1], [1, -1], [2, 2], [3, 3]]

# for문으로 2차원 리스트 요소 출력
# [1, -1] [1, 1] [2, 2] [3, 3] [3, 4]
for x, y in sorted(num):
    print(x, y)

🤫  solution_11651

num = [list(map(int, input().split())) for _ in range(int(input()))]

# 맨 뒤의 원소 a[1]을 기준으로 정렬 후 a[0]을 기준으로 정렬
for x, y in sorted(num, key = lambda a: (a[1], a[0])):
    print(x, y)

단, 이 문제에서 유의할 점은 python은 정렬에서 기준 여러 개 세울 수 있다는 점이다. 위에서 처럼 말이다.

# 맨 뒤의 원소 a[1]을 기준으로 정렬 후 a[0]을 기준으로 정렬
sorted(num, key = lambda a: (a[1], a[0])):

 

🧐 백준 18870 (메모리에 대한 접근)

🤫 해결의 실마리 1. 메모리 제한이 여유롭다??

🤔 이 문제는 메모리 제한이 512MB로 여유로운데, 이에 대해 살펴볼 필요가 있다.
- 메모리 제한이 많음 = 순서를 따로 저장(hash)하지 않으면 시간초과가 발생할 것이라 유추
- 순서만 간단히 비교하면 되기에 set으로 중복을 없애고 sort를 진행하면 더 간단히 해결 가능.
🤔사실 문제에서 말하는 바는 등수를 출력하는 것과 동일!

🤫 해결의 실마리 2. 딕셔너리 자료구조

🤔 Dictionary.
- key-value 형태로 이루어진 자료구조로 값과 데이터의 대응관계를 표현할 때, powerful하다.
- 이때, 핵심은 key값은 중복될 수 없다는 점이며 아래의 코드를 예시로 들어 보겠다.

# x_set에는 [-10, -9, 2, 4] 원소가 들어가있는 set리스트이다.

x_dict = {x_set[i] : i for i in range(len(x_set))}

#x_dict = { -10: 0, -9: 1, 2: 2, 4: 3 }
# print(x_dict[-9])  # key값을 이용한 value, 1 출력

🤔 Algorithm 과정 
1. 입력값을 저장하는 x리스트와
2. x리스트의 원소들이 겹치지 않도록 set을 만들어 정렬시켜준다.
3. 오름차순 정렬이 된 set에 index를 맵핑해주면 그것이 비로소 순위가 되므로
4. set_element  :  index의 맵핑을 위해 딕셔너리를 사용해준다.
5. 그 후 x리스트를 돌면서 해당 원소와 일치하는 값과 맵핑한 딕셔너리의 value값(인덱스, 순위 값)을 출력

 

🤫  solution_18870 (시간초과)

N = int(input())
x = list(map(int, input().split()))
x_prime = []

for i in x:
    cnt = 0
    for j in set(sorted(x)):
        if i > j:
            cnt += 1
    x_prime.append(cnt)
print(*x_prime)

처음 짠 코드로 문제점은 이중 for문을 이용하여 if문을 2번 돌리면 시간복잡도가 O(n^2)이다.
이 문항의 경우 시간복잡도가 O(nlog n)의 정렬 알고리즘이 필요하다.

🤫  solution_18870

N = int(input())
x = list(map(int, input().split()))
x_set = sorted(list(set(x)))
x_prime = []

# x_set의 [-10, -9, 2, 4]에 index를 맵핑하여 딕셔너리로(순위)
# cf. 딕셔너리는 해시를 이용해 데이터 저장
x_dict = {x_set[i] : i for i in range(len(x_set))}
#x_dict = {-10: 0, -9: 1, 2: 2, 4: 3}
# print(x_dict[-9])  # 1 출력


for i in x:
    print(x_dict[i], end = " ")