[백준] 5052번 전화번호 목록 (시간초과 해결과정)

문제 링크 - https://www.acmicpc.net/problem/5052

 

이 문제를 풀 때는 정말 쉽게 생각했다. 

정규표현식을 사용해서 비교하면 되겠는데? 하고 풀었더니 시간초과가 나왔다. 

그 다음에는 알고리즘 스터디 이 주의 주제였던 ChainHash를 사용해서 풀어보았다. 역시나 시간 초과를 했다.

해결하기 위해서 다양한 방법을 시도하고 정답을 맞춘 후에도 계속 다양한 방법을 시도해서 개선을 했다.

 

 

시간초과로 실패 목록

1. 직접 ChainHash 구현 정규표현식 사용해서 모두 비교
2. 직접 ChainHash 구현
   • 번호의 앞자리로 해시코드 생성 후 버킷에 담음
     ex) 1234 - table[1], 955 - table[9]
3. Sort 후 앞자리 같고 길이가 다르면 비교
   • 정규표현식으로 비교

 

해결 방법

• 실패의 가장 큰 이유는 Integer.parsInt로 첫자리를 정수로 바꿔서다. (그냥 문자로 비교) (그래도 BufferedReader > Scanner)
• 정규표현 대신 startsWith 사용
• 앞자리 추출방법 변경 split(" ")[0] -> charAt(0)

정리

1. 정렬을 하고 나면 이중 for문을 사용하지 않아도 된다.
2. 문자열에서 문자 하나만 얻을 때는 split(" ")[0] 보다 charAt(0) 이 더 빠르다. 2760ms -> 1704ms 로 향상
3. parsInst를 사용하면 속도를 많이 잡아먹는다.
4. startswith가 matches로 비교하는 것보다 아주 조금 더 빨랐다.

 

boolean check = true;
for (int i = 1; i < n && check; i++)
     check = !numbers[i].startsWith(numbers[i - 1]);

System.out.println(check?"YES":"NO");

 

 

1. 체인해시로 해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main {
    public static void check(ChainHash chainHash, String nums[]) {
        boolean check = false;
 
        for(String s : nums) {
            check = chainHash.search(s);
            if(check==true) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
 
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //테스트 케이스
        int t = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < t; i++) {
            // 숫자 개수
            int n = Integer.parseInt(br.readLine());
            ChainHash chainHash = new ChainHash();
 
            String[] nums = new String[n];
            for (int k = 0; k < n; k++) {
                nums[k] = br.readLine();
            }
            for(String s: nums)
                chainHash.add(s);
            check(chainHash, nums);
        }
    }
}
 
class ChainHash {
    private Node[] table;
 
    class Node {
        private String number;
        private Node next;
 
        public Node(String number,Node next) {
            this.number = number;
            this.next = next;
        }
 
        public String getnumber() {
            return number;
        }
 
        @Override
        public int hashCode() {
            return number.charAt(0)-'0';
        }
    }
 
    public ChainHash() {
        table = new Node[10];
    }
 
    public boolean search(String number){
        // 아스키코드 때문에 -'0'
        int hash = number.charAt(0)-'0';
        Node p = table[hash];
        while (p!=null){
            if(number.length()!=p.getnumber().length() && p.getnumber().startsWith(number)){
                return true;
            }
            p=p.next;
        }
        return false;
    }
 
    public void add(String number) {
        int hash = number.charAt(0)-'0';
        Node p = table[hash];
        while (p != null) {
            if (p.getnumber().equals(number))        // 이 키 값은 이미 등록됨
                return;
            p = p.next;                        // 다음 노드에 주목
        }
        Node temp = new Node(number, table[hash]);
        table[hash] = temp;                    // 노드를 삽입
        return;
    }
}

이렇게 해결을 하였고 다른 사람들은 어떻게 풀었나 확인을 해봤더니 왠걸?

내가 한 것보다 훨씬 짧고 속도도 훨씬 빨랐다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Quiz5052BySort {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
 
        while (t-- > 0) {
            int n= Integer.parseInt(br.readLine());
            String[] numbers = new String[n];
            for (int i = 0; i < n; i++)
                numbers[i] =br.readLine();
 
            Arrays.sort(numbers);
            boolean check = true;
            for (int i = 1; i < n && check; i++)
                check = !numbers[i].startsWith(numbers[i - 1]);
            System.out.println(check?"YES":"NO");
        }
    }
}

확인을 해보니까 먼저 정렬을 한 뒤에 startsWith로 풀었는데 정말 심플하고 완벽한 정답이었다. 

심지어 저기서 제출한 문제는 Scanner를 사용해서 1000ms지 BufferedReader를 사용하니까 500ms로 줄더라..

 

역시 알고리즘은 정답을 해결하는 것도 좋지만 다른 사람들이 풀이한 방식을 보고 비교해보고 개선해나갈 때가 더 많이 배우고 재미있는거 같다.