[백준] S4 20291 파일 정리 (java)

www.acmicpc.net/problem/20291

20291번: 파일 정리

 

풀이

 

1) TreeMap 을 생성

2) 입력값을 .을 기준으로 잘라서 뒷부분만 뽑아냄

3) 트리맵에 삽입.

3-1) 새로 들어오면 value = 1;

3-2) 이미 존재하면 value += 1;

4) 맵 출력

 

주의사항

 

1) 시간복잡도가 O(n^2)일 시 무조건 시간초과가 난다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.StringReader;
import java.util.Map;
import java.util.TreeMap;

public class BJ_S4_20291_파일정리 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(input.readLine());
		Map<String, Integer> map = new TreeMap<>();
		
		for(int n=0; n<N; n++) {
			String line = input.readLine();
			for(int i=0; i<line.length(); i++) {
				if(line.charAt(i) == '.') {
					String key = line.substring(i+1);
					if(map.get(key) == null) {
						map.put(key, 1);
					}else {
						map.put(key, map.get(key)+1);
					}
				}
			}
		}
		for(Map.Entry<String, Integer> entry : map.entrySet()) {
			output.append(entry.getKey()+" "+entry.getValue()+"\n");
		}
		output.close();
	}

	static String src =
			"8\r\n" + 
			"sbrus.txt\r\n" + 
			"spc.spc\r\n" + 
			"acm.icpc\r\n" + 
			"korea.icpc\r\n" + 
			"sample.txt\r\n" + 
			"hello.world\r\n" + 
			"sogang.spc\r\n" + 
			"example.txt";
}

 

 

후기

 

예전에 시간초과가 나고 잊혀진 문제를 이제서야 다시 풀어보았다.

문제를 보자마자 Map이 생각 났지만 (이전에는 리스트로 헛짓하면서 풀었더라..) Map을 어떻게 정렬하지? 라는 의문이 들어서 구글링을 해보았다.

결론은 TreeMap을 사용하는것이었고 저절로 Key에 대하여 알파벳 순으로 자동 정렬이 된다.

물론 역순으로 하려면 Comparable을 사용해야 하지만 이 문제는 그럴 필요가 없어서 냅뒀다.

다른 사람의 풀이를 보았는데 나와는 다르게 split으로 바로 문자열을 뽑는것을 보았다.

String[] fullName = br.readLine().split("\\.");
String tail = fullName[1];

이걸 보고 또 한번 배웠다. 이렇게 쉽게 자르는 방법이 있었다니..

또한 채점 결과를 보면 시간 차이가 많이 나는데 println과 BufferedWriter의 차이이다.

문자열 문제는 되도록.. 아니 그냥 모든 문제를 BufferedWriter로 풀는 습관을 가져야겠다.