[BOJ] 13144번 - List of Unique Numbers

 

[BOJ] 13144번 - List of Unique Numbers

 

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

13144번: List of Unique Numbers

 

문제 이해

---

수열에서 연속되게 1개 이상 뽑는 경우에서 같은 수가 등장하는 경우는 제외하고 갯수를 세라.

여기서 중요한 점이 "연속"과 "같은 수"이다.

 

알고리즘

---

처음 문제를 보자마자 투포인터로 풀어야겠다는 생각을 하였다. 각 시작점에서 같은 수가 없이 등장하는 뒷단계를 알면 한번에 계산이 되기 때문이다.

 

처음에는 Left , Right를 0부터 두고 시작하여 각 단계에서 중복을 확인하기 위하여 Deque를 이용하여 사용하였다.

위와 같이 구현 시 특정 %까지는 맞지만 중간에서 시간 초과가 발생하였다.

 

이에 따라 문제를 다시 본 결과 정수의 범위가 100,000까지 밖에 안되는 것을 캐치하고 List로 Index를 정수로 나타내어 처리하는 부분으로 가닥을 잡았다.

-> 그 결과 성공하였다.

 

1. 투포인터 초기화

2. 중복이 발생할 때 까지 Right 값을 계속하여 움직여준다.

3. 현재 위치에서 Right가 이동한 값 까지 계속하여 더하여 주면 된다.

 

코드

---

#BOJ 13144번

import sys
input = sys.stdin.readline

n = int(input())
datas = list(map(int,input().split()))

answer = 0
right = 0
number = [0]*(100001)

for i in range(n) : # i = left
    for j in range(right,n) :
        if number[datas[j]] :
            break
        else :
            number[datas[j]] = 1
            right += 1
    answer += right-i
    number[datas[i]]=0

print(answer)