[python_파이썬]백준_11478번_서로 다른 부분 문자열의 개수_풀이

공부하는허딩크 : https://www.youtube.com/live/0PBsmU7Tfk4?feature=shared

보기보다 쉽지 않은 문제다.

"일단 연속된 일부분"이라는 단어에 주목해야 한다. => 이게 아니면 실버등급의 문제가 아닌듯...

 

즉, combinations조합으로 모든 조합을 뽑아내는것이 아니라, 연속된 글자여야 한다는 것이다.

 

<첫번째 시도 : 제출하지도 않았음_중간에 코드의 방향잡으려고만 함>

combinations로 쉽게 조합을 가져 올 수 있을 것으로 예상했으나 아예 방향을 잘못 잡음.

import sys

import itertools

input = sys.stdin.readline

S = input().strip()

s = set()

for i in range(1, len(S) + 1):

    s.add(itertools.combinations(S, i))

for i in s:

    print(list(i))

 

<두번째 시도 : 맞았습니다.>

import sys

import itertools

input = sys.stdin.readline

S = input().strip()

s = set()

for i in range(len(S)):

    for j in range(1, len(S)+1):

        s.add(S[i:j])

cnt = 0

for i in s:

    if i:

        cnt += 1

print(cnt)

일단 중복을 허용하지 않기 때문에 s = set()으로 초기화 한 후 슬라이싱으로 문자열을 조건대로 올 수 있도록 코드를 작성하였다.

처음에는 이중for문으로 하면 시간초과를 걱정해서 다른 코드를 고민했으나 일단 내가 생각할 수 있는 최선이 이중for문이었다.

S[i:j]의 조건을 주기 위해 아래와 같이 고민했다.

결과가 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 나와야 함으로

01, 12, 23, 34, 45

02, 13, 24, 35

03, 14, 25

04, 15

05

이렇게 슬라이싱 숫자가 나와야 하는데 조합을 오른쪽 방향으로 순서를 고민할때 i와 j의 조합이 보이지 않았다.

몇번 그려볼때 위에서 아래의 순으로 조합이 그려질 것 같은 느낌이 있어 그려보았다.

i = 0일때 j = 1, 2, 3, 4, 5

i = 1일때 j = 2, 3, 4, 5

i = 2일때 j = 3, 4, 5

i = 3일때 j = 4, 5

i = 4일때 j = 5가 나오면 되는데 

j의 범위를 range(len(S))로 줘도 어차피 i보다 작거나 같을때는 무시하기 때문에 조건이 만족할 것 같았다.

여기서 문제가 결과 s의 결과가 {'', 'ab', 'babc', 'aba', 'ababc', 'c', 'a', 'abab', 'abc', 'bc', 'ba', 'b', 'bab'}가 나왔다.

즉, 빈칸이 나와서 len(s)로는 13이 되어서 다시 for문으로 빈칸이면 무시하는 조건을 줘서 12를 만들어 냈다.

※여기서 ''가 1개 나오는 이유는 i보다 작거나 같을때는 ''로 나오는데 이게 중복이 안되니까 1번만 나오는 것!!!!!

 

<세번째 시도 : 맞았습니다. -100ms>

''가 무조건 1개는 있을 것으로 예상해서 len(s)에서 -1해주고 바로 출력.

S = input().strip()

s = set()

for i in range(len(S)):

    for j in range(1, len(S)+1):

        s.add(S[i:j])

        print(i, j, S[i:j])

print(len(s)-1)

 

<네번째 시도 : 맞았습니다. + 32ms>

이중for문 안에 if문으로 비어있으면 false로 아예 조합으로 가지 않게 작성.

import sys

import itertools

input = sys.stdin.readline

S = input().strip()

s = set()

for i in range(len(S)):

    for j in range(1, len(S)+1):

        if S[i:j]:

            s.add(S[i:j])

print(len(s))

 

<다섯번째 시도 : 시간 초과를 예상했으나..... 맞았습니다.?>

리스트를 사용해도 상관 없네??속도도 2번째 코드보다 빠름 (700ms -> 644ms)

import sys

import itertools

input = sys.stdin.readline

S = input().strip()

s = []

for i in range(len(S)):

    for j in range(1, len(S)+1):

        if S[i:j]:

            s.append(S[i:j])

print(len(set(s)))

 

<다른사람코드 참조>

1. 조건을 i => range(len(S)), j => range(i, len(S))를 주고 S[i : j + 1]로 해도 가능함 => 나도 몇번 고민했는데 이게 생각이 안남....젠장....

2. 조건을 i > range(len(S)), j => range(len(S) - i)를 주고 S[j:(j + i) + 1]로 해도 가능함

   ㄴ 여기서 문자열 슬라이싱은 out of range가 발생하지 않고 문자열이 있는 부분만 읽는다.