[백준] 4358번 - 생태학

문제 설명

생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 때, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다.

입력

프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어진다.

출력

주어진 각 종의 이름을 사전순으로 출력하고, 그 종이 차지하는 비율을 백분율로 소수점 4째자리까지 반올림해 함께 출력한다.

---

문제 분석

'생태학' 문제는 입력으로 주어진 여러 개의 나무 이름이 각각 전체 입력에서 차지하는 비율을 구하는 문제이다.
출력 시에는 나무 이름을 사전순으로 정렬하고, 각 비율을 소수점 네 자리까지 출력해야 한다.

문제 자체는 어렵지 않으며, 접근 방식도 직관적이다.
즉, 나무의 빈도를 세고, 이를 전체 개수로 나눈 후 정렬하여 출력하면 되는 문제이다.

---

초기 접근 방식

처음에는 아래와 같은 방식으로 풀었다.

from collections import Counter
a = []
while True:
  try:
    a.append(input())
  except:
    break

for key, value in sorted(Counter(a).items()):
  print(key, round((value / len(a)) * 100, 4))

✅ 코드 설명

1. while True 루프를 사용하여 입력을 계속 받는다.
2. try-except를 활용하여 EOF(End of File)가 입력될 때까지 데이터를 읽는다.
3. Counter를 이용하여 나무의 출현 빈도를 계산한다.
4. 정렬 후, 비율을 round(%, 4)로 출력한다.

---

⛔ 문제 발생: 시간 초과

위 코드에서 시간 초과가 발생했다.
이유를 분석해보면 다음과 같다.

🔴 시간 초과 원인

input()을 여러 번 호출

• input()은 호출할 때마다 표준 입력에서 한 줄을 읽고 처리하는데,
  이 과정이 반복되면 속도가 느려질 수 있다.
• 특히, 많은 데이터가 주어지는 경우 sys.stdin.read()를 이용하는 것이 훨씬 빠르다.

---

✅ 최적화: sys.stdin.read() 사용

위 문제를 해결하기 위해 빠른 입력 방법을 적용하였다.

import sys
from collections import Counter

a = sys.stdin.read().splitlines()  # 한 번에 입력을 모두 읽고 리스트로 변환
for key, value in sorted(Counter(a).items()):
  print(key, round((value / len(a)) * 100, 4))

✅ 개선된 점

• sys.stdin.read()를 사용하여 한 번에 모든 입력을 읽음 → 입력 속도 향상
• splitlines()를 사용하여 줄바꿈을 기준으로 리스트 변환 → 기존 방식과 동일한 데이터 구조 유지

---

⛔ 문제 발생: 오답 (틀렸습니다)

이번에는 시간 초과는 해결되었지만, 오답이 발생하였다.
이유를 살펴보니, round(%, 4) 함수의 동작 방식 때문이었다.

🔴 round() 함수의 문제점

• 파이썬의 round() 함수는 "은행가 반올림" (Bankers' Rounding) 방식을 따른다.
• 즉, 정확히 .xxxx5와 같은 값이 나올 경우, 가장 가까운 짝수 방향으로 반올림된다.

예를 들어:

print(round(2.5))       # 2  (짝수 방향으로 반올림)
print(round(3.5))       # 4  (짝수 방향으로 반올림)

따라서 문제에서 요구하는 정밀한 반올림 방식과 다를 수 있다.
즉, round()를 사용하면 정확한 결과를 출력하지 못할 가능성이 있다.

---

✅ 최종 해결 방법: 문자열 포맷팅 사용

import sys
from collections import Counter

a = sys.stdin.read().splitlines()
for key, value in sorted(Counter(a).items()):
  print(f"{key} {(value / len(a)) * 100:.4f}")

✅ f"{:.4f}"를 사용한 이유

• "{:.4f}".format() 또는 f"{:.4f}"는 반올림이 아닌 소수점 4자리까지만 유지하는 방식이다.
• 은행가 반올림을 피할 수 있어 정답을 정확히 출력할 수 있다.

---

📌 결론 및 정리

1. 입력 속도 개선
   • sys.stdin.read() + splitlines()를 사용하면 속도가 빨라진다.
2. round() 사용 금지
   • 파이썬의 round()는 문제의 요구사항과 다르게 동작할 수 있다.
3. 소수점 자리수를 정확히 맞추려면 f"{:.4f}" 사용
   • 반올림 문제가 발생하지 않고, 정확한 출력을 보장할 수 있다.