백준 5052번: 전화번호 목록

문제 설명

• https://www.acmicpc.net/problem/5052
• 어떤 입력값이 다른 입력값의 접두어로 사용되는 경우가 있는지를 판단하는 문제입니다.

접근법

• 데이터를 문자열 순서로 정렬하면 접두어를 효율적으로 판단할 수 있습니다.
  • 정렬이 안된 {A,B,C,D}에서 A가 어딘가의 접두어로 사용되었는지를 판단하기 위해서는 A-B, A-C,A-D를 모두 비교해야 합니다.
  • 하지만 {A,B,C,D}가 정렬된 상태라면 A가 누군가의 접두어로 사용될 가능성은 오직 B에게만 존재합니다.

정답

import java.util.*;
import java.io.*;

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 t = 0; t < T; t++) {
			int N = Integer.parseInt(br.readLine());
			List<String> list = new ArrayList<String>(); // 496ms
//			List<String> list = new LinkedList<String>(); // 2796ms
			for (int i = 0; i < N; i++) {
				list.add(br.readLine());
			}
			Collections.sort(list);
			boolean flag = false;
			for (int i = 0; i < N-1; i++) {
				if(func(list.get(i),list.get(i+1))) {
					flag = true;
					break;
				}
			}
			if(flag) {
				System.out.println("NO");
			}else {
				System.out.println("YES");
			}
			
		}
	}

	public static boolean func(String now, String next) {
		int now_length = now.length();
		int next_length = next.length();
		if(now_length>next_length) return false;
		next = next.substring(0, now_length);
		if(now.equals(next)) return true;
		return false;
	}
}

기타

LinkedList vs ArrayList

• 해당 문제는 LinkedList와 ArrayList의 시간차이가 극명하게 납니다.
  • 
  • 그 이유는 ArrayList가 인덱스로 값에 접근하는 방식은 O(1)의 시간복잡도, LinkedList가 인덱스로 값에 접근하는 방식은 O(N)의 시간복잡도가 소모되기 때문입니다.
    • ArrayList는 메모리 주소를 바탕으로 값이 저장되기 때문에 주소값을 통해 한번에 값에 접근할 수 있지만
    • LinkedList는 순차적으로 값이 저장되기 때문에 Head부터 타고타고 들어가야 i번째에 도달할 수 있기 때문입니다. (내용출처: https://yeon-kr.tistory.com/152)