[TIL] 문제 풀이 연습 - two point (with python)

1. 문제 풀이 연습

1. 2018번 - 수들의 합

import sys

N = int(sys.stdin.readline())

start = 1 # 현재 더한 값 중 첫번째 값
end = 1 # 현재 더한 값 중 마지막 값
count = 1 # 자기 자신 포함
sum = 1 # 총 더한 값

# 최소 2개의 연속된 자연수의 합이어야 하므로 
# start는 N의 절반보다 클 수 없다.
while start != N // 2 + 1 :
    if sum < N : # 아직 누적합이 N보다 작을 경우
        end += 1
        sum += end
    elif sum == N : # N과 같을 경우
        count += 1
        sum -= start
        start += 1
    else : # N보다 클 경우
        sum -= start
        start += 1
print(count)

처음에는 연속된 수의 합이 N일 수 있는 경우에 대한 공식을 사용했는데 시간초과로 실패했다.
< 참고 공식 > https://velog.io/@zmdals/연속된-자연수의-합-2-수학적풀이

투 포인터를 이용해야한다고 해서 start와 end를 잡고 시작했다.
1. 이미 자기 자신에 대한 것은 포함한다고 생각하고 count = 1
2. start, end, sum = 1, 1, 1 → 첫번째 요소만 우선 넣어준다.
3. sum < N 이면 + 다음값
4. sum == N 이면 count++, 맨 앞 값 하나 제거
5. sum > N 이면 맨 앞 값 하나 제거
6. 3, 4, 5 번 과정을 start가 N의 절반이 될때 까지 반복

< 알고리즘 참고 > https://baby-ohgu.tistory.com/11

15 예시 동작 과정

---

2. 1940번 - 주몽

import sys

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
nums.sort() # 정렬

start = 0 # 현재 가장 작은 값의 인덱스
end = N-1 # 현재 가장 큰 값의 인덱스
count = 0

while start < end :
    s = nums[start] + nums[end]
    if s == M : # 갑옷을 만들 수 있다.
        count += 1
        start += 1
        end -= 1
    elif s < M : # M보다 작으므로 작은 값을 올려준다.
        start += 1
    else : # M보다 크므로 큰 값을 줄여준다.
        end -= 1

print(count)

예시 동작 과정

이번에는 확실히 투 포인터를 쓰면 되겠다는 생각이 들어 바로 구현해보았다.
두 개의 재료를 가지고 갑옷을 만들어야하는데 재료들의 번호의 합이 M이어야 한다면 두개를 선택해서 비교해보면 된다.
대신 시작하기 전에 정렬하여 가장 큰 수와 가장 작은 수를 비교할 수 있도록 했다.
두 수의 합이 M보다 작으면 작은 값을 좀 더 크게 만들고
M보다 크면 큰 값을 좀 더 작게 만들어서 M과 가까워지도록 했다.

---

3.  1253번 - 좋다

import sys

N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
nums.sort()

count = 0
for i in range(N) :
    start = 0
    end = N-1
    while start < end :
        # start와 end는 현재 값이면 안된다.
        if start == i :
            start += 1
        elif end == i :
            end -= 1
        else :
            current = nums[i] # 현재값
            t = nums[start] + nums[end] # 두개 더한값
            if current == t :
                count += 1
                break
            elif current > t :
                start += 1
            else :
                end -= 1
print(count)

현재 인덱스가 아니면 선택된 두 값을 더해 현재 값과 비교하여 좋은 수 인지 확인한다.
단, 좋은 수 이면 바로 다음 수로 넘어갈 수 있도록 해준다

---

4. 12891번 - DNA 비밀번호

import sys
from collections import deque

s, p = map(int, sys.stdin.readline().split())
dna = list(sys.stdin.readline().strip())
# A, C, G, T
esssential = list(map(int, sys.stdin.readline().split()))

start = 0
end = p-1
count = 0
# 현재 부분 문자열
current = deque(dna[0:p])
# 각각의 원소 포함 개수
a = current.count("A")
c = current.count("C")
g = current.count("G")
t = current.count("T")

