-
1342. [Python]행운의 문자열Python_알고리즘/Silver I 2023. 12. 8. 01:45
1. 문제
https://www.acmicpc.net/problem/1342
1342번: 행운의 문자열
민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초 (Python 8초)
- 메모리 제한: 256MB
- 브루트포스
- 백트래킹
3. 파이썬 코드
def backtracking(current): global cnt # 현재 값이 시작인경우 ans 리스트에 값을 한개씩 추가해 나가며 방문했는지 체크 if current == 0: for i in range(word_length): ans.append(word[i]) visited[i] = True backtracking(current + 1) visited[i] = False ans.pop() else: # 만약 리스트 길이와 같으면 리스트를 set에 저장 if current == word_length: check = "".join(ans) answer_list.add(check) return # 0부터 리스트 길이까지 반복문을 진행하며 방문했는지 이전값이랑 같은지 체크 조건에 맞으면 백트래킹 for i in range(word_length): if word[i] != ans[-1] and not visited[i]: ans.append(word[i]) visited[i] = True backtracking(current + 1) visited[i] = False ans.pop() word = input() word_dict = {} ans = [] answer_list = set() cnt = 0 word_length = len(word) visited = [False] * word_length current = 0 backtracking(current) print(len(answer_list))
4. 문제를 풀고난 후 생각
- 모든 자리에서 문자를 한개씩 넣어보며 다른지 아닌지 판단을 해야하는 문제이다.
- 방문처리 및 이전 문자랑 같은지 체크를 통해서 최소한의 가지수를 줄이긴 했지만 그래도 시간초가 많이 나오게 된다.
- 여기서 좀 더 줄일 수 있는 방법은 모든 문자가 다른경우를 소거할 수 있을 것 같다.
5. 문제를 푸는데 도움이 되는 지식
- 브루트포스
- 백트래킹
'Python_알고리즘 > Silver I' 카테고리의 다른 글
1946. [Python]신입 사원 (0) 2023.12.19 1926. [Python]그림 (0) 2023.12.09 1421. [Python]나무꾼 이다솜 (2) 2023.12.07 1527. [Python] 금민수의 개수 (0) 2023.08.30 2667. [Python]단지번호붙이기 (0) 2023.06.04