(Python/🥈1)백준 알고리즘 1342번: 행운의 문자열

728x90

문제 바로가기

문제:

민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다.

입력:

첫째 줄에 문자열 S가 주어진다. S의 길이는 최대 10이고, 알파벳 소문자로만 이루어져 있다.

출력:

첫째 줄에 위치를 재배치해서 얻은 서로 다른 행운의 문자열의 개수를 출력한다.

풀이:

permutations 를 사용한 코드인데 메모리 초과가 나온다.하나하나 다 돌려서 그런거 같다.

import sys
from itertools import permutations

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

lst = sys.stdin.readline()
sets = set()
for i in list(permutations(lst,len(lst))):
    N = "".join(i)
    flag = True
    for i in range(1,len(lst)):
        if N[i-1] == N[i]:
            flag = False
            break
    if flag:
        sets.add(N)
print(len(sets))

포문으로 전부 다 돌리는거 같아서

lst = sys.stdin.readline()
sets = set(list(permutations(lst,len(lst))))

형식으로 바꿔줬지만 실패

2.

딕셔너리로 키와 밸류로 바꿔주는 식으로 하는게 좋을것 같다. Counter 함수로 간단히 가능

N = list(map(str, sys.stdin.readline().strip()))
cnt = Counter(N)

import sys
from collections import Counter

def bt(temp,x):
    answer = 0
    # 길이를 다 채우면
    if x == len(N):
        # 성공하면 1 더해줌
        return 1

    for i in cnt.keys():
        # 이전 단어랑 같거나, 해당문자의 밸류값이 0 일때 (남은 글자 없으면 다음으로 넘어감)
        if i == temp or cnt[i] == 0:
            continue
        # 해당 문자 하나 빼고
        cnt[i] -= 1
        # 백트래킹 
        answer += bt(i, x+1)
        # 돌아와서 문자 뺀거 다시 넣어줌
        cnt[i] += 1

    return answer

N = list(map(str, sys.stdin.readline().strip()))
cnt = Counter(N)
print(bt("",0))