[코드트리] 완전탐색 - 등장하지 않는 문자열의 길이

코드트리 네이버 커리큘럼 - 완전탐색

• 등장하지 않는 문자열의 길이 (Python)
  https://www.codetree.ai/cote/14/problems/length-of-string-that-does-not-appear/description

Code

N = int(input())
str_input = input()
str_list = list(str_input)

checked = set()

double = []

cnt = 1
ans = 0

for i in range(N):
    for j in range(i, N):
        sub_str = str_input[i:j+1]      # 현재 위치에서 만들 수 있는 모든 부분수열 만들기

        if(sub_str not in checked):     # 해당 부분수열이 한번도 나오지 않았던 것이라면 -> 다음 비교를 위해 checked 집합에 추가
            checked.add(sub_str)
        else:                           # 해당 부분수열이 앞전에 이미 나온 것이라면 -> 길이값 업데이트
            ans = max(ans, len(sub_str)+1)

print(ans)

풀이 및 해설

• 연속부분문자열을 만들어서 → 기존에 있는거면 길이값 업데이트 , 기존에 없던거면 다음에 나올때를 위해서 저장해두기

정답 코드

• 연속하는 부분

n = int(input())
string = input()

ans = 1

# 1씩 늘려가면서 어느 길이까지 2번 등장하지는지 모두 시도해봅니다.
for i in range(1, n):
    # 모든 길이가 i인 부분 문자열에 대해 쌍을 짓고
    # 둘이 완전히 똑같은지 확인합니다.

    # twice : i 길이의 2회 이상 등장하는 부분 문자열이 존재하면 true
    twice = False

    for j in range(n - i + 1):
        for k in range(j + 1, n - i + 1):
            # issame : j부터 i길이의 부분 문자열과
            # k부터 i길이의 부분 문자열이 완전히 같으면 true
            issame = True

            for l in range(i):
                if string[j + l] != string[k + l]:
                    issame = False

            if issame:
                twice = True

    if twice:
        ans = i + 1
    else:
        break

print(ans)