[JAVA] 백준 1141. 접두사 :: 로직/코드 - GODZ

안녕하세요 GODZ입니다.

오늘은 문자열을 이용한 문제를 풀어볼 예정입니다.

---

1. 문제

사진을 클릭하면 문제  페이지로 이동합니다

 

2. 입출력 예제

 

3. 접근

[설명]

1. N개의 문자열의 집합에서 특정 문자열이 어떤 문자열의 접두사가 되지 않을 때, 그 집합을 접두사 X 집합이라고 한다. 또한 접두사 X 집합을 만족하는 가장 큰 집합을 만드는 게 관건이다.

2. 문자열의 수(N)가 최대 50, 문자열의 길이(M)가 최대 50이다.
   ---> 각 문자열을 이중 반복문으로 순회해도 O(N^2)이고, 문자열을 비교할 때 역시 O(M)이므로 결국 O(MN^2) = 125,000회 이내이다.

 

[로직]

1. 기준 문자열(origin)과 N-1개의 비교 문자열(comp)을 비교한다. 

2. origin의 길이가 comp의 길이보다 같거나 짧을 때만 비교한다.

   ---> origin의 길이가 더 길면 접두사가 당연히 될 수 없으므로 cnt++.

3. origin이 comp의 접두사가 아닐 때 cnt++.

4. origin이 comp와 접두사 관계가 아닌 경우의 수는 cnt이므로 cnt와 N-1이 같다면 origin은 어떤 문자열과도 접두사 관계가 아님.

 

[주의사항]

 문제에서 각 문자열이 모두 다르다는 전제 조건이 없기 때문에, 같은 문자열이 들어왔을 때의 로직을 따로 만들어야 한다.

 

[예시1 : 특정 문자열의 접두사가 되는 문자열이 중복일 때]

hi

hk

h

h

zh

---> 중복되는 문자열은 h이다. 이때는 h가 hi, hk의 접두사이기 때문에 기존 로직에서도 원하는 결과가 나온다.

(답 : hi, hk, zh)

 

[예시2 : 특정 문자열의 접두사가 되지 않는 문자열이 중복일 때]

hi

hi

hk

h

zh

---> 중복되는 문자열은 hi이다. 이때는 hi는 다른 hi의 접두사로 처리되므로 답에 hi가 제외된다.

(답 : hk, zh) (원하는 답 : hi, hk, zh)

---> 같을 때는 접두사 관계가 아닌 것으로 처리하면 된다. (아래 코드 line32 참고) 그러면 hi가 중복되어 카운트 된다. 중복을 허용하지 않는 자료구조 HashSet을 통해 중복되는 hi를 지워주면 된다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
 
public class Main {
    static int N;
    static String[] words;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        words = new String[N];
        
        // Input Strings
        for(int i = 0; i < N; i++) {
            words[i] = br.readLine();
        }
        
        Set<String> set = new HashSet<>();
        
        for(int i = 0 ; i < N; i++) {
            String origin = words[i];
            int cnt = 0;
            for(int j = 0; j < N; j++) {
                // If not same,
                if(i != j) {
                    String comp = words[j];
                    // origin이 같거나 짧을 때만 접두사가 되므로
                    if(origin.length() <= comp.length()) {
                        for(int k = 0; k < origin.length(); k++) {
                            if(origin.equals(comp)) {
                                cnt++;
                                break;
                            }
                            if(origin.charAt(k) != comp.charAt(k)) {
                                cnt++;
                                break;
                            }
                        }
                    } else {
                        cnt++;
                    }
                }
            }
            if(cnt == N - 1) {
                set.add(origin);
            }
        }
        System.out.println(set.size());
    }
}
 

 

5. 결과