백준 11478번: 서로 다른 부분 문자열의 개수 with Java

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

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

30742

19194

15491

63.108%

문제

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.

부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.

예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

출력

첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.

예제 입력 1 복사

ababc

예제 출력 1 복사

12

 

 

---

 

 

문자열 s가 주어졌을 때, s의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오...............

길이는 1000 이하...

 

그냥 String으로 받는다면 얘를 어떻게 쪼개야 하지? 공백이나 뭐 기준이 있으면 split 쓰면 되는데(파이썬이랑 헷갈리나 하고 황급히 검색했는데 다행히 java에도 split 있었다) 

 

BufferedReader가 더 빨라 알고리즘 문제를 풀 때는 BufferedReader 사용을 더 권장

 

...딴 거 검색하다가 이거 찾음 그렇다고 합니다. BufferedReader 사용을 배워야겠다.

일단 지금은... PASS ㅎ

 

그러니까 이게 문자열을 따로 조합하면 안 되고 붙어있는 것만 허용한다는 거지...

일단 자러 가야겠다

 

 

아오 피곤해죽겟네 지금 또 새벽이네 갱이 코드 보다가 왔는데 CORS에러가 여기서도? 진짜 못하겠다

 

그래 일단 부분 문자열인데 근데 중복은 빼고 해야 한다는 말이자ㅑㄶ아

그러면 이걸 부분 문자열을 다 저장한 담에 중복 확인을 해야 해? 메모리 낭비 같기도 하고.. 근데 저장을 안 하면 어떻게 중복 확인을 하지 파이썬은 집합 쓰면 될 것 같은데 -> 검색해보니까 자바도 있네여..

 

거의 자면서 쓴 첫 코드

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class BJ_11478 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String s = sc.next();	// String으로 문자열 s 입력
		char[] sArray = s.toCharArray();	// 캐릭터 배열로 변환
		
		Set<String> set = new HashSet<String>();	// 중복 안 되게 저장하려고 set으로 설정
		for (int i = 0; i < sArray.length; i++) {
			String tmp = "";
			tmp += sArray[i];
			set.add(tmp);
			for (int j = i + 1; j < sArray.length; j++) {
				tmp += sArray[j];
				set.add(tmp);
			}
		}
		
		System.out.println(set.size());
		
		sc.close();
	}
}

 

 

??????????????????????????

뭐지

맞은 게 더 신기해

역대급 시간이어서(진심 1초에 1%씩 올라갔음) 당연히 안 되겠구나~ 했는데 맞은 게 더 신기하네

이게..도네? 진짜 넘 피곤해서 일단 이걸루 끝... 낼 다시 볼게여 ㅎ