์•Œ๊ณ ๋ฆฌ์ฆ˜(๋‚ด๋ฐฉ์‹)

  • ์ˆซ์ž๋ฅผ ์™ผ์ชฝ์—์„œ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์‚ดํŽด๊ฐ€๋ฉด์„œ, ๊ทธ ์ˆ˜๊ฐ€ ๋‚˜์˜จ ์ธ๋ฑ์Šค๋ฅผ ๊ธฐ๋ก(saveIdx)ํ•œ๋‹ค.
  • i๋ฅผ ๊ธฐ๋กํ• ๋•Œ ์ด๋ฏธ ๊ธฐ๋ก๋œ ์ธ๋ฑ์Šค๊ฐ€ ์žˆ์„ ๊ฒฝ์šฐ, ๊ทธ ์ธ๋ฑ์Šค๋ถ€ํ„ฐ ์ด์ „์— ์ฒดํฌ๊ฐ€ ์•ˆ๋œ ์ธ๋ฑ์Šค๋“ค์€ i ๊นŒ์ง€๋งŒ ์—ฐ์†ํ•ด์„œ ์ˆซ์ž๋ฅผ ๋ฝ‘์„ ์ˆ˜ ์žˆ๋‹ค. ๋”ฐ๋ผ์„œ ์ด์— ํ•ด๋‹นํ•˜๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ •๋‹ต์— ์ถ”๊ฐ€์‹œ์ผœ์ค€๋‹ค.

์•Œ๊ณ ๋ฆฌ์ฆ˜(ํˆฌํฌ์ธํ„ฐ)

  • ๋‚ด๊ฐ€ ํ•œ ๋ฐฉ์‹์—์„œ ๊ด€์ ๋งŒ ๋ฐ”๊พธ๋ฉด ํˆฌํฌ์ธํ„ฐ ๋ฐฉ๋ฒ•์ด ๋œ๋‹ค.

    1. ์™ผ์ชฝ์—์„œ ์˜ค๋ฅธ์ชฝ์œผ๋กœ end๋ฅผ ํ•˜๋‚˜์”ฉ ๋Š˜๋ ค๊ฐ€๋ฉฐ ์ˆซ์ž๋ฅผ ์‚ดํŽด๊ฐ€๋ฉด์„œ, ํ˜„์žฌ ์ˆ˜๋ฅผ ์ฒดํฌํ•œ๋‹ค.

    2. ๋งŒ์•ฝ i์—์„œ์˜ ์ˆซ์ž๊ฐ€ ์ด๋ฏธ ์ฒดํฌ ๋˜์—ˆ์„ ๊ฒฝ์šฐ, start ์—์„œ๋ถ€ํ„ฐ ๊ทธ ์ฒดํฌ๋œ ์ˆซ์ž(c)๊นŒ์ง€๋Š” end ์ด์ „๊นŒ์ง€๋งŒ ์—ฐ์†ํ•ด์„œ ์ˆซ์ž๋ฅผ ๋ฝ‘์„ ์ˆ˜ ์žˆ๋‹ค.

    3. ๋”ฐ๋ผ์„œ start๋ฅผ c๊นŒ์ง€ ๋Š˜๋ ค๊ฐ€๋ฉฐ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ถ”๊ฐ€ํ•˜๊ณ , check๋ฅผ ํ’€์–ด๊ฐ€๋ฉด ๋œ๋‹ค.

์ฝ”๋“œ

#include <iostream>
 
using namespace std;
 
int n, nums[100010], saveIdx[100010];
long long ans;
bool check[100010];
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> nums[i];
 
	for (int i = 1; i <= n; i++) {
		if (saveIdx[nums[i]] != 0) {
			for (int j = saveIdx[nums[i]]; j >= 1; j--) {
				if (!check[j]) {
					ans += (i - j);
					check[j] = true;
					saveIdx[nums[j]] = 0;
				}
				else
					break;
			}
		}
		saveIdx[nums[i]] = i;
	}
	for (int i = n; i >= 1; i--) {
		if (!check[i]) {
			ans += (n + 1 - i);
			check[i] = true;
		}
		else
			break;
	}
	cout << ans;
}