[백준] 단계별로 풀어보기(단계:12, 집합과 맵,JAVA)11478번, 서로 다른 부분 문자열의 개수

문제 링크

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

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은

1. 문자열에서 중복되지 않는 연속된 일부분의 개수를 결과로 출력합니다.

 

 

중복되지 않는 연속된 일부분인 S의 값을 저장할 HashMap<>을 만들었습니다.

 

완전 탐색을 통해 문자열에서 연속된 일부분이 나올 수 있는 경우를 모두 탐색합니다.

 

탐색할 때마다 처음 보는 연속된 일부분이면 HashSet<>에 저장하였습니다.

 

이후 모든 연속된 일부분을 탐색한 뒤 HashSet<>에 저장된 개수가 중복되지 않는 연속된 일부분이므로

 

HashSet<>에 크기를 결과로 출력하였습니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. S의 값들을 저장할 HashMap<> 만들었습니다.

2. 입력된 문자열에 연속된 일부분의 모든 경우를 탐색합니다.

3. 탐색할 때 처음 보는 연속된 일부분이면 HashSet에 저장합니다.

4. 모든 탐색이 끝난 뒤 HashSet에 크기를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 입력된 문자열에 대한 연속된 일부분의 모든 경우를 탐색합니다.
• 탐색할 때 해당 연속된 일부분이 처음인지 확인할 때 HashSet.contains()를 이용하였습니다.
• 처음이면 HashSet에 해당 연속된 일부분을 저장합니다.
• HashSet의 크기가 곧 S에 포함된 값들의 개수이므로 HashSet의 크기를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	String str = br.readLine();
    	HashSet<String> S = new HashSet<>();		//S값 저장할 HashSet
        //입력된 문자열에 대한 모든 경우 탐색
    	for(int i=0;i<str.length();i++) {
    		for(int j=i+1;j<=str.length();j++) {
    			String temp = str.substring(i, j);		//문자열 나누기
    			if(!S.contains(temp))		//처음 보는 연속된 일부분일 때
    				S.add(temp);		//HashSet에 추가
    		}
    	}
    	bw.write(S.size() + "\n");		//HashSet 크기 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
}