[Java] 백준 풀기 11478 - 서로 다른 부분 문자열의 개수

자바 백준 11478번

실버 3

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

11478번: 서로 다른 부분 문자열의 개수

 

 

 

 

 

문제 보기

분류: 자료 구조, 문자열, 해시를 사용한 집학과 맵, 트리를 사용한 집합과 맵

 

 

 

 

 

문제 풀기

입력 받은 문자의 길이를 length() 로 확인하여 저장한다.

서로 다른 부분 문자열을 저장할 HashSet 을 생성한다.

 

이중 for loop 을 통해 문자열의 처음과 끝을 지정하여 substring() 으로 모든 경우에 대해 분리한다.

이 분리한 문자열을 HashSet<>() 으로 생성한 mySet 에 추가한다. HashSet 특성상 중복 추가에 대해서는 기록하지 않으므로 중복없는 모든 부분 문자열을 얻을 수 있다.

 

모든 for loop 이 완료되고 나면 size() 를 통해 그 개수를 찾고 return 하여 결과를 출력한다.

 

 

 

 

 

코드 보기

import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;

public class Main {
    
    public static void main (String args[]) {
        
        Scanner sc = new Scanner(System.in);
        
        String inputStr = sc.next();
        
        int count = countDistinctSubstrings(inputStr);
        
        System.out.print(count);  // "서로 다른 부분 문자열 개수"
    }
    
    
    public static int countDistinctSubstrings (String inputStr) {
        
        int n = inputStr.length();
        
        Set<String> mySet = new HashSet<>();  // 결과를 저장할 Set.

        // 모든 가능한 부분 문자열 생성.
        for (int i = 0; i < n; i++) {  // 문자의 시작 위치.
            for (int j = i + 1; j <= n; j++) {  // 문자의 끝 위치.
                String substring = inputStr.substring(i, j);  // 현재 loop 의 문자 추출.
                mySet.add(substring);  // 생성한 mySet 에 추가.
                // System.out.println(mySet);  // TEST PRINT
            }
        }

        return mySet.size();  // mySet 에 담긴 개수를 반환.
    }
    
}



/*
ababc

[a]
[a, ab]
[a, ab, aba]
[a, ab, aba, abab]
[a, ab, aba, ababc, abab]
[a, ab, aba, b, ababc, abab]
[a, ab, aba, b, ababc, abab, ba]
[a, ab, aba, b, bab, ababc, abab, ba]
[a, ab, aba, b, bab, ababc, babc, abab, ba]
[a, ab, aba, b, bab, ababc, babc, abab, ba]
[a, ab, aba, b, bab, ababc, babc, abab, ba]
[a, ab, aba, b, bab, abc, ababc, babc, abab, ba]
[a, ab, aba, b, bab, abc, ababc, babc, abab, ba]
[a, ab, aba, bc, b, bab, abc, ababc, babc, abab, ba]
[a, ab, aba, bc, b, bab, abc, c, ababc, babc, abab, ba]

12
*/