백준 20291번 파일 정리 JAVA

링크텍스트

설명

풀이 흐름 설명

먼저 입력으로 주어진 파일 개수를 n만큼 반복하여 처리하였다.
각 파일 이름에서 .의 위치를 찾은 뒤 해당 위치 이후 문자열을 잘라 확장자만 추출하였다.
확장자는 HashMap<String, Integer>에 저장하여 개수를 누적하였다. 이때 getOrDefault()를 사용하여 기존 값이 없다면 0으로 초기화한 뒤 1 증가시키는 방식으로 구현하였다.

모든 입력 처리가 끝난 후에는 keySet()을 이용해 확장자 목록을 ArrayList로 옮겼다.
그 다음 Collections.sort()로 사전순 정렬을 수행하였다.
마지막으로 정렬된 확장자를 하나씩 순회하면서 확장자와 개수를 StringBuilder에 담아 출력하였다.

문자열 처리 방식에 대한 고민과 해결

확장자를 추출하는 방법은 두 가지를 고려하였다.
1. indexOf()와 substring()을 이용하는 방법
2. split()을 이용하는 방법

처음에는 split()을 사용하면 더 간단하게 token[1]로 접근할 수 있다고 생각하였다.
하지만 split()은 내부적으로 정규표현식을 사용하므로 단순한 문자 기준 분리임에도 상대적으로 비용이 더 크다는 점을 다시 확인하였다. 특히 "."은 정규표현식에서 모든 문자를 의미하므로 "\."처럼 이스케이프 처리가 필요하다는 점도 고려해야 한다.

반면 indexOf() + substring() 방식은 단순 탐색 후 잘라내는 구조이므로 오히려 더 가볍고 명확한 방법이었다. 따라서 이 문제에서는 indexOf() 방식이 더 적절하다고 판단하였다.

정렬 및 자료구조 선택

확장자의 등장 횟수를 세기 위해 HashMap을 사용하였다.
HashMap은 평균적으로 O(1)의 삽입 및 조회 성능을 가지므로 n개의 파일을 처리하는 데 효율적이다.

이후 정렬을 위해 keySet()을 ArrayList로 복사한 뒤 정렬하였다.
확장자 종류를 k라고 할 때, 정렬 비용은 O(k log k)이다.

만약 처음부터 정렬된 상태로 관리하고 싶다면 TreeMap을 사용하는 방법도 있다.
이 경우 삽입할 때마다 O(log k)의 비용이 발생하지만 별도의 정렬 과정이 필요 없다.
시간복잡도: O(NlogN), 공간복잡도: O(N)

회독

• [ x ] 1회
• 2회
• 3회

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());

        HashMap<String,Integer> hm = new HashMap<>();

        for(int i=0;i<n;i++){
            String s = br.readLine();
            
            int num = s.indexOf(".");

            s = s.substring(num+1);

            hm.put(s,hm.getOrDefault(s, 0)+1);
        }

        ArrayList<String> al = new ArrayList<>(hm.keySet());

        Collections.sort(al);

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<al.size();i++){
            sb.append(al.get(i)).append(" ").append(hm.get(al.get(i))).append("\n");
        }

        System.out.print(sb);
    }
}