알고리즘/백준
[백준][C++] 13144: List of Unique Numbers
KANTAM
2023. 12. 5. 19:04
문제
13144번: List of Unique Numbers
길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.
www.acmicpc.net
풀이
두 포인터 문제이다.
- 두 포인터를 이용하여 start를 포함하며 반복되는 수가 없는 수열의 경우의 수를 계산하는 방식으로 해결한다.
- start부터 중복되는 수가 없을 때까지 end를 늘린다. 혹은 end가 N까지 도달하여 더 이상 수열을 늘릴 수 없을 때까지 늘린다.
- start에서 end까지 start를 포함하여 만들 수 있는 수열의 개수는 end - start개이다. 이 개수를 answer에 추가한다.
- 그 다음, start를 앞으로 늘려서 1번부터 반복한다.
코드
#include <iostream>
using namespace std;
int nums[100000];
bool num_count[100001];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
for (int i = 0; i < N; ++i)
{
cin >> nums[i];
}
long long answer = 0;
int start = 0;
int end = 0;
while (true)
{
// start를 더 이상 늘릴 수 없을 때까지 반복한다.
if (start >= N)
{
break;
}
// start부터 중복되는 값이 없을 때까지 수열을 늘린다.
// 혹은 end가 N까지 도달하여 더 이상 수열을 늘릴 수 없을 때까지 늘린다.
while (end < N && num_count[nums[end]] == false)
{
num_count[nums[end]] = true;
end++;
}
// start에서 end까지 start를 포함하여 만들 수 있는 수열의 개수는 end - start이다.
answer += (end - start);
// start를 앞으로 늘린다.
num_count[nums[start]] = false;
start++;
}
cout << answer;
return 0;
}