#6 투 포인터

투 포인터 알고리즘

• 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 찾을 때까지 탐색하는 알고리즘
• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리

동작 방식&구현

- 보통 left, right이나 start, end 같은 식으로 포인터의 이름을 붙임 -

---

회전 초밥

문제

시간 초과 풀이

N, d, k, c = map(int, input().split())
A = []

for i in range(N):
    a = int(input())
    A.append(a)

count = []

for i in range(N-k+1):
    start = i
    end = i+k-1
    a = [c]
    for j in range(start, end+1):
        if A[j] not in a:
            a.append(A[j])
    count.append(len(a))

print(max(count))

최종 풀이

N, d, k, c = map(int, input().split())
A = []

for i in range(N):
    a = int(input())
    A.append(a)
count = []

A += A[:-1] # 원형으로 만들기
for i in range(N):
    a = [c]
    a += A[i:i+k]
    a = set(a)
    count.append(len(a))
    a =[c]


print(max(count))

이게 풀리네...?

---

귀여운 라이언

문제

• 라이언 인형은 1, 어피치 인형은 2
• 라이언 인형이 k개 이상 있는 가장 작은 연속된 인형들의 집합의 크기 구하기

입력

• N: 인형의 개수, K: 구해야 하는 집합의 라이언 인형 개수
• N개의 인형의 정보

출력

• K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합

풀긴 풀었는데 투 포인터가 전혀 들어가지 않았다
사실 통과될 줄 몰랐다

N, K = map(int, input().split())
a = list(map(int, input().split()))

c = a.count(1)

idx = []
idx2 = []
if c < K:
    print(-1)
else:
    for i in range(N):
        if a[i] == 1:
            idx.append(i) # 인덱스 넣어놓기

    for j in range(len(idx)):
        v = j+K-1 # 개수만큼 인덱스 세서
        if v < len(idx):
            idx2.append(idx[v] - idx[j]+1) # 개수니까 + 1
        else:
            continue
    print(min(idx2)) # 집합 개수가 가장 작은 거 구하기


# 10 2
# 1 2 2 1 2 2 2 2 2 1
#4

---

고냥이

문제

• 고양이는 너무 귀엽다 🐱
• 문자열이 주어지면 최대 N개의 종류의 알파벳을 가진 연속된 문자열 인식
• 최대 문자열 길이 구하기

입력

• N: 인식할 수 있는 알파벳의 종류 최대 개수
• 문자열이 주어짐 (소문자만 포함)

출력

• 번역기가 인식할 수 있는 문자열의 최대길이 출력

힌트

• abbcaccba에서 답은 cacc가 된다. 번역기가 인식할 수 있는 알파벳의 종류는 최대 2개이고, 알파벳의 종류를 최대 2개만 가지면서 가장 긴 연속된 문자열이 cacc이다. 따라서 답은 cacc의 길이인 4가 된다.

풀이

• 문자 하나씩 돌면서 개수 세기 카운트로 개수 세서 달라지면 그 카운트를 리스트에 넣고 가장 긴 값 출력

시간 초과 풀이

N = int(input()) # 알파벳의 종류 최대 개수
S = list(input().rstrip()) # 문자열
answer = []

for i in range(len(S)):
    count = [S[i]]
    count2 = []
    start = i
    start2 = i+1

    while start2 < len(S):
        count2.append(S[start])
        if S[start2] not in count:
            count.append(S[start2])
            if len(count) > N:
                break
        start += 1
        start2 += 1

    answer.append(len(count2))

print(max(answer))