[백준/Python] 16200번 - 해커톤

import sys
input = sys.stdin.readline

# 팀의 수가 최소
# i번은 팀원 수가 자기 자신 포함 xi명 이하여야함
n = int(input())
xi = [0 for _ in range(n+1)] # xi의 범위는 1<= xi <= n
for v in list(map(int, input().split())):
  xi[v] += 1

result = 0
p = 0 # 사람이 더 들어갈 수 있는 팀에서 필요한 사람 수
for i, v in enumerate(xi): # xi 오름차순 무조건!
  if v == 0:
    continue
  
  if p >= v:
    p -= v # 이전에 사람 들어갈 수 있는 팀으로 자동 배정
    continue

  # xi 내에서 팀 만들기
  v -= p # 이전 팀으로 자동 배정
  p = 0
  result += (v // i)

  # 남은 사람이 있다면
  rest = v % i
  if rest:
    result += 1 # 일단 남은 사람끼리 팀 만들기
    p = i - rest # 사람이 더 들어갈 수 있는 팀에서 필요한 사람 수

print(result)

그리디 문제다. bfs를 즐겨 사용하지 않아서 구현으로 풀었다.

메인 아이디어는 다음과 같다. "같은 xi를 가진 팀원끼리 xi에 맞게 팀을 만든다"

- 같은 xi를 가진 인원 수를 측정하여 저장

- xi를 오름차순 함(부족한 인원수를 상위 xi를 가진 사람들으로만 채울 수 있기 때문. 가장 가까운 xi를 가진 사람일수록 효율적)

 

고민이 됐던 지점은 서로 팀을 만들고 남은 사람들의 처리를 어떻게 구현해야할지 였다.

우선 남은 사람은 팀을 만들고, 그 팀에 몇명을 더 채워넣을 수 있는지를 저장하고 있는 p 변수를 만들었다.

 

그 다음 xi에서 p 만큼 숫자를 빼준 이유는, 팀의 수를 줄이기 위해서는 인원 수가 남는 팀으로 무조건 가야했기 때문이다.

이 식을 넣기 위해 v가 0이거나, v가 p보다 작은 경우의 예외 처리가 필요했다(2개의 if문)

 

시간 복잡도

학생 수는 1 ≤ N ≤ 100,000

for문: O(n)

=> O(n)

 

다른 사람 풀이

- 위 아이디어를 좀 더 간단하게 구현할 수 있다.

xi 배열을 인원수 측정에 사용하지 않고 그냥 입력값 그대로 받아서 오름차순으로 정렬한다.

그리고 그냥 최대 인원 수 대로 끊어서 센다(간단 그잡채ㅋㅋㅋㅋ내 고민이 너무 허무해~)

N = int(input())
X = list(map(int,input().split()))
X.sort()

i, cnt = 0, 0
while i < len(X):
    cnt += 1
    i += X[i]
print(cnt)