-
1544. [Python]사이클 단어Python_알고리즘/Silver IV 2023. 5. 15. 22:17
1. 문제
https://www.acmicpc.net/problem/1544
1544번: 사이클 단어
사이클 단어는 어떤 단어를 원형 모양으로 차례대로 쓴 것이다. 따라서, 어떤 단어를 이렇게 쓴 후에 임의의 단어를 고른다. 그 후에 시계방향으로 차례대로 읽으면 그 것이 단어가 된다. 만약에
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 브루트 포스
- 정렬
3. 파이썬 코드
N = int(input()) # 문자를 저장할 리스트 word_list = [] # 문자열 저장 for _ in range(N): word_list.append(input()) # 최종적으로 사용할 리스트 total_list = [] # 리스트의 문자를 한개씩 반복해가는 반복문 for i in word_list: # 문자열의 모든 숫자를 번갈아가며 모든 경우의 수의 문자를 저장할 리스트 middle_list = [] # 문자열의 처음부터 끝까지 반복 for j in range(len(i)): # 0~끝 1~끝 2~끝 이런식으로 더해나감 word = i[j:] + i[:j] # 중간 리스트에 순회하는 문자를 저장 middle_list.append(word) # 중간리스트를 정렬 middle_list.sort() # 최종적인 리스트에 중간리스트 저장 total_list.append(middle_list) # 최종리스트를 set으로 중복처리를 해줘서 다른 문자열의 갯수를 파악 total_list = set(map(tuple,total_list)) print(len(total_list))
4. 문제를 풀고난 후 생각
- 문자에서 중복이 있는지 없는지를 파악하기 위해서 한 문자를 가지고 만들 수 있는 모든 문자의 경우의수를 생성하여 리스트로 묶어서 저장을 하는 방식으로 해결했다.
- "picture" 과 "turepic"는 같은 문자이지만 이걸 어떻게 비교를 하는지에 대해서 고민을 했었고 두 단어로 만들 수 있는 모든 문자를 리스트로 저장한 후 정렬을 진행하여 저장을 해두면 최종적으로 구하는 곳에서 처리를 해주면 되기 때문에 리스트를 생성하여 모든 경우의 수를 만들어줬다.
- 이후 2차원 리스트로 구성되었기 때문에 set 처리를 하기 위해서는 map 함수를 사용하여 2차원 리스트 내부의 리스트를 튜플로 변경해준 후 set처리를 진행하였다.
- set 처리를 진행하고 난 후 남은 리스트는 중복되지 않은 문자열들로 나올 수 있는 문자들이기 때문에 그 길이를 구해주면 답이 된다.
5. 문제를 푸는데 도움이 되는 지식
- 브루트 포스
- 정렬
'Python_알고리즘 > Silver IV' 카테고리의 다른 글
1015. [Python]수열 정렬 (0) 2023.05.28 1057. [Python]토너먼트 (2) 2023.05.16 2090. [Python]조화 평균 (0) 2023.05.14 1758. [Python]알바생 강호 (0) 2023.05.11 1487. [Python]물건 팔기 (0) 2023.05.04