[백준] 5052번 : 전화번호 목록 / java - String, Hash 문제

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

5052번: 전화번호 목록

 

[ 코드 ]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        int T = Integer.parseInt(br.readLine());

        for (int tc=1; tc<=T; tc++) {
            int n = Integer.parseInt(br.readLine());
            
            String[] arr = new String[n];
            HashSet<String> set = new HashSet<>();
            boolean flag = true;

            for (int i=0; i<n; i++) {
                String s = br.readLine();
                arr[i] = s;
                set.add(s);
            }

            for (int i=0; i<n; i++) {
                for (int j=0; j<arr[i].length(); j++) {
                    if (set.contains(arr[i].substring(0, j))) {
                        flag = false;
                        break;
                    }
                }
            }

            if (flag == true) System.out.println("YES");
            else System.out.println("NO");
        }
	}
}

 

 

방법 1.

자기 자신을 substring으로

arr[i].substring(0, 0 ~ 자기자신의 길이-1)로 점점 늘려서 잘라가며 모든 HashSet에 있는 String과 비교

 

방법 2.

자기 자신을 기준으로

다른 것을 arr[j].substring(0, 자기 자신의 길이) 만큼 잘라서 이중 for문으로 비교

 

밑은 방법 2로 한 코드인데, 시간 초과가 났다!

 

 

 

[ 시간초과 코드 ]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        int T = Integer.parseInt(br.readLine());

        for (int tc=1; tc<=T; tc++) {
            int n = Integer.parseInt(br.readLine());
            boolean flag = true;

            String[] arr = new String[n];

            for (int i=0; i<n; i++) {
                String s = br.readLine();
                arr[i] = s;
            }

            for (int i=0; i<n-1; i++) {
                String me = arr[i];
                for (int j=i+1; j<n; j++) {
                    if (arr[j].length() >= me.length()) {
                        String prefix = arr[j].substring(0, me.length());
                        if (prefix.equals(me)) {
                            flag = false;
                            break;
                        }
                    }
                }
            }

            if (flag == true) System.out.println("YES");
            else System.out.println("NO");
        }
	}
}

 

 

※ 오늘의 교훈

테스트케이스 갯수를 잘 확인하고, 효율을 생각해 시간초과를 유의하자!