투 포인터
2개의 포인터로 알고리즘의 시간 복잡도를 최적화함
[문제 006] 연속된 자연수의 합 구하기
N의 최댓값이 10,000,000으로 매우 크므로 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n) 시간 복잡도 알고리즘을 사용해야 함
⇒ 이런 경우 자주 사용하는 방법이 투 포인터
💡 투 포인터 이동 법칙
- sum > N: sum = sum-start_index; start_index++;
- sum < N: end_index++; sum = sum+end_index;
- sum = N: end_index++; sum = sum+end_index; count++;
- start_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 것
- end_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수의 범위를 한 칸 더 확장하는 것
- sum이 N과 같을 때는 경우의 수를 +1 하고, end_index를 오른쪽으로 이동시킴
n = int(input())
left, right = 0, 0 # 투 포인터
sum = 0 # left ~ right 까지의 합
answer = 0 # 가짓수
# right가 n이 될 때까지 반복
while right <= n:
# 합이 n이면
if sum == n:
answer += 1 # 가짓수 +1
right += 1
sum += right
# 합이 n보다 작으면 right 포인터 오른쪽으로 한 칸 이동
elif sum < n:
right += 1
sum += right
# 합이 n보다 크면 left 포인터 오른쪽으로 한 칸 이동
elif sum > n:
sum -= left
left += 1
print(answer)
[문제 007] 주몽의 명령
N의 최대 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘을 사용해도 문제없음
- 일반적으로 정렬 알고리즘의 시간 복잡도는 O(nlogn)이므로 정렬 사용 가능
- N개의 재료값을 오름차순 정렬한 다음 양쪽 끝의 위치를 투 포인터로 지정해 접근
💡 투 포인터 이동 원칙
- A[i] + A[j] > M: j—;
- A[i] + A[j] < M: i++;
- A[i] + A[j] = M: i++, j—; count++;
n = int(input()) # 재료의 개수
m = int(input()) # 갑옷을 만드는데 필요한 두 재료의 합
nlist = list(map(int, input().split())) # n개의 재료 고유 번호
left, right = 0, n-1 # 시작 인덱스, 끝 인덱스
answer = 0 # 경우의 수
nlist.sort() # nlist를 정렬해준 후 투 포인터로 접근
# left와 right가 만날 때까지 반복
while left < right:
# 두 재료의 합이 m이면
if nlist[left] + nlist[right] == m:
answer += 1
left += 1
right -= 1
# 두 재료의 합이 m보다 작으면 left +1
elif nlist[left] + nlist[right] < m:
left += 1
# 두 재료의 합이 m보다 크면 right -1
elif nlist[left] + nlist[right] > m:
right -= 1
print(answer)
[문제 008] ‘좋은 수’ 구하기
💡 투 포인터 이동 원칙
- A[i] + A[j] > K: j—;
- A[i] + A[j] < K: i++;
- A[i] + A[j] = K: count++; 프로세스 종료
n = int(input()) # 수의 개수
nlist = list(map(int, input().split())) # n개의 수
answer = 0 # 경우의 수
nlist.sort()
for i in range(n):
temp = nlist[:i] + nlist[i+1:] # i를 제외한 리스트
start, end = 0, len(temp)-1
while start < end:
# 두 수의 합이 nlist[i]이면 경우의 수 +1
if temp[start] + temp[end] == nlist[i]:
answer += 1
break
# 두 수의 합이 nlist[i]보다 작으면 start +1
elif temp[start] + temp[end] < nlist[i]:
start += 1
# 두 수의 합이 nlsit[i]보다 크면 end -1
else:
end -= 1
print(answer)
슬라이딩 윈도우
2개의 포인터로 범위를 지정한 다음, 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결하는 방식
[문제 009] DNA 비밀번호
s, p = map(int, input().split()) # DNA 문자열 길이, 비밀번호 부분 문자열 길이
dna = input() # DNA 문자열
a, c, g, t = map(int, input().split()) # 'A', 'C', 'G', 'T'의 최소 개수
password = 0 # 만들 수 있는 비밀번호의 개수
count = {'A': 0, 'C': 0, 'G': 0, 'T': 0}
for i in range(s-p+1):
# 초기 길이 p의 문자열의 acgt 개수 파악
if i == 0:
for j in range(p):
count[dna[j]] += 1
# 한 칸 씩 이동하며 왼쪽 값 -1(제거), 오른쪽 값 +1(추가)
else:
count[dna[i-1]] -= 1
count[dna[i-1+p]] += 1
# 조건에 맞는 지 확인 후 개수 +1
if count['A'] >= a and count['C'] >= c and count['G'] >= g and count['T'] >= t:
password += 1
print(password)
[문제 010] 최솟값 찾기 1
💡 deque의 구조
from collections import deque
N, L = map(int, input().split())
A = list(map(int, input().split())) # n개의 수
queue = deque()
for i in range(N):
# 가장 마지막 원소의 값이 A[i]보다 크면 queue에서 제거
while queue and queue[-1][1] > A[i]:
queue.pop()
queue.append((i, A[i])) # (인덱스, 값) 형식으로 queue에 추가
# 범위 L을 벗어나면 맨 앞에 위치한 원소 queue에서 제거
if queue[-1][0] - queue[0][0] >= L:
queue.popleft()
print(queue[0][1], end=' ') # 공백으로 구분하여 출력
반응형
