백준 20291 파일정리 (StringTokenizer 속도 good, split("정규표현식"))

https://www.acmicpc.net/problem/20291

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
//6:15
public class Solution {
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<String,Integer> map = new HashMap<>();
        List<String> key = new ArrayList<>();
        StringBuilder ans = new StringBuilder();
        N =Integer.parseInt(br.readLine());
        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine(),".");
            st.nextToken();
            String last = st.nextToken();
//            if(!key.contains(last)){
//                key.add(last);
//            }

            if(map.containsKey(last)){
                map.replace(last,map.get(last)+1);
            }
            else{
                key.add(last);
                map.put(last,1);
            }
        }
        Collections.sort(key);
        for(int i=0; i<key.size(); i++){
            ans.append(key.get(i)+" "+map.get(key.get(i))+"\n");
        }
        System.out.println(ans);

    }
}

로직은 맞았는데 타임아웃만 엄청나게 나던 문제이다.

 

잘 보면 list에서 contains는 앞에서부터 순회하면서 해당 데이터가 있는지 확인한다.

현재 0<N<50000 이라서 O(N^2)으론 안되고 O(NlogN)에서 끊어야한다.

 

하지만 만약 확장자가 전부 달라서 list에 계속 쌓이는거면 

매 시행마다 1 , 2 , 3 , ... , 50000 번 돌거라서 다 합하면 O(N^2)이 되어 시간초과가 발생한다.

 

 

따라서 이 부분만 다르게 로직을 바꿀 필요가 있는데...

보니까 key의 list는 map에서 put해줄때 같이 들어가면 된다. 즉 map 한번 따로 , key 한번 따로 해당 원소를 찾을 필요가 없다는 것이다.

따라서 해당 부분을 주석치고 key와 map 안에 같이 넣어주면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
//6:15
public class Solution {
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<String,Integer> map = new HashMap<>();
        List<String> key = new ArrayList<>();
        StringBuilder ans = new StringBuilder();
        N =Integer.parseInt(br.readLine());
        for(int i=0;i<N;i++){
            String s= br.readLine();
            int index = s.indexOf(".");
            String last= "";
            for(int j=index+1; j<s.length();j++){
                last+=s.charAt(j);
            }
//            if(!key.contains(last)){
//                key.add(last);
//            }

            if(map.containsKey(last)){
                map.replace(last,map.get(last)+1);
            }
            else{
                key.add(last);
                map.put(last,1);
            }
        }
        Collections.sort(key);
        for(int i=0; i<key.size(); i++){
            ans.append(key.get(i)+" "+map.get(key.get(i))+"\n");
        }
        System.out.println(ans);

    }
}

이 코드는 StringTokenizer 부분만 직접 index에서 순회해서 찾는 방법을 쓴것이다.

확실히 느리다. StringTokenizer로 받아오면서 이미 순회를 하는데 다시 순회하니까 속도 차이가 꽤 크게 난다.

 

마지막으로 기본 split("")로 해보았다.

split의 문제는 이것이다.

얘는 StringTokenizer(br.readLine(), "."); 처럼

split(".")로 하면 안된다.

split에서는 파라미터로 정규표현식 형태를 받고 StringTokenizer는 일반 문자를 받는다.

따라서 split은 정규표현식을 사용해야하므로 되도록이면 쓰지 말자. 속도도 StringTokenizer에 비해 느리다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
//6:15
public class Solution {
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<String,Integer> map = new HashMap<>();
        List<String> key = new ArrayList<>();
        StringBuilder ans = new StringBuilder();
        N =Integer.parseInt(br.readLine());
        for(int i=0;i<N;i++){
            String[] s = br.readLine().split("\\.");
            String last = s[1];
//            if(!key.contains(last)){
//                key.add(last);
//            }

            if(map.containsKey(last)){
                map.replace(last,map.get(last)+1);
            }
            else{
                key.add(last);
                map.put(last,1);
            }
        }
        Collections.sort(key);
        for(int i=0; i<key.size(); i++){
            ans.append(key.get(i)+" "+map.get(key.get(i))+"\n");
        }
        System.out.println(ans);

    }
}

아래서부터 첫번째는 StringTokenizer, 2번째는 .의 index 기준 반복 돌림 , 3번째는 split 사용