[Java] 백준(실버-3) 11478번 - 서로 다른 부분 문자열의 개수

문제 풀이

---

주어진 문자열에서 부분 문자열을 탐색해가며 서로 다른 부분 문자열의 개수만 세어야 한다.
서로 다른 부분 문자열만 센다는 것은 중복되는 부분 문자열은 세지 않는다는 것과 동일하다.

아이디어 도출

• 주어진 문자열 S의 모든 부분 문자열이 만들어지는 경우를 탐색하며 부분 문자열을 구한다.
• 구한 부분 문자열을 HashSet에 저장해가며 중복을 제거한다.

이중 for문 안에서 부분 문자열을 구하는 과정을 살펴보면 다음과 같다.

S = "ababc"

i=0,
    j=0 -> a
    j=1 -> ab
    j=2 -> aba
    j=3 -> abab
    j=4 -> ababc
i=1,
    j=1 -> b
    j=2 -> ba
    j=3 -> bab
    j=4 -> babc
i=2,
    j=2 -> a
    j=3 -> ab
    j=4 -> abc
i=3,
    j=3 -> b
    j=4 -> bc
i=4,
    j=4 -> c

위와 같이 부분 문자열이 만들어지는 경우를 모두 돌며 부분 문자열을 만들고, 만들어진 부분 문자열을 HashSet에 저장하면, 중복없이 서로 다른 문자열만이 남아있을 것이다.

그럼 코드로 작성해보자.

String S = br.readLine();
HashSet<String> set = new HashSet<>();

문자열 S를 입력받고 부분 문자열의 중복을 제거할 HashSet을 하나 선언하자.

for(int i=0; i<S.length(); i++) {
    String str = "";
    for(int j=i; j<S.length(); j++) {
        str += S.substring(j, j+1);
        set.add(str);
    }
}   

bw.write(set.size()+"\n");

그리고 이중 for문으로 문자열 S를 순회화며 위 예시와 같이 부분 문자열이 만들어지는 경우를 탐색하여 부분 문자열을 구한다.
구한 부분 문자열을 HashSet에 저장해나가면, 서로 다른 부분 문자열만 HashSet에 저장된다.
문제 요구사항은 서로 다른 부분 문자열의 개수이니, HastSet의 size를 출력해주면 정답을 낼 수 있다.

작성코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String S = br.readLine();
        HashSet<String> set = new HashSet<>();

        for(int i=0; i<S.length(); i++) {
            String str = "";
            for(int j=i; j<S.length(); j++) {
                str += S.substring(j, j+1);
                set.add(str);
            }
        }   

        bw.write(set.size()+"\n");

        bw.flush();
        bw.close();
        br.close();
    }   
}

회고

• 이중 for문을 통해 부분 문자열을 구하는 과정이 조금 헷갈렸지만, 중복을 제거할 수 있는 HashSet은 바로 생각이 났기애 솔루션 코드에 접목할 수 있었다.