while end < s :
    # 만약에 모든 원소들의 조건을 충족했다면
    if a >= esssential[0] and c >= esssential[1] and g >= esssential[2] and t >= esssential[3] :
        count += 1
    # 가장 첫번째 값 제거
    current.popleft()
    # 각각의 원소 개수 중 일치하는 것 빼기
    if dna[start] == 'A' :
        a -= 1
    elif dna[start] == 'C' :
        c -= 1
    elif dna[start] == 'G' :
        g -= 1
    elif dna[start] == 'T' :
        t -= 1
    
    start += 1
    end += 1
    # end가 끝에 도달했으므로
    if end == s :
        break
    # 맨뒤에 문자 하나 추가
    current.append(dna[end])
    # 각각의 원소 개수 중 일치하는 것 추가
    if dna[end] == 'A' :
        a += 1
    elif dna[end] == 'C' :
        c += 1
    elif dna[end] == 'G' :
        g += 1
    elif dna[end] == 'T' :
        t += 1
print(count)

가장 기초적으로 생각하면서 풀었다.
기본적으로 부분 문자열의 길이는 정해져있으므로 맨앞 한개를 빼주고 맨뒤 한개를 더해주면서 크기를 유지한채 조건을 검사한다.
단지, 각각의 원소 포함개수는 문자열이 변경될 때마다 업데이트를 해주어야 하므로 이에 대해 처리를 해주었다.

---

2. 나중에 다시 공부해야할 문제

1. 9249번 - 최장 공통 부분 문자열

★ Manber-Myers Algorithm

정렬할 때 랭크라는 개념과 기수 정렬을 사용하여 시간 복잡도를 줄인 알고리즘
각 단계마다 접미사에 랭크를 부여하고 랭크를 기준으로 정렬한다.
k번째 단계에서 사용되는 랭크는 접미사 앞에서 2^k-1 글자의 순서 정보를 담고 있다.

< 출처 > https://ko.wikipedia.org/wiki/접미사_배열

import sys

A = sys.stdin.readline().strip()
B = sys.stdin.readline().strip()

s = A + "1" + B
n = len(s)

# 접미사 배열 suffix[i] = i -> i번째부터 끝까지 포함하는 부분문자열
# Get Suffix Array
suffix = [i for i in range(n)]
g = [0] * (n+1) # 순위
ng = [0] * (n+1) # 새로운 순위를 갱신할 때 이용

for i in range(n):
    g[i] = ord(s[i])

g[n] = -1 
ng[suffix[0]] = 0
ng[n] = -1

t = 1 # 단계를 나타내는 변수
while t < n:
    suffix.sort( key=lambda x :(g[x], g[min(x+t, n)]) )
    
    for i in range(1, n):
        p, q = suffix[i-1], suffix[i]

        if g[p] != g[q] or g[min(p + t, n)] != g[min(q + t, n)]:
            ng[q] = ng[p] + 1
        else:
            ng[q] = ng[p]
    
    # 처음 부터 정렬이 바로 되어 있을 때 바로 탈출 하기 위해서
    if ng[n-1] == n-1:
        break

    t= t*2
    g = ng[:]


# Get LCP Array
LCP = [0] * n
length = 0 
for i in range(n):
    k = g[i]
    if k == 0: # 처음은 들어가지 않는다.
        continue 
    p = suffix[k-1]

    while i+length < n and p+length < n and s[i+length] == s[p+length]:
        length += 1
    LCP[k] = length

    if length:
        length -= 1


# 나누어진 영역에서의 최대값 구하기
m =(0,0) # length, start_index
for i, j in enumerate(LCP):
    if 0 <= suffix[i-1] + j - 1 < len(A) and len(A) < suffix[i] + j-1 < len(s):
        m = max(m,(j,i))
    if 0 <= suffix[i] + j - 1 < len(A) and len(A) < suffix[i-1] + j-1 < len(s):
        m = max(m,(j,i))
    
length, start = m
print(length)
print(s[suffix[start]: suffix[start] + length])

문제를 풀지는 못하고 어떤 것을 공부하면 되는지에 대해 보기만 했다.
아직 알고리즘이 이해가 확실하게 되는 편이 아니라서 후에 다시 공부해야겠다.

< 참고 >
🔗 https://gumgood.github.io/suffix-array-and-lcp
🔗 https://velog.io/@gopas777/백준-9249-python
🔗 https://velog.io/@stkang9409/최장공통부분문자열-문제