[Baekjoon] 1593번: 문자 해독 (python)

https://www.acmicpc.net/problem/1593

1593번: 문자 해독

c++으로 풀었던 문제를 python으로도 풀어봤다

 

https://ggsing.tistory.com/35

[Baekjoon] 1593번: 문자 해독(c++)

 

w를 순열으로 문제를 풀게된다면 입력이 3000! 까지라서 시간초과 문제가 생긴다.

그래서 슬라이딩 윈도우 방식으로 기존 크기에서 오른쪽으로 1칸씩 옮겨서 비교하는 방법으로 구현했다.

 

예시에서 주어진 것으로 보면

4 11
cAda
AbrAcadAbRa

 

1. arr의 모든 객체 요소가 0일때, result+1을 해줌

2. arr객체 요소를 입력된 문자 개수만큼 +1

3. 맨 처음 한번은 0~3만큼 s[i] 문자에 대하여, arr[s[i]] - 1 을 해줌

      - 해당 예시에서는 ( arr[A] = 0, arr[b] = 0, arr[r] = 0, arr[A] = -1 ) 

      - s[i]는 w안에 있는 문자의 경우에만 계산해줌. arr[b] 와 arr[r]은 계산할 필요 없어서 제외시켰음

4. 0부터 s문자길이-w문자길이 만큼 반복. 예시에서는 0~7까지 반복문 시작

      - 현재 구간 0~3 에서 왼쪽 문자 1개 제외. 1~3구간에서 제외된 문자 arr[s[left]] + 1 (예시에서는 arr[A] + 1)

      - 현재 구간 1~3에서 오른쪽 문자 1개 추가. 1~4구간에서 추가된 문자 arr[s[right]] - 1  (예시에서는 arr[c] - 1)

      - 현재 구간 1~4에서 arr의 모든 요소가 0인지 확인 후 맞으면 result+1 (comp의 모든요소가 0이므로, comp와 비교함)

 

 

**처음 객체 할당할 때, 문자의 개수만큼 +1을 해줘야 

3 3
aaa
aaa 

이런 예시가 들어왔을 때, a = 0 을 만족시킬 수 있다.

처음엔 초기화를 그냥 arr[i] = 1 으로 해줬더니 arr[a] 가 -2 로 되버려서 comp객체와 일치하지않아서.. result+1이 안돼서 계속 틀렸다.

for i in w:
    arr[i] = 0
    comp[i] = 0

for i in w:
    arr[i] = arr[i] + 1

 

---

python코드

import sys

W, S = map(int, input().split())
w = sys.stdin.readline().strip()
s = sys.stdin.readline().strip()

result = 0
sum = 0
left = 0
right = len(w)

#객체 할당
arr = {}
comp = {}
for i in w:
    arr[i] = 0
    comp[i] = 0

for i in w:
    arr[i] = arr[i] + 1            

# 객체원소가 모두 0이면 result+1
def chk():
    global sum, result
    if arr == comp:
        result = result+1

# 처음 한번만
for i in range(left, right):
        if s[i] in w:
            arr[s[i]] = arr[s[i]] - 1            
chk()
                         
# right+1 전에 맨 앞. left에 있는 글자 하나씩 빼주기
# 오른쪽 글자를 더할때는 -1, 왼쪽부터 빼줄때는 +1
for k in range(0, len(s)-len(w)): 

    if s[left] in arr:
        arr[s[left]] = arr[s[left]] + 1
    
    if s[right] in arr:
        arr[s[right]] = arr[s[right]] - 1   
        
    chk()
    
    left = left + 1
    right = right + 1
    
print(result)

---

​