2143 => 1234처럼 만들어야 하므로 먼저 str로 받고 원소 각각을 비교하면 된다.
🧐 백준 2108 (통계학 _ statistics 라이브러리 이용)
🤫해결의 실마리
🤔 수학 통계 내장함수 statistics (https://python.flowdas.com/library/statistics.html) 이 문제의 경우, 최빈값을 구하기 위해 count함수를 사용하게 될 경우, 이로 인해 시간초과가 걸리게 된다. 따라서 아래의 통계학관련 statistics 라이브러리의 multimode()함수를 이용해 최빈값을 구해준다.
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 = " ")
