[2025 1학기 알고리즘 스터디] 1주차, 박현빈

10989번: 수 정렬하기 3

각 수에 대응하는 리스트를 생성하여 나오는 숫자 만큼 카운팅하고, 출력

import sys

N = int(sys.stdin.readline())
count = [0] * 10001 

for _ in range(N):
    count[int(sys.stdin.readline())] += 1  

for num in range(10001):
    if count[num] > 0:
        for _ in range(count[num]):
            print(num)

 

11652번: 카드

Counter를 사용하여 빈도수를 계산한 후, 최빈값을 찾음.정렬하여 최빈값이 같은 경우 가장 작은 숫자 선택.

카운팅 함수 없이 문제를 해결하고자 한다면, 딕셔너리를 선언한고 이러한 딕셔너리를 의 키로 등장하는 수로 값을 등장하는 횟수를 값으로 넘겨준다. 

해당 문제를 푸는 과정에서 딕셔너리보다 Counter의 동작 방식만 이해한다면 훨씬 짧고 직관적인 코드를 작성할 수 있다. 

import sys
from collections import Counter

N = int(sys.stdin.readline())
cards = [int(sys.stdin.readline()) for _ in range(N)]

counter = Counter(cards)  
max_count = max(counter.values())  

print(min(k for k, v in counter.items() if v == max_count))

 

18870번: 좌표 압축

중복 제거 후 정렬하여 압축된 인덱스를 매핑. 딕셔너리를 사용하여 빠르게 변환.

n = int(sys.stdin.readline().strip())

number_list = list(map(int, sys.stdin.readline().split()))

# 중복 제거 및 정렬 
sort_number_list = list(set(number_list))
sort_number_list.sort()

# 각 value의 순서를 dictional에 키와 값으로 저장한다. 좌표의 값이 키로 좌표의 순서가 값으로 간다.
index_dic = {}
counter = 0
for number in sort_number_list:
    index_dic[number] = counter
    counter += 1

index_list = []
for number in number_list:
    index_list.append(str(index_dic[number]))

print(" ".join(index_list))

"""
index_list = []
for number in number_list:
    index_list.append(str(sort_number_list.index(number)))
print(" ".join(index_list))
다음 코드는 index를 통해서 좌표 압축을 하려했던 코드이다. index의 경우 시간 복잡도가 O(n)이다. 
그런데 이를 n개의 원소에 반복함으로 시간복잡도가 O(n^2)가 되기 때문에 index()를 사용할 수 없다. 
그렇기에 나는 시간복잡도가 O(1)인 딕셔너리를 이용했다. 
"""