[백준] 1697, 2108 - Python3

2108. 통계학

https://www.acmicpc.net/problem/2108

내 풀이 - 성공

from sys import stdin
import collections
import math

N = int(stdin.readline())
nums = [0] * N

for i in range(N):
    nums[i] = int(stdin.readline())

nums.sort()

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

# 중앙값
print(nums[N//2])

# 최빈값
n = collections.Counter(nums)
m = 1
for k,v in n.items():
    if v > m:
        m = v
r = []
for k,v in n.items():
    if v == m:
        m = v
        r.append(k)
        if len(r) == 2:
            r.pop(0)
            break
print(r[0])

# 범위
print(nums[-1] - nums[0])

입력받은 숫자들은 nums 에 모두 저장한 후 sort()

산술평균 : N개의 수들의 합을 N으로 나눈 값
round() 함수로 소수점 이하 첫째 자리에서 반올림하도록 함

중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
N 은 무조건 홀수이므로 2 로 나눈 중간값 print

최빈값 : N개의 수들 중 가장 많이 나타나는 값
Counter 로 숫자들의 빈도수를 파악한 후, 최대 빈도수 m 구하기
다시 값들을 보면서 m 과 같은 값들은 r 에 저장
"여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력" 해야 하므로
길이가 2 개가 되면 break

범위 : N개의 수들 중 최댓값과 최솟값의 차이
마지막 값 - 처음 값

최빈값 다른 풀이

ncnt = collections.Counter(nums).most_common()
if len(ncnt) > 1 and ncnt[0][1] == ncnt[1][1]:
    print(ncnt[1][0])
else:
    print(ncnt[0][0])

most_common() : 데이터의 개수가 많은 순으로 정렬된 배열 return
ex) 'hello world'
=> [('l', 3), ('o', 2), ('h', 1), ('e', 1), (' ', 1), ('w', 1), ('r', 1), ('d', 1)]

most_common(1) : 최대 빈도수의 값 return
ex) ('l', 3)

---

1697. 숨바꼭질

https://www.acmicpc.net/problem/1697

내 풀이 - 시간초과

import sys
sys.setrecursionlimit(10**5)

N, K = map(int, sys.stdin.readline().split())

ans = abs(K-N)
M = N
while M < K:
    M *= 2

def func(n, k, cnt):
    global ans, M
    
    if ans < cnt:
        return
    if n == k:
        ans = min(ans, cnt)
        return

    # 걷기
    if n-1 >= 0 and cnt+1 <= ans:
        func(n-1, k, cnt+1)
    if n+1 <= k and cnt+1 <= ans:
        func(n+1, k, cnt+1)

    # 순간이동
    if n*2 <= M and cnt+1 <= ans:
        func(n*2, k, cnt+1)

func(N, K, 0)
print(ans)

우선 ans 는 abs(K-N) 으로 초기화
=> N 이 K 보다 큰 경우를 고려

순간이동의 범위를 제한하기 위해 M 지정
=> N 에 2 를 곱한 값 중 K 보다 큰 첫번째 값

재귀 함수를 돌려서 ans 에 최소 횟수 update
걷기는 0 ~ k 범위이도록 함

하지만 시간 초과...☆

다른 사람의 풀이

import sys
import collections

N, K = map(int, sys.stdin.readline().split())

queue = collections.deque()
dist = collections.defaultdict(int)
visited = collections.defaultdict(int)

queue.append(N)
visited[N] = 1

# bfs
while queue:
    node = queue.popleft()
    if node == K:
        print(dist[node])
        break
    for next_node in (node-1, node+1, 2*node):
        if visited[next_node] != 1 and next_node <= 100000:
            queue.append(next_node)
            visited[next_node] = 1
            dist[next_node] = dist[node] + 1

deque 를 이용한 queue 생성
dist : 걸린 시간 저장
visited : 봤던 숫자들인지 체크

처음 시작 값인 N 을 queue 에 저장 & visited[N] = 1

반복문을 이용한 bfs 로
지금 node 가 K 라면 print & break
아니라면 (node-1, node+1, 2*node) 세가지 경우를 보면서
방문한 노드가 아니고 100000 보다 작을 때만
queue 에 저장 & visited = 1 & dist 값 update

참고) https://deep-learning-study.tistory.com/611