-
1342. [Python]행운의 문자열Python_알고리즘/Silver I 2023. 12. 8. 01:45
1. 문제
https://www.acmicpc.net/problem/1342
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