백준 11478번 풀이

문제

입력받은 문자열에서 서로 다른 부분 문자열이 몇 개인지 세면 된다.

Reference

https://reo91004.tistory.com/140

설마사카 이중 반복문으로 풀다니…

풀이

일단 부분 문자열이 뭐냐면 문자열의 일부분을 떼어낸 걸 말한다. 문제에 있는 ababc의 경우 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc 이렇게 열다섯개인데 여기서 중복 쳐내서 12개다. 파이썬은 set() 만들고 거기에 넣어두면 중복 알아서 쳐내니까 부분 문자열을 잘 골라내기만 하면 된다.

import sys



S = sys.stdin.readline().rstrip()

input()은 상관 없는데 sys.stdin.readline()으로 입력받을때는 반드시! 공백을 뗍시다… 안그러면 초유의 사태 터진다.

for i in range(len(S)):

    for j in range(i, len(S)):

        alphabet_set.add(S[i:j+1])

시간초과 뜰 줄 알았는데 저걸로 클리어가 될줄이야… 아무튼 이 반복문의 골자는 이렇다. i는 S의 길이만큼이기때문에 0부터 len(S)-1까지 생긴다. 그러면 j는 0부터 len(S)-1, 1부터 len(S)-1 이런 식으로 범위가 줄어들게 된다. 근데 뒤에 j+1은 왜 있냐고? ababa면 len(S)로 범위 잡았을때 길이가 5니까 0부터 4까지가 되는데, 여기서 j+1을 안하고 슬라이싱을 하게 되면 정말 핵 초유의 사태가 터지게 된다. 바로… 마지막 글자가 없어!!! 안잡혀!!! 슬라이싱도 m 이상 n 미만이라j가 4일때 [0:4]로 슬라이싱하면 0부터 3까지 나온다. 그리고 i가 범위인데 j 때려버리면 첫빠따에 공백 나오더라…

import sys



S = sys.stdin.readline().rstrip()

alphabet_set = set()



for i in range(len(S)):

    for j in range(i, len(S)):

        alphabet_set.add(S[i:j+1])



print(len(alphabet_set))

아무튼 set 만들어서 자른거 넣고 set 길이 출력하면 된다. 빈 세트 만든다고 {}쓰면 딕셔너리 되니까 set() 하십쇼.

아, 위에서 내가 sys.stdin.readline()은 반드시 공백인지 줄바꿈인지 아무튼 떼라고 했는데(strip() 혹은 rstrip()을 붙이면 된다) 안떼면 어떻게 되냐고?

이렇게요. 저건 예시에 있는건데

저기서 겹치는거 다 쳐내면 12개가 맞다. 안 떼고 걍 돌리면 위처럼 대참사 터지니까 반드시 strip()이나 rstrip()을 붙이고 그거 까먹음각 보이면 걍 인풋 쓰십쇼.