백준 - 6443

KangMyungJoe·2023년 4월 24일

목록 보기

24/55

문제 설명

입력받은 영단어의 각 알파벳을 이용해 가능한 모든 경우를 출력하는 문제이며, 입력받은 영단어에 동일한 알파벳이 있는 경우 같은 경우가 출력될 수 있는데, 이를 방지해야 한다.

접근 방식

다른 풀이는 접근 법이 생각나지 않아 backtracking 방식으로 접근했다.

영단어의 알파벳을 분리해 리스트 형태로 만든 뒤, 정렬과정을 거쳐 출력이 오름차순으로 나올 수 있게끔 했다.

처음엔 시간을 고려하지않고, 가능한 모든 경우의 수의 출력까지 구한 뒤 그 값이 있는 경우에 출력하지 않는 식으로 코드를 작성했는데, 이러한 과정에서 시간초과가 발생했다.

다른 기타 블로그를 참고했을 때, 딕셔너리 형태의 visit을 생성하여 내가 쓸 수 있는 알파벳의 개수를 기억하는 것이 좋아보였고, 이를 적용했다.

기존 백트래킹 방식은 배열에 값 넣기 -> 재귀 호출 -> 배열 값 빼기와 같은 방식으로 이루어졌었는데, 이번 문제는 반대로 진행되는 점이 참신했다.

작성한 코드

실패한 코드 (시간초과)

import sys

input = sys.stdin.readline

n = int(input())
result_list = []
def back(str_list, visit, cnt, result):
    
    if cnt == len(str_list):		
        if result in result_list: # 수행시간 초과 예상
            return
        result_list.append(result)
        print(result)

    for i in range(len(str_list)):
        if visit[i] :
            continue
        visit[i] = 1
        back(str_list, visit, cnt + 1, result + str_list[i])
        visit[i] = 0


for i in range(n):
    string = list(input().rstrip())
    string.sort()
    visit = [0 for _ in range(len(string))]     
    back(string, visit, 0, '',)

정상적으로 수행되는 코드지만, 중복된 값을 출력하지 않기 위해 출력 전 한번 검사하는 곳에서 수행시간의 초과가 나타나는 듯 하다.

수정 코드

import sys
input = sys.stdin.readline

def back(cnt):
    print(cnt, ans)
    if cnt == len(string):
        print("".join(ans))
        return
    for k in visit:
        if visit[k] :   # 딕셔너리에 값이 있으면
            visit[k] -= 1   # 빼고, ans에 추가
            ans.append(k)
            
            back(cnt+1)     # 재귀
            
            visit[k] += 1
            ans.pop()

n = int(input())

for i in range(n):
    string = sorted(list(input().rstrip()))
    visit = {}
    ans = []            # 출력에 필요한 배열

    for i in string:    # 알파벳의 개수를 입력
        if i in visit:
            visit[i] += 1    
        else:
            visit[i] = 1
    
    back(0)