๋ฌธ์
https://www.acmicpc.net/problem/13144
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x14๊ฐ - ํฌ ํฌ์ธํฐ
์๊ณ ๋ฆฌ์ฆ: ํฌ ํฌ์ธํฐ
ํ์ด
๊ธธ์ด๊ฐ N์ธ ์์ด์ด ์ฃผ์ด์ง ๋, ์์ด์์ ์ฐ์ํ 1๊ฐ ์ด์์ ์๋ฅผ ๋ฝ์์ ๋ ๊ฐ์ ์๊ฐ ์ฌ๋ฌ ๋ฒ ๋ฑ์ฅํ์ง ์๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์ฌ๋ผ.
๊ฐ๊ธฐ ๋ค๋ฅธ ์ซ์๋ก ์ด๋ฃจ์ด์ง ์ฐ์๋ ๋ถ๋ถ ์์ด์ ๊ฐฏ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ๋ค.
์ฆ, ์์ 2์ฒ๋ผ [1, 2, 3, 1, 2]๊ฐ ์ฃผ์ด์ก์ ๊ฒฝ์ฐ ๊ฐ๋ฅํ ๋ถ๋ถ ์์ด์ ์๋์ ๊ฐ๋ค.
# 1๊ฐ
[1]. [2], [3], [1], [2]
# 2๊ฐ
[1, 2], [2, 3], [3, 1], [1, 2]
# 3๊ฐ
[1, 2, 3], [2, 3, 1], [3, 1, 2]
# 4๊ฐ, 5๊ฐ๋ ๋ถ๊ฐ๋ฅ
# ๋ต: 12
์ ์์ ๋ง ๋ณด๊ณ set()์ผ๋ก ๊ด๋ฆฌํ๋ ค ํ์ผ๋ ์๋์ ๊ฐ์ ๋ฐ๋ก๊ฐ ์์๋ค.
# ์ถ์ฒ: https://www.acmicpc.net/board/view/128564
5
1 2 2 2 1
#wrong
9
#answer
7
set์ ์ฌ์ฉํ๋ ๋ฐฉ๋ฒ์ ์์ 2์ ๊ฐ์ด "์ค๋ณต๋๋ ์ซ์ == ๊ธฐ์กด ์์ด์ ๊ฐ์ฅ ์ผ์ชฝ ์ซ์" ์ผ ๋์๋ง ๊ฐ๋ฅํ๊ฒ์ด์๋ค.
๊ทธ๋ฐ๊ณ ๋ก ์์ด์ ํฌํจ๋ ๊ฐ ์ซ์์ ๊ฐฏ์๋ฅผ ์ ํํ ํ์ ํ๋ ค๋ฉด ํด์(๋์ ๋๋ฆฌ)๋ฅผ ์ฌ์ฉํด์ผํ๋ค.
- ํ์ฌ ์ถ๊ฐํ ์ซ์์ ๊ฐฏ์๋ฅผ ์นด์ดํธํ๋ค.
- ๋ง์ฝ 1์ด ์๋๋ผ๋ฉด, 1์ด ๋ ๋๊น์ง left ์ซ์์ ๊ฐฏ์๋ฅผ ๊ฐ์์ํค๋ฉฐ left ํฌ์ธํฐ๋ฅผ ์ค๋ฅธ์ชฝ์ผ๋ก ํ์นธ์ฉ ์ด๋ํ๋ค.
- ๋์ฌ ์ ์๋ ์์ด์ ๊ฐฏ์๋ฅผ ์นด์ดํธํ๋ค.
๋์ฌ ์ ์๋ ์์ด์ ๊ฐฏ์๋ ์์ด์ ๊ธธ์ด๋ฅผ ๋ํ ๊ฐ๊ณผ ๊ฐ๋ค.
right๋ฅผ left๋ถํฐ right๊น์ง ์ฆ๊ฐ์ํค๋ฉด์ "right๋ฅผ ํฌํจํ๋ ์์ด์ ๊ฐฏ์"๋ฅผ ๋ํด๊ฐ๋ค๊ณ ์๊ฐํ๋ฉด ๋๋ค.
์๋ฅผ๋ค์ด [1, 2, 3, 4, 5]๊ฐ ์๊ณ left = 0, right = 2 ๋ผ๊ณ ํ๋ค๋ฉด ์์ด์ ๊ฐฏ์๋ฅผ ์ธ๋ ๊ณผ์ ์ ์๋์ ๊ฐ๋ค.
# right = 0 / ์ ํ๋ฒ์: [1]
[1]
=> 1๊ฐ
# right = 1 / ์ ํ๋ฒ์: [1, 2]
[2]
[1, 2]
=> 2๊ฐ
# right = 2 / ์ ํ๋ฒ์: [1, 2, 3]
[3]
[2, 3]
[1, 2, 3]
=> 3๊ฐ
๋ต: 6
์ ์ฒด ์ฝ๋
# ๋ฉ๋ชจ๋ฆฌ: 46492KB / ์๊ฐ: 136ms
from sys import stdin
input = stdin.readline
N = int(input())
arr = list(map(int, input().split()))
nums = {} # ์์ ๊ฐฏ์๋ฅผ ์ฒดํฌํ ๋์
๋๋ฆฌ
cnt = 0
left = 0
for right in range(N):
nums[arr[right]] = nums.get(arr[right], 0) + 1
# ํ์ฌ ์ถ๊ฐํ ์์ ๊ฐฏ์๊ฐ 1์ด ๋ ๋๊น์ง
while nums[arr[right]] > 1:
nums[arr[left]] -= 1 # ๊ฐ์ฅ ์ผ์ชฝ ์ธ๋ฑ์ค์ ์ซ์๋ฅผ ๊ฐ์์ํด
left += 1
cnt += right - left + 1 # ๋์ฌ ์ ์๋ ์์ด์ ๊ฐฏ์ ์นด์ดํธ
print(cnt)