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

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

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

접근 방법

• (런타임 에러)중복처리는 list로 처리
• (런타임 에러)이미 방문했다면 돌아가도록(백트래킹) 구현
• (해결) for 문으로 돌고, set 함수 사용

소스 코드 1, 2(RecursionError)

소스 코드 1: 91788083 제출

S = input()

# 초깃값 설정
visited = []

# 백트래킹 함수
def backtracking(index: int, track: str):
    if index == len(S):
        return

    track += S[index]
    if track not in visited:
        visited.append(track)  # 방문처리

    backtracking(index+1, track)    

# 백트래킹 실행
for idx in range(len(S)):
    backtracking(idx, "")

# 출력
print(len(visited))

• 백트래킹으로 방문처리를 해가면서 모든 경우의 수를 탐색
• 최대 문자열이 1000인데, 이때 RecursionError 발생

소스 코드 2: 91788610 제출

S = input()

# 초깃값 설정
visited = []

# 백트래킹 함수
def backtracking(track: str):
    if len(track) == 0:
        return

    if track not in visited:
        visited.append(track)

    backtracking(track[1:])
    backtracking(track[:-1])

# 백트래킹 실행
backtracking(S)

# 출력
print(len(visited))

• RecursionError를 해결하고자 반복 횟수를 줄이도록 구현
• 앞 또는 뒤의 문자를 하나씩 제거하면서 반복
• 이 또한 최대 문자열(1000)일 때 RecursionError 발생

소스 코드 3

소스 코드 3: 91788864 제출

S = input()

# 초깃값 설정
visited = set()

for start in range(len(S)):
    for end in range(start+1, len(S)+1):
        visited.add(S[start:end])

print(len(visited))

• 간단하게 for 문으로 반복하고, set 함수로 중복제거롤 해결

결론

• 최근 dfs나 백트래킹 문제를 풀어서 문제가 보이면 무작정 단정지어서 풀려는 경향이 생긴듯
• 문제의 알고리즘을 우선 판단하는 것을 잘하고 다음 단계를 준비해야할 것 같다.