[JAVA] 백준 5052 - 전화번호 목록

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

특정 전화번호 전체가 다른 문자열의 Prefix인 경우가 있는지를 확인하는 문제이다.

전화번호 10000개에 대해서 각각 String.StartWith 함수를 쓰는 방식으로 구현한다고 생각하면 10000*10000*startWith함수 시간복잡도니까 시간초과가 발생할 거라고 생각하고 시도도 하지 않았다.

그렇게 고민하다가 점점 이상한 방향으로 생각이 흘러가게 됐다.

JAVA stream API의 groupingby로 그룹핑 조건 문자열의 길이를 점점 늘려가면서 혼자 그룹핑된 문자열을 리스트에서 지워가며 list size가 0이 될때까지 반복할 때 아무리 문자열의 길이를 늘려도 list의 size가 0으로 줄어들지 않다가 결국 indexoutofboundException이 발생한다면 한 문자열이 다른 문자열의 prefix인 관계가 아닌가 라는 생각을 하게 되었고

그렇게 구현했는데 성공했다.

exception을 ps에서 사용하는 건 지양해야겠다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for (int i = 0; i < tc; i++) {
            List<String> list = new ArrayList<>();
            int numbers = Integer.parseInt(br.readLine());
            for (int j = 0; j < numbers; j++) {
                String s = br.readLine();
                list.add(s);
            }
            Collections.sort(list);
            AtomicInteger atomicInteger = new AtomicInteger(1);
            boolean flag = false;
            while(list.size()>1){
                try{
                    Map<String, List<String>> map = list.stream().collect(Collectors.groupingBy(s->s.substring(0,atomicInteger.get()), Collectors.toList()));
                    atomicInteger.incrementAndGet();
                    list = map.keySet().stream().filter(x->map.get(x).size()>1).flatMap(x -> map.get(x).stream()).collect(Collectors.toList());
                }catch (StringIndexOutOfBoundsException e){
                    flag = true;
                    break;
                }
            }
            System.out.println(flag?"NO":"YES");
        }
    } 
}

 

GPT말로는 트라이 자료구조 안써도 정렬 후 인접 문자열에 대해서만 검사해도 된다고한다.

난 이 문제가 유독 테케가 적어서 성공한 것 같은 느낌이다.