99클럽 코테 스터디 15일차 TIL [04/18]
[시작]
참여 기간 : 2025/03/31 ~ 2025/04/28
참여 난이도 : 파이썬 / 비기너
⏳ 코테 스터디 진행도 🧱 : [▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰ ] 15/29일 (52%)본 글에서 다룬 문제 : 백준 25325번 : 학생 인기도 측정
문제 푸는 데 걸린 시간 : 측정을 못했음. 30분 초과
내 풀이 : list.count(), dict, collections.Counter
처음 코드를 작성하고, 조금 더 간결하고 효율적인 코드 작성을 목표로 여러 번 수정했다.
그 결과 총 5개의 코드를 작성했다. (이 중 1개의 코드는 정렬을 잘못해서 틀렸다)
[오늘의 문제]
[문제 해석]
문제의 입력 부분을 먼저 보자.
첫 번째 줄에 학생 수 n이 입력되고
두 번째 줄에 n명의 학생 이름이 공백으로 구분된 문자열 A가 입력됨
다음 줄부터 n개의 줄에 걸쳐, 한 줄에 한 학생의 정보가 입력됨
학생 정보는 문자열 A에 나온 학생 순서대로 입력됨
한 명의 학생 정보는 해당 학생이 좋아하는 학생 이름이 공백으로 구분된 문자열로 입력됨
문제의 출력 부분을 보면
첫 번째 줄부터 n번째 줄까지 학생 이름과 해당 학생을 좋아하는 학생 수를 공백으로 구분하여 한 줄에 출력
정렬 순서는 인기도가 높은 학생부터 낮은 학생 순으로 출력하고
인기도가 같은 경우 학생 이름 기준으로 오름차순으로 출력
＃ 문제의 입력 출력과 예제 입출력만 잘 보면 어떤 코드를 작성해야 하는지 감을 잡을 수 있다.
[구현]
▶ 구현할 코드 흐름(입력)
- 첫 번째 줄에서 학생 수 n을 입력받는다.
- 두 번째 줄에서 n명의 학생 이름을 공백을 기준으로 나누어 name_list에 저장한다.
- 이후 n 줄에 걸쳐 각 학생이 좋아하는 친구들의 이름을 입력받고, 이를 한 줄씩 리스트로 받아 처리한다.
▶ 구현할 코드 흐름(로직)
- 학생 이름을 key로, 그 이름의 인덱스를 value로 가지는 딕셔너리를 만든다.
- 나중에 학생 이름을 바로 인덱스로 찾을 수 있게 하기 위해서!
- like_count 리스트를 만들어 각 학생의 좋아요 수를 저장한다.
- 이름 순서에 맞게 인덱스를 맞춰서 저장
- n 줄의 좋아요 데이터를 받아오고, 좋아요를 받은 학생의 인덱스를 찾아 like_count[index] += 1을 통해 수를 누적(카운트)
- name_list와 like_count를 묶어 (이름, 좋아요 수) 형태의 튜플 리스트 result를 생성한다.
- result 리스트를 다음 기준으로 정렬한다
- 좋아요 수가 많은 순 (내림차순, -x[1])
- 좋아요 수가 같을 경우 이름이 빠른 순서 (오름차순, x[0])
▶ 구현할 코드 흐름(출력)
- 정렬된 result 리스트를 순회하면서 "이름 좋아요 수" 형식으로 한 줄씩 출력한다.
[코드_첫 번째 시도]
import sys
input = sys.stdin.readline
def main():
n = int(input()) # 학생 수 입력 받기
name_list = input().split() # 학생 이름들을 리스트로 입력 받기
like_count = [0] * n # 각 학생이 받은 좋아요 수를 저장할 리스트
name_to_index = {} # 이름과 인덱스를 연결해주는 딕셔너리 생성
for i in range(n):
name_to_index[name_list[i]] = i # 예: 'aaa': 0, 'bbb': 1, ...
# 각 학생이 좋아하는 친구 목록을 받아서 좋아요 수 누적
for _ in range(n):
likes = input().split() # 해당 학생이 좋아하는 이름들
for liked_name in likes:
index = name_to_index[liked_name] # 좋아요 받은 학생의 인덱스
like_count[index] += 1 # 해당 학생의 좋아요 수 +1
result = [] # (이름, 좋아요 수) 쌍을 저장할 리스트
for i in range(n):
result.append((name_list[i], like_count[i]))
# 정렬: 좋아요 수 내림차순 → 이름 오름차순
result.sort(key=lambda x: (-x[1], x[0]))
# 결과 출력
for name, count in result:
print(name, count)
if __name__ == "__main__":
main()| 결과 | 메모리 | 시간 |
| 정답 | 32412 KB | 36 ms |
위에서 작성한 [구현할 코드 흐름]을 그대로 코드로 구현한 첫 번째 코드다.
제출 결과 정답이지만, 마음에 쏙 들지 않았다.
[코드_두 번째 시도]
첫 번째 코드를 간결화시켜 봤다.
변경된 내용은 다음 표와 같다.
| 비교 항목 | 첫 번째 코드 | 두 번째 코드 |
| 좋아요 수 저장 구조 | list 사용 + 이름-인덱스 딕셔너리 필요 | dict 하나로 바로 이름별 카운트 |
| 반복 구조 | 인덱스 변환 후 list에 count 누적 | 이름 기준으로 바로 count 증가 |
| 정렬 대상 | [(name, count)] 리스트 따로 구성 | dict.items() 바로 정렬 |
| 전체 코드 구조 | list + dict 조합 | dict만으로 간결화 |
import sys
input = sys.stdin.readline # 그대로 유지 (빠른 입력)
def main():
n = int(input()) # 학생 수 입력
names = input().split() # 학생 이름 리스트 입력
# 기존: like_count 리스트 + name_to_index 딕셔너리 2개 사용
# ✅ 개선 1: 딕셔너리 하나로 이름별 좋아요 수 저장
student_like_count = {name: 0 for name in names}
# 기존: 인덱스로 찾아서 list에 누적
# ✅ 개선 2: 이름으로 바로 dict에 접근해서 좋아요 수 증가
for _ in range(n):
likes_list = input().split()
for student in likes_list:
student_like_count[student] += 1 # 바로 이름 기준 누적
# 기존: (이름, 좋아요수) 리스트를 따로 만들고 sort()
# ✅ 개선 3: dict.items()를 바로 정렬 → 코드 간결
result = sorted(student_like_count.items(), key = lambda x: (-x[1], x[0]))
# 출력 구조는 기존과 동일 (이름 + 좋아요수 출력)
for name, count in result:
print(f"{name} {count}")
if __name__ == "__main__":
main()| 결과 | 메모리 | 시간 |
| 정답 | 32412 KB | 36 ms |
메모리와 시간은 달라지지 않았다.
[코드_세 번째 시도]
사람의 욕심은 끝이 없다.
더 간결하게... 더 간결하게 만들어보자
import sys
input = sys.stdin.readline
def main():
n = int(input())
name_list = input().split()
like_data = []
for _ in range(n):
likes = input().split()
like_data += likes # 전체 좋아요 모음 저장
for name in sorted(name_list):
print(name, like_data.count(name))
if __name__ == "__main__":
main()욕심을 냈지만, 출력 순서가 틀려서 오답이 되었다.
어디서 틀렸을까?
for name in sorted(name_list):
print(name, like_data.count(name))이 부분인데, 이 코드는 이름순 정렬만 하고 있어서 좋아요 수 높은 순서를 반영하지 못하고 있었다.
그래서 네 번째 코드에서 이를 수정했다.
[코드_네 번째 시도]
세 번째 코드에서 출력 순서 부분 오류를 수정했다.
변경된 내용은 다음 표와 같다.
| 비교 항목 | 두 번째 코드 | 네 번째 코드 |
| 좋아요 수 저장 | dict (Counter 역할) | like_data.count() |
| 이름 ↔ 위치 연결 | dict로 이름 직접 key로 사용 | 연결 필요 없음 |
| 좋아요 누적 방식 | dict 키 누적 | 리스트에 누적 후 .count() |
| 정렬 방식 | dict.items() 정렬 | name_list.sort() 정렬 |
| 속도 | 매우 빠름 | count()는 느림 |
import sys
input = sys.stdin.readline
def main():
# ✅ 개선 1: 딕셔너리도 없이 name_list와 like_data만으로 처리
n = int(input()) # 학생 수 입력
name_list = input().split() # 학생 이름 리스트 입력
like_data = [] # 좋아요 받은 이름들을 누적할 리스트
# ✅ 개선 2: for문으로 받은 좋아요 데이터를 리스트 하나에 전부 저장
for _ in range(n):
like_data += input().split() # 리스트 확장하며 누적
# ✅ 개선 3: 이름 리스트를 바로 정렬
# 좋아요 수를 기준으로 내림차순 정렬하고, 같으면 이름 오름차순 정렬
name_list.sort(key=lambda name: (-like_data.count(name), name))
# ✅ 개선 4: 정렬된 이름을 출력하면서, count()로 좋아요 수 표시
for name in name_list:
print(name, like_data.count(name)) # count()는 리스트 내 등장 횟수 세기
if __name__ == "__main__":
main()
.count()는 매번 리스트 전체를 순회하기 때문에 느리지만
코드의 길이와 이해도는 가장 쉽다.
데이터가 적고 직관적인 문제에는 적합함
나중에 더 어려운 문제는 .count() 사용이 부적절하지 않을까....
복잡한 자료구조 없이 간결하게 코드를 작성하고 싶어서 사용했다.
| 결과 | 메모리 | 시간 |
| 정답 | 33432 KB | 52 ms |
[코드_다섯 번째 시도]
진짜 마지막 코드
무슨 바람이 들어서 이렇게 여러 번 코드를 작성했을까? 글 적으면서 후회 중
변경된 내용은 다음 표와 같다.
| 비교 항목 | 네 번째 코드 | 다섯 번째 코드 |
| 좋아요 수 저장 | 리스트에서 .count() 호출 | Counter로 한 번에 계산 |
| 이름 ↔ 위치 연결 | 없음 | 딕셔너리 key로 바로 접근 |
| 좋아요 누적 방식 | 매번 리스트 순회 | 리스트 → Counter 1회 처리 |
| 정렬 방식 | 정렬 시 .count() 계속 호출 | 딕셔너리 값 바로 사용 |
| 속도 | 느림 (비효율적) | 빠름 (효율적) |
from collections import Counter # ✅ 개선 1: Counter를 사용해 좋아요 수를 한 번에 계산
import sys
input = sys.stdin.readline
def main():
n = int(input()) # 학생 수 입력
name_list = input().split() # 학생 이름 리스트 입력
like_data = [] # 좋아요 받은 이름들을 누적할 리스트
# 좋아요 데이터를 한 줄씩 받아서 리스트에 누적
for _ in range(n):
like_data += input().split()
# ✅ 개선 2: Counter를 이용해 각 이름이 몇 번 나왔는지 한 번에 세기 (딕셔너리처럼 동작)
count = Counter(like_data)
# ✅ 개선 3: 기존에는 count()를 매번 호출했지만, 이제는 딕셔너리처럼 바로 접근 가능
name_list.sort(key = lambda x: (-count[x], x)) # 좋아요 수 내림차순 → 이름 오름차순 정렬
# 출력 (이름 + 좋아요 수)
for name in name_list:
print(name, count[name]) # ✅ 개선 4: count[name] 으로 빠르게 접근
if __name__ == "__main__":
main()네 번째 코드에서 사용한 list.count() 코드는 구조는 단순하지만 느렸다.
이를 개선하기 위해 내장 모듈 collections.Counter을 사용했다.
Counter는 한 번의 순회로 모든 좋아요 수 계산이 가능하고 딕셔너리처럼 빠르게 접근 가능하다.
시간복잡도 또한 O(N) 정도로 네 번째 코드에 비해 개선되었다.
| 결과 | 메모리 | 시간 |
| 정답 | 34908 KB | 56 ms |
그런데 백준에 코드를 제출하면 오히려 다섯 번째 코드가 시간이 더 걸린다.
왜 그럴까. why??
| 항목 | list.count() 방식 | Counter 방식 |
| 소규모 데이터 | 빠를 수도 있음 | 약간 느릴 수도 있음 |
| 대규모 데이터 | 급격히 느려짐 | 일정하게 빠름 |
| 그럼 실전에선 어떤게 좋아? | 비효율적 | 효율적이라 따봉! |
(tmi 1)
Counter는 C로 구현된 내부 모듈이기에 내부적으로 딕셔너리를 생성하고 초기화하는 고정 오버헤드가 존재함
반면, list.count()는 단순 순회 연산이라 작은 데이터에선 더 빠를 수 있음(지금 이 문제처럼)
즉, 입력이 작으면 Counter 초기화 비용이 오히려 더 클 수 있음. 지금처럼
그리고 일반적으로 10ms 이내 차이는 "사실상 동일"로 판단한다고 함 ㅎㅎ...
(tmi 2)
파이썬 표준 라이브러리인 collections.Counter는 내부적으로 C 언어로 작성된 dict 타입을 기반으로 동작함
( Counter는 파이썬 코드지만, 내부 로직은 CPython 인터프리터가 C로 최적화해 처리함)
그래서 파이썬 코드보다 훨씬 빠르게 실행되는 거다~!
[다른 접근 방법]
이 문제 질려서 더 못 풀겠음...
시도해보진 않았는데 defaultdict(int) 사용해서 할 수도 있고
그냥 이중 for문으로 비교비교 하는 방법으로도 구현할 수 있음
근데 직관성은 Counter를 사용하는 게 제일 좋지 않을까?
이중 for문은 시간 복잡도 O(N^2)이 될 테고 그러니...
[회고]
오래간만에 시간을 많이 투자해서 여러 코드를 작성하고, 계속 개선시키려고 시도해 봤다.
힘들긴 하지만 같은 문제를 다른 방법으로 접근하면서
어떤 접근 방법이 효율적이구나 하는 것을 알 수 있었다. (Counter 사용)
다만 고민이 되는 것은 한 문제를 이렇게까지 여러 방법으로 풀어보는 것이 좋은지
이 시간에 다른 문제를 풀어보는 게 좋은지 모르겠다.
정답을 알려줘!