[Python][백준] 13144. List of Unique Numbers / 투포인터 (G4)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

import sys
input = sys.stdin.readline

N = int(input())
lst = list(map(int,input().split()))
number = set()
rs = sp = 0 

for ep in range(N):
    while lst[ep] in number:
        number.remove(lst[sp])
        sp += 1 
    number.add(lst[ep])
    rs = rs + ep - sp + 1

print(rs)

ex)
1 2 3 1 2

 

1. 위와 같은 입력을 예시로 들어보자. 

아마 대부분의 보통은 1 / 1,2 / 1,2,3 /  2 / 2,3 / 2,3,1 / 3 / 3,1 / 3,1,2 / 1 / 1,2 / 2의 순서대로 생각할 것 같다.

 

2. 하지만 이 문제는 1 / 1,2 / 2 / 1,2,3 / 2,3 / 3 ... 의 접근법이다.

(이러한 접근도 가능하다는 것 생각)

 

3. 글로 보는 것을 헷갈리고 코드로 이해하는 것 좋다.

 

4. 메모리를 아끼기 위해 집합 자료 구조를 사용한다. 

 

5. sp (start point)와 ep (end point)를 잘 이용해야한다.

📌 문제 코멘트 

이렇게 많은 수열들을 모두 리스트에 넣으면 메모리 초과가 발생한다.

이를 위해 집합 자료 구조를 사용한다.

그리고 N의 범위가 10만이므로 1개의 반복문을 써야한다. 

---

📚문제

길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)

두 번째 줄에는 수열을 나타내는 N개의 정수가 주어진다. 수열에 나타나는 수는 모두 1 이상 100,000 이하이다.

출력

조건을 만족하는 경우의 수를 출력한다.

예제 입력 1 복사

5
1 2 3 4 5

예제 출력 1 복사

15

예제 입력 2 복사

5
1 2 3 1 2

예제 출력 2 복사

12

예제 입력 3 복사

5
1 1 1 1 1

예제 출력 3 복사

5