boj 20291 : 파일 정리

문제 주소: https://www.acmicpc.net/problem/20291

난이도: silver 3

1.문제설명

• 파일들의 이름과 확장자가 주어진다

  "idecs.git" -> 요렇게

• 이때 확장자별로 몇개의 파일이 있는지 카운팅한 다음
• 확장자 이름의 사전순으로 확장자와 개수를 출력한다.

2.문제해결 아이디어.

• split으로 확장자와 이름을 분해해서 확장자만 저장
• 확장자를 count
• 이를 이름으로 정렬 하면 될꺼같다.

3.문제접근법

• 가장 처음 생각한 방법. (시간초과, 다시생각해봐도 시간복잡도 너무 손해 O(N) + O(N) +O(N^2) +O(NlogN))
  • 리스트에 확장자만 append하고
  • set에 다 추가해서
  • set 원소를 순회하면서 리스트에서 count하고 그 결과를 튜플로(확장자, 개수)로 리스트에 저장 후
  • sort한 다음에 출력
• Counter 사용
  • Counter 사용하면 dictionary 형식으로 그 아이템이 몇번있나 count해서 저장해줌
  • 이제 확장자 이름순으로 정렬해서 출력

4.특별히 참고할 사항

• Counter는 수업시간에 조교님이 설명해주셨는데 알아두면 좋은거같다.

5.코드구현

import sys
input = sys.stdin.readline
N = int(input())
from collections import Counter
files = []
for i in range(N):
    _, extension = input().rstrip().split('.')
    files.append(extension)
count_dict = Counter(files)
count = sorted(count_dict.items(), key = lambda x: x[0])
for item in count:
    print(item[0], item[1])