[BOJ 1141] 접두사 (S1)

📍 문제

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

 

📍 문제 풀이

문제 이해를 위해 예시를 들어보자.

만약 입력이 아래와 같이 주어졌다면 어떻게 될까?

hi

hk

h

zh

 

이 경우에는 `h`가 `hi`, `hk`의 접두사이기 때문에 답은 { `hi`, `hk`, `zh` } 즉, 3이 나온다.

 

그래서 나 같은 경우에는 이중 반복문으로 리스트를 탐색하면서

한 단어가 다른 단어로 시작된다면 접두사임을 의미하기 때문에 결과에서 빼주는 식으로 진행했다.

이때 시작되는지 파악하는 부분에서 `startsWith`를 사용하지 않는다면 

`for문`과 `equals`를 통해서 확인해야하고 이 부분에서 시간초과가 나는 것 같다.라는 나의 예상..?

words.get(j).startsWith(words.get(i))

 

이때 결과값은 초기값이 `n`으로 지정되어 있어야한다.

 

📍 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class boj_1141 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		List<String> words = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			words.add(br.readLine());
		}
		Collections.sort(words);

		int result = n;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (words.get(j).startsWith(words.get(i))) {
					result--;
					break;
				}
			}
		}
		System.out.println(result);
	}
}

 

 

다풀고 다른 풀이 좀 찾아보니 다들 `set`을 사용하거나

`Comparator`사용해서 길이로 정렬을 했는데 그렇게해야하는 이유가 뭘까..

그냥 `sort`로만 진행해도 정렬되는거 아닌가?