-
1593. [Python]문자 해독Python_알고리즘/Gold V 2023. 12. 28. 03:42
1. 문제
https://www.acmicpc.net/problem/1593
1593번: 문자 해독
첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 슬라이딩 윈도우
3. 파이썬 코드
g, s = map(int,input().split()) # 찾을 단어 find_word = input() # 비교할 단어 search_list = input() # 아스키 코드로 찾을 단어를 체크 current_list = [0] * 58 # 비교할 단어들의 아스키 코드값을 체크할 리스트 check_list = [0] * 58 # 순열이 몇개 존재하는지 체크할 변수 cnt = 0 # 시작 값 start = 0 # 길이를 체크할 변수 check_length = 0 # 찾을 단어의 아스키 값을 리스트에 저장 for i in find_word: current_list[ord(i)-65] += 1 # 비교할 단어를 반복문을 돌며 아스키 코드 값 체크 for i in search_list: check_list[ord(i)-65] += 1 # 아스키 코드값을 넣어준 후 길이를 +1 해줌 check_length += 1 # 만약 길이가 비교할 단어와 같은경우 if check_length == g: # 두 리스트가 동일하면 cnt 증가 if check_list == current_list: cnt += 1 # 비교를 진행하였으니 앞의 값의 아스키 코드를 -1 해줌 check_list[ord(search_list[start])-65] -= 1 # start 부분을 1씩 증가 후 길이는 -1 start += 1 check_length -= 1 print(cnt)
4. 문제를 풀고난 후 생각
- 처음 접근하는 방법으로 단어를 순회하며 아스키 코드 값의 합이 같은지를 체크해주는 방식으로 문제를 접근했다.
- 각 문자의 아스키 코드 값을 합치는 방식으로 접근하였더니 최악의 경우 3,000 * 3,000,000 의 반복횟수로 인해 시간초과가 나는 것을 생각이 났다.
- 해결하는 방법을 고민하던 중 너무 생각이 안나 다른 사람의 블로그를 참조하였다.
- 슬라이딩 윈도우라는 개념 자체가 아직 생소하다 보니 추후 정리 한번 해야할 것 같다.
위에 주석으로 간단한 설명을 적어뒀으니 추가적으로 설명을 그림으로 간단하게 첨부함
- 1, 2, 3, 4 에 해당하는 아스키 코드값을 각각 리스트에 저장이 되고 이 값들이 비교할 문자의 아스키 코드값들의 위치와 같은지 확인한다.
- 같으면 cnt가 증가하고 아니면 다른 조건없이 1번의 아스키 값을 빼주고 start가 가리키는 곳이 1에서 2로 바뀐다.
- 다음으로 5가 들어오게 되므로 다시 길이가 같아지게되며 위의 1, 2를 그대로 따라가고 이런 방식으로 값들을 비교해 나가며 cnt를 증가시키는 구조이다.
5. 문제를 푸는데 도움이 되는 지식
- 슬라이딩 윈도우
'Python_알고리즘 > Gold V' 카테고리의 다른 글
2023. [Python] 신기한 소수 (1) 2024.02.25 9205. [Python] 맥주 마시면서 걸어가기 (0) 2024.02.18 1263. [Python]시간 관리 (1) 2023.12.21 1490. [Python]자리수로 나누기 (0) 2023.11.01 1374. [Python]강의실 (0) 2023.10.30