[정렬] 백준 9237 이장님 초대

9237번: 이장님 초대

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

9237번: 이장님 초대

 

#1 문제 이해

• 묘목 n개를 구입해 모든 묘목을 심고 모든 묘목이 다 자란 다음날을 구하는 문제이다.
• 하루에 한 개의 묘목만 심을 수 있다.
• 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)을 입력받고, 둘째 줄에는 각 묘목들이 다 자라는데 걸리는 일수 (1 ≤ ti ≤ 1,000,000) 를 입력 받는다.
• 입력값이 정수이며 범위가 제한되어 있으므로 빠른 성능을 기대하며 계수 정렬을 사용해보자.
• 먼저 계수 정렬을 이용해 일수를 내림차순으로 정렬한다.
• 묘목이 다 자란 날짜를 기준으로 가장 큰 수(날짜)를 뽑기 위해 일수 배열에 인덱스 i를 더한다.
• 1일 차는 묘목을 구입한 날이고, 묘목들이 다 자란 다음날에 이장님을 초대할 수 있으므로 최종적으로 가장 큰 수에 2일을 더하면 정답이다.

 

#2 어려웠던 부분

지난 BFS 스터디에서 정답률 25%대의 문제에 호기롭게 도전했다가 뺨을 맞고 약간 주눅이 들어서 쉬워보이는 문제를 골라왔다.

(사실 너무 쉬운 문제를 고른 것 같긴 하다.... ㅎㅎ)

그래서 어려웠던 부분은 없다.

 

 

#3 최종 코드

# 묘목의 수
n = input()

# 배열 array 초기화 & 공백 기준 각 묘목 자라는 일수 입력받기
array = []
array = list(map(int, input().split()))

# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
# 0도 포함해야 하기 때문에 max(array) + 1만큼 리스트 크기를 설정
count = [0] * (max(array) + 1)

for i in range(len(array)):
  count[array[i]] += 1  # 각 데이터에 해당하는 인덱스의 값 증가

result = []

# 정렬한 결과 리스트 result
for i in range(len(count)):
  for j in range(count[i]):
    result.append(i)

# reverse
result.reverse()

# 묘목 자라는 일수
for i in range(len(result)):
  result[i] += i

# 이장님 초대 날짜
print(max(result) + 2)