백준 12891, 11003

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

12891번: DNA 비밀번호

<내풀이>

n, m =map(int,(input().split()))
S= input()

# 각 문자와 최소 갯수를 딕셔너리로 셋팅
D = {'A':0, 'C':0, 'G':0, 'T':0}
D['A'], D['C'], D['G'], D['T'] = list(map(int,(input().split())))

# 포인터는 m의 간격을 유지하면서 옮긴다.
i = 0
j = i + m
count = 0

# 각 문자를 카운트 했을 때의 숫자가 최소 충족해야하는 숫자보다 큰지 확인 후 카운트
while j < n+1:
    if D['A'] <= S[i:j].count('A') and D['C'] <= S[i:j].count('C') and D['G'] <= S[i:j].count('G') and D['T'] <= S[i:j].count('T') :
        count += 1
    i += 1
    j += 1
print(count)

> 이번 내용도 포인터를 이용해서 풀어나갔습니다. 주어진 문자열 S에서 i와 j를 m의 간격으로 세팅해두고 같은 간격으로 포인터를 옮겨가며 조건에 맞게 카운트 해줬습니다.

 

<덱의 구조>

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

11003번: 최솟값 찾기

해당 문제는 정해진 범위 안에서 최소값 찾기 입니다.

<내 풀이>

n, m =map(int,(input().split()))
A=list(map(int,(input().split())))

i = 0
j = 1
mi = []
for x in range(n):
    mi.append(min(A[i:j]))
    if j >= m:
        i += 1
        j += 1
    else:
        j += 1
print(*mi)

> 처음엔 단순히 포인터 개념으로 접근하여 문제를 해결했습니다. 하지만, 위의 해답으로는 n의 수가 커질 수록 비교를 해야하는 횟수가 굉장히 많아지기 때문에 시간초과가 걸리게됩니다.

해답에서는 덱의 구조를 이용하여 비교 연산 횟수를 줄였습니다.

핵심 개념은 1. 최솟값이 될 수 없는 데이터 삭제, 2. 주어진 범위 밖의 데이터 삭제. 입니다.

덱은 값과 인덱스가 튜플 구조로 함께 저장하기 때문에 한번은 값을 비교하고, 두번째는 범위를 비교할 수 있습니다.

from collections import deque
N, L = map(int, input().split())
mydeque = deque()
now = list(map(int,input().split()))

for i in range(N):
    # 나보다 큰 데이터 삭제
    while mydeque and mydeque[-1][0] > now[i]:
        mydeque.pop()
    mydeque.append((now[i],i))
    # 슬라이딩 윈도우 범위 벗어난 데이터 삭제
    if mydeque[0][1] <= i - L:
        mydeque.popleft()
    print(mydeque[0][0], end= ' ')