🧚‍♂️알고리즘🧚‍♂️ - 자료구조 - 투 포인터 / 슬라이딩 윈도우

투 포인터 

- 2개의 포인터 / 시간 복잡도 최적화

---

1번

백준 2018번 실버 5

2018번: 수들의 합 5

- 결과값에 1 미리 넣기 (자기자신의 수)

- 시작 포인터 / 끝 포인터 ( 값이 목표보다 작거나 같으면 끝포인터++ / 값이 목표보다 크면 시작포인터++)

from sys import stdin
N = int(stdin.readline())
sum = 1 # 현재  합
count = 1 # 자기 자신이 포함된 결과값
startPoint = 1 
endPoint = 1

while (endPoint != N):
    if (N == sum):# 값 완성 -> 결과 ++ , 합 0으로, 엔드++
        count += 1
        endPoint += 1
        sum += endPoint # sum 0 으로 만드는게아니라..계속되어야함..
    elif(N > sum): # 아직 작음 -> 엔드++ , 합 += 엔드
        endPoint += 1
        sum += endPoint
    else: # 큼 -> 합 - 스타트,스타트++
        sum -= startPoint 
        startPoint+=1
    

print(count)

---

2번

백준 1940번 실버 4

1940번: 주몽

-얘는 사이의 범위가 아니라 두개 고르는 거니까 양쪽 끝에서 시작해서 가운데쪽으로 보내야 함..!

from sys import stdin
N = int(stdin.readline())
M = int(stdin.readline())
Nlist = list(map(int,stdin.readline().split()))
Nlist.sort()

# 포인터두개가가리키는값으로 만드므로 합변수 필요없음
count = 0 
startPoint =0
endPoint = N-1

while (endPoint != startPoint):
    if (M == Nlist[startPoint]+Nlist[endPoint]):# 값 완성 -> 결과 ++ 
        count += 1
        endPoint -=1
    elif(M > Nlist[startPoint]+Nlist[endPoint]): # 작음 
        startPoint+=1
    else: # 큼
        endPoint -= 1

print(count)

---

3번

백준 1253번 골드 4

1253번: 좋다

- 리스트 Nlist = Mlist로 복사하면 얕은 복사인가봐.. 깊은 복사 어케하지

copy.deepcopy 메소드 사용하면 됨

from sys import stdin
import copy
N = int(stdin.readline())
Nlist = list(map(int,stdin.readline().split()))
Nlist.sort()

count = 0
startPoint = 0
endPoint = N-2

for i in range(N):
    Mlist = copy.deepcopy(Nlist)
    Mlist.pop(i)
    startPoint = 0
    endPoint = N-2
    while (endPoint != startPoint):

        if (Nlist[i] == Mlist[startPoint]+Mlist[endPoint]):# 값 완성 -> 결과 ++ 
            count += 1
            break
        elif(Nlist[i] > Mlist[startPoint]+Mlist[endPoint]): # 작음 
            startPoint+=1
        else: # 큼
            endPoint -= 1

print(count)

와 책이랑 다르게 맞혔다!

---

슬라이딩 윈도우

- 2개의 포인터 / 범위 유지한 채로 이동하며 문제 해결

---

1번

백준 12891번 실버 2

12891번: DNA 비밀번호

- 처음 이후로는, 들어오고 나가는 문자열만 반영하는 것이 시간복잡도를 줄이는 포인트 (매번 ACGT 개수 세지 않게)

이런...

---

2번

백준 11003번 플래티넘 5!

11003번: 최솟값 찾기

< 크기 비교해서 값 덱에 새로 추가하기(자기보다 큰 값이 앞에 있으면 앞값 삭제) -> 윈도우 범위만큼 남기기 ->맨앞값뽑기 >반복

from sys import stdin
from collections import deque
N,L = map(int,stdin.readline().split())
Nlist = list(map(int,stdin.readline().split()))
mydeque = deque() # 덱! 양 끝에서 데이터삭제.삽입 가능한 자료구조

for i in range(N): 
    #자기보다 큰 값이 앞에 있으면 앞값 삭제 후 값 덱에 새로 추가
    while  mydeque and mydeque[-1][0] >= Nlist[i]:
        mydeque.pop() # pop() 뒷값 삭제
    mydeque.append((Nlist[i],i))
    # 윈도우 범위만큼 남기기 
    if (mydeque[0][1] <= i-L): #(mydeque[-1][1]-mydeque[0][1]+1 > L)로 하면 값이 1개일 때 오류
        mydeque.popleft() # popleft() 앞값 삭제
    # 맨앞값뽑기
    print(mydeque[0][0], end=" ")

 

아하 덱이 비어있을 때 오류 안 나나 생각했는데 저게 그거였군!!

조건문에 덩그러니 덱(리스트) 쓰이면 "비어있지 않음"의 뜻!!

---

메리크리스마스!