길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.
첫 번째 줄에는 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)
두 번째 줄에는 수열을 나타내는 N개의 정수가 주어진다. 수열에 나타나는 수는 모두 1 이상 100,000 이하이다.
조건을 만족하는 경우의 수를 출력한다.
5
1 2 3 4 5
15
5
1 2 3 1 2
12
5
1 1 1 1 1
5
이 문제는 투 포인터를 이용해서 풀 수 있었다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String[] input = br.readLine().split(" ");
int[] arr = new int[N];
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(input[i]);
}
long ans = 0;
HashSet<Integer> visited = new HashSet<>(); //숫자 체크할 해쉬셋
int left = 0;
int right = 0;
while(true) {
if(right==N) {
if(left==N) break;
else {
ans += (right-left);
left++;
}
}
else if(!visited.contains(arr[right])) { //포함안된 숫자면 포인터 늘림
visited.add(arr[right]);
right++;
}
else {
ans += (right-left); //이미 포함된 숫자면 다 더해주고 시작 idx 늘림
visited.remove(arr[left]);
left++;
}
}
System.out.println(ans);
}
}