self.winter.(12). 투 포인터, 슬라이딩 윈도우 _ 백준 [17609, 1253, 11003]

🧐 투 포인터 (two - pointer)

2개의 포인터를 이용해 알고리즘의 시간복잡도를 최적화하는 방법으로 간단한 알고리즘을 사용한다.

주로 n의 최댓값이 크게 잡혀있고 O(nlog n)의 시간복잡도로 해결이 힘들 때, O(n)의 시간복잡도로 구현해야 한다.
이때, 자주 사용되는 것이 바로 투 포인터 알고리즘이다.

투 포인터 알고리즘은 시작 인덱스와 종료 인덱스를 지정해 서로 조건에 따라 접근하도록 하는 것이다.

 

 

🧐 슬라이딩 윈도우

슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 후
범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결하는 알고리즘이다.

투포인터 알고리즘과 매우 비슷하다.

 

 

 

🧐 백준 17609 (회문)    Gold V 

🤫  solution_17609(시간초과)

string_list = [input() for _ in range(int(input()))]

def palindrome(string):
    # 회문인 경우
    if string == string[::-1]:
        print(0)
    # 회문이 아닌경우
    else:
        ans = 2
        for i in range(len(string)):
            new_string = string[:i] + string[i+1:]
            if new_string == new_string[::-1]:
                ans = 1
        print(ans)

for i in string_list:
    palindrome(i)

 

🤫  solution_17609

# 유사 회문 판단 함수
def palindrome_like(string, left, right):
    while left < right:
        if string[left] == string[right]:
            left += 1
            right -= 1
        else:
            return False
    return True
# 회문 함수
def palindrome(string, left, right):
    while left < right:
        if string[left] == string[right]:
            left += 1
            right -= 1
        else:
            pseudo1 = palindrome_like(string, left+1, right)
            pseudo2 = palindrome_like(string, left, right-1)

            if pseudo1 or pseudo2:
                return 1
            else:
                return 2
    return 0

for string in list([input() for _ in range(int(input()))]):
    print(palindrome(string, 0, len(string) - 1))

 

 

 

🧐 백준 1253 (Good Number)    Gold IV 

  

🤫  Algorithm 

# 해당 원소를 제외한 리스트에서 투 포인터(Two-Pointer)를 통해 
# 두 원소의 합이 선택한 원소와 같은지 비교하는 방식으로 해결할 수 있다.

1. num 리스트를 정렬한다.

2. 0부터 N - 1 까지 반복문을 통해 특정 원소(num[i])를 선택하고, 해당 원소를 제외한 except_num 리스트를 생성

3. except_num 리스트에서 투 포인터를 통해 두 원소의 합(sum)이 num[i] 인지 비교한다.
  t < num[i]이면 left를 증가
  t > num[i]이면 right를 감소

4. 2, 3 과정을 반복한다.

🤫  solution_1253

N = int(input())
num = list(map(int, input().split()))
num.sort()
cnt = 0

for i in range(N):
    except_num = num[:i] + num[i + 1:]
    left, right = 0, len(except_num) - 1
    while left < right:
        sum = except_num[left] + except_num[right]
        if sum == num[i]:
            cnt += 1
            break
        if sum < num[i]:
            left += 1  # t 를 증가시켜야 하므로 left 증가
        else:
            right -= 1  # t 를 감소시켜야 하므로 right 감소
print(cnt)

 

 

 

🧐 백준 11003 (최솟값 찾기,  슬라이딩 윈도우 이용)    Platinum V 

  

🤫  Algorithm 

특정 새로운 원소가 추가될 때 이 원소보다 큰 값은 유지될 필요가 없다.
(인덱스로 볼 때에도 새로 추가되는 원소가 가장 오래 남기 때문.)

덱으로 구성하고 덱의 앞에 항상 최소값이 오도록하기 위해
삽입은 append를 이용해 값과 인덱스로 진행한다.

1. 삽입하기전에 덱을 뒤에서 while로 삽입하려는 요소보다 큰값을 모두 제거.
(삽입한다면 덱은 항상 오름차순으로 정렬된 상태를 자동적으로 유지할 것이다.)
(이는 정렬로 인한 시간복잡도를 없애줘 시간초과가 발생하지 않게 할 수 있다.)

2. 추가적으로 슬라이딩 범위를 벗어난 요소들을 생각하면 아래와 같다.
삽입하기전에 덱을 앞에서부터 보며 인덱스 범위가 벗어난 요소들을 빼준다.

i) 뒤에서부터 확인하며 삽입하려는 요소보다 큰 값들을 제거
ii) 앞에서부터 보며 슬라이딩 범위를 벗어난 요소들을 제거
iii) 현재 요소 삽입
모든 연산이 O(1)으로 전체 배열을 확인하는데 O(n)으로 해결가능하다.

🤫  solution_11003

from collections import deque

N, L = map(int, input().split())
A = list(map(int, input().split()))
dq = deque()


for i in range(N):
    first, end = i - L, i
    # 현재 들어온 값보다 큰 값들을 제거하여 시간복잡도를 줄임
    while dq and dq[-1][0] > A[end]:  # 덱의 마지막 위치에서 현재값보다 큰 값 제거
        dq.pop()
    dq.append((A[end], end))  # A, A_idx, 마지막 위치에 현재값 저장
    if dq[0][1] <= first:
        dq.popleft()
    print(dq[0][0], end = " ")