[2022 하계 모각코] 팀 "한 명 어디갔노" 1회차 - 계획 및 결과

목표
알고리즘 실력 향상을 위해 백준에서 출제하는 문제들을 풀어본다.

사용 언어
Python

일정
1회차: 7/2 19:00 ~ 22:00
목표 : 백준 정렬 알고리즘 관련 3 - 4 문제 풀기

1. 백준 2750번
   
   단순히 수를 정렬하는 문제로, 기본적인 문제를 먼저 풀어보았다. PYTHON의 min 내장함수를 이용하여 리스트에서 가장 작은 값을 꺼내와 새로운 리스트에 값을 추가하고 가장 작은 값을 리스트에서 삭제하는 방식으로 코드를 구현했다.

def sort_number():
    n = int(input())
    s = []
    for i in range(n):          # 정렬할 수 리스트에 넣기
        temp = int(input())
        s.append(temp)
    result = []
    for i in range(len(s)):
        result.append(min(s))
        s.remove(min(s))
    for i in range(len(result)):
        print(result[i])

    if __name__ == '__main__':
        sort_number()

2. 백준 2108번
   

• 산술평균 : sum 내장함수로 리스트 값의 합을 구한 후 리스트의 길이로 나눈다. 이때 round 내장함수를 이용하여 조건을 만족시킨다.

• 중앙값 : 정렬을 한 뒤 (전체 리스트 길이 - 1) // 2 인 인덱스값을 반환한다.

• 최빈값 : 계수정렬을 이용하려 했으나... 필요한 리스트의 길이가 너무 커 Runtime Error가 발생하였다. 그래서 dictionary를 이용해서 키와 값을 갱신하도록 하였다. 조건에 최빈값이 여러개가 있을 경우 두번째로 작은 값을 출력해야하므로 키를 count 개수로 하고 값을 리스트값을 리스트의 형태로 넣어주었다.

• 범위 : max, min 내장함수를 이용한다.

n = int(input())

nums = []
for _ in range(n) :
	nums.append(int(input()))

# 산술평균
print(round(sum(nums)/n))

# 중앙값
nums.sort()
print(nums[int((n-1)/2)])

# 최빈값
counts = dict()
for i in range(1,n+1) :
	counts[i] = []

maxCount = 1
count = 1
for j in range(1,n) :
	if nums[j] == nums[j-1] :
		count += 1
	else :
		counts[count].append(nums[j-1])
		if maxCount < count : maxCount = count
		count = 1
	if j == n-1 : 
		counts[count].append(nums[j])
		if maxCount < count : maxCount = count

if n == 1 :
	counts[1].append(nums[0])

counts[maxCount].sort()
if len(counts[maxCount]) == 1 :
	print(counts[maxCount][0])
else :
	print(counts[maxCount][1])

# 범위
print(max(nums) - min(nums))

하지만 이렇게 코드를 실행하면 시간초과로 통과하지 못하였다.
pypy3로 돌릴 경우는 정상적으로 통과할 수 있었다.
이를 해결하기 위해 python의 컬렉션 라이브러리의 Counter를 이용하기로 했다.
counter의 most_common() 메소드는 딕셔너리의 최빈값을 키와 값을 저장하여 2차원 배열로 반환한다.
이를 이용하여 코드를 작성하면 아래와 같다.

import sys
from collections import Counter

# main
t = int(sys.stdin.readline())

numbers = []
for _ in range(t):
    numbers.append(int(sys.stdin.readline()))


def mean(nums):
    return round(sum(nums) / len(nums))


def median(nums):
    nums.sort()
    mid = nums[len(nums) // 2]  # nums의 개수는 홀수

    return mid


def mode(nums):
    mode_dict = Counter(nums)
    modes = mode_dict.most_common()

    if len(nums) > 1:						# 최빈값이 여러개인 경우 두번째로 작은 값을 출력하기 위함.
        if modes[0][1] == modes[1][1]:
            mod = modes[1][0]
        else:
            mod = modes[0][0]
    else:
        mod = modes[0][0]

    return mod


def scope(nums):
    return max(nums) - min(nums)


print(mean(numbers))
print(median(numbers))
print(mode(numbers))
print(scope(numbers))

시간초과를 피하기 위해 sys.stdin.readline()을 사용하였다.

3. 백준 18870
   
   내용을 이해하는데 정말 어려웠다.
   문제를 단순히 정리하자면 크기 순으로 해당하는 수가 리스트 중에서 몇번째로 큰 지를 매기는 문제이다.
   이 때 가장 작은 것은 0부터 시작한다.
   여기서 같은 값이 들어올 수 있음에 유의해야한다.
   따라서 set 자료구조를 이용해서 중복을 제거한 뒤 정렬을 하고 해당하는 값을 부여하면 크기 순서를 알 수 있다.
   이를 코드로 구현하면 아래와 같다.

import sys

input = sys.stdin.readline

n = int(input())

arr = list(map(int, input().split()))

arr2 = sorted(list(set(arr)))
dic = {arr2[i] : i for i in range(len(arr2))}

for i in arr:
    print(dic[i], end= ' ')

이상으로 1회차 모각코를 마친다.