์๊ณ ๋ฆฌ์ฆ(๋ด๋ฐฉ์)
- ์ซ์๋ฅผ ์ผ์ชฝ์์ ์ค๋ฅธ์ชฝ์ผ๋ก ์ดํด๊ฐ๋ฉด์, ๊ทธ ์๊ฐ ๋์จ ์ธ๋ฑ์ค๋ฅผ ๊ธฐ๋ก(saveIdx)ํ๋ค.
- i๋ฅผ ๊ธฐ๋กํ ๋ ์ด๋ฏธ ๊ธฐ๋ก๋ ์ธ๋ฑ์ค๊ฐ ์์ ๊ฒฝ์ฐ, ๊ทธ ์ธ๋ฑ์ค๋ถํฐ ์ด์ ์ ์ฒดํฌ๊ฐ ์๋ ์ธ๋ฑ์ค๋ค์ i ๊น์ง๋ง ์ฐ์ํด์ ์ซ์๋ฅผ ๋ฝ์ ์ ์๋ค. ๋ฐ๋ผ์ ์ด์ ํด๋นํ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ ๋ต์ ์ถ๊ฐ์์ผ์ค๋ค.
์๊ณ ๋ฆฌ์ฆ(ํฌํฌ์ธํฐ)
-
๋ด๊ฐ ํ ๋ฐฉ์์์ ๊ด์ ๋ง ๋ฐ๊พธ๋ฉด ํฌํฌ์ธํฐ ๋ฐฉ๋ฒ์ด ๋๋ค.
-
์ผ์ชฝ์์ ์ค๋ฅธ์ชฝ์ผ๋ก end๋ฅผ ํ๋์ฉ ๋๋ ค๊ฐ๋ฉฐ ์ซ์๋ฅผ ์ดํด๊ฐ๋ฉด์, ํ์ฌ ์๋ฅผ ์ฒดํฌํ๋ค.
-
๋ง์ฝ i์์์ ์ซ์๊ฐ ์ด๋ฏธ ์ฒดํฌ ๋์์ ๊ฒฝ์ฐ, start ์์๋ถํฐ ๊ทธ ์ฒดํฌ๋ ์ซ์(c)๊น์ง๋ end ์ด์ ๊น์ง๋ง ์ฐ์ํด์ ์ซ์๋ฅผ ๋ฝ์ ์ ์๋ค.
-
๋ฐ๋ผ์ 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;
}