백준 13144 List of Unique Numbers 파이썬 주석 설명 O

https://www.acmicpc.net/problem/13144

13144번: List of Unique Numbers

<정답 코드 및 상세 설명은 맨 아래 있습니다.>

중복된 수가 나왔는지 확인해주는 배열 ch를 나올 수 있는 숫자의 최대 크기 +1 길이 만큼 만들어줬다.

처음에는 시작 지점을 0~n-1 idx로 잡고 거기서 부터 앞으로 나아가는 동시에 최종 값에 +1을 해줬다. 만약 중복된 수가 나오면 멈추고 이전에 나왔던 수를 모두 False로 바꿔주면서 다시 ch 배열을 재사용했다.

n = int(input())
s = list(map(int,input().split()))
st,en=0,0
re=0
ch = [False]*100001
for i in range(n):
    d =[s[i]]
    re+=1
    ch[s[st]]=True
    for k in range(i+1,n):
        if not ch[s[k]]:
            ch[s[k]]=True
            re+=1
            d.append(s[k])
        else:
            break
    for k in d:
        ch[k]=False
print(re)

하지만 위의 코드는 메모리 초과가 나왔고 아래와 같이 재귀로도 바꿔봤지만 메모리 초과가 나오는 것은 여전했다.

import sys
sys.setrecursionlimit(10**5)#메모리를 잡아 먹는 다는 것은 알지만 안 해주면 재귀깊이 오류가 나옴.
def cs(ch,i):
    global re
    if i<n and not ch[s[i]]:
        re+=1
        ch[s[i]]=True
        cs(ch,i+1)
        ch[s[i]]=False
    
n = int(input())
s = list(map(int,input().split()))
re=0
ch = [False]*100001
for i in range(n):
    re+=1
    ch[s[i]]=True
    cs(ch,i+1)
    ch[s[i]]=False
print(re)

그래서 문제 분류에 맞게 두 포인터를 사용해 아래와 같이 풀었다.

n = int(input())
s = list(map(int,input().split()))
re=0
st,en = 0,0
ch = [False]*100001
while st!=n and en!=n:#시작 지점과 끝나는 지점이 n이면 멈춰줌 
    if not ch[s[en]]:#끝나는 지점이 안 나온 수 라면 앞으로 전진해줌
        ch[s[en]]=True
        en+=1
        re+=en-st#s=[1, 2, 3]인 경우 st = 0,en=1,2,3|en =1: 1, en = 2: 1 2/ 2, en = 3: 1 2 3/ 2, 3/ 3
    else:
        while ch[s[en]]:#s[en]이 참인 경우 = 앞에 중복되는 숫자가 이미 나왔다.
            ch[s[st]]=False#앞에 나온 숫자는 이제 안 쓸거므로 False로 바꿔줌
            st+=1#다음 숫자로 이동
    
print(re)#결과 출력