문제 이해

숫자 배열 중 인접한 수를 1개 이상 뽑을 것이다.
이 때, 뽑은 수들 사이에서는 중복되는 값이 없어야 한다.

뽑을 수 있는 모든 경우의 수를 구하라.

---

문제 풀이

부분합을 구하는 문제와 풀이 자체는 비슷하게 풀었다.
하지만 부분합과 차이점이 2개가 있다.

1. 최소값이 아닌 경우의 수를 찾는 것

2. 부분합이 아닌 중복 여부를 검사할 것

먼저 포인터 2개를 설정한다.
왼쪽 포인터 left, 오른쪽 포인터 right으로 설정 후 처음에는 index=0위치에 둔다.
그리고, left ~ right사이의 중복 여부를 확인하면 된다.

1. right : 이전 Search에서 중복이 없을 경우 오른쪽으로 1 증가한다.

2. left : 이전 Search에서 중복을 찾았을 경우 오른쪽으로 1 증가한다.

이 때, 이전 Search에서는 left ~ right까지의 범위를 찾았을 것이다.
즉, 만약 이전 Search에서 중복이 없었을 경우, arr[right+1]이 유일하게 중복이 될 수 있는 가능성이 존재한다.
(만약, right+1이 아닌 부분에 중복이 있었다면, left ~ right 사이에 중복이 있었다는 의미이며, 이는 모순이다.)

또한 경우의 수를 구하는 것이므로, 정답을 구하는 법도 약간 다르다.

1. Search에서 중복이 없을 경우 : 아무런 행동을 취하지 않음

2. Search에서 중복이 있을 경우 : left ~ right에서 중복을 발견했다. 위에서 말했던 것처럼, 정확히는 arr[right]과 arr[left] ~ arr[right-1] 사이에 중복이 발생하였다. 이를 반대로 생각하면, arr[left] ~ arr[right-1]에서는 중복이 없었다는 의미이다. 즉, left ~ (right-1)에서 만들 수 있는 연속된 인접 수열 개수인 (left + 0) ~ (left + right - left - 1), 총 right-left개가 중복이 없는 경우의 수가 될 것이다. 이를 전체 정답에 더해준다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	
	static int N;
	static int[] arr;
	
	static Boolean duplicate(int left, int right) {
        // 중복 여부 검사 메서드. 
        // 중복일 경우 true, 중복이 안 될 경우 false 반환
        // 위에서 설명했듯, arr[right]와 비교만 하면 됨
		for(int i = left;i<right;i++) {
			if(arr[i]==arr[right]) return true;
		}
		return false;
	}
	
	static void two_pointer() {
		int left = 0;
		int right = 0;
		long ans = 0;
		
		while(right < N) {
			if(!duplicate(left, right)) {
                // 중복 안 될 경우
				right++;
			}
			else {
                // 중복 되었을 경우. 
                // left ~ (right-1)으로 만들 수 있는 인접배열 개수를 더해줌
				ans+= right- left;
				left++;
			}
		}
		
		for(int i = left;i<N;i++) {
        /*
        right이 배열을 벗어났다는 의미는, 마지막으로 right++명령이 
        수행되었을 것이다.
        즉, 중복이 되지 않았다는 의미이다.
        
        따라서, left ~ (배열 끝), (left + 1) ~ (배열 끝), ...은 
        모두 중복이 되지 않을 것이다.
        그러므로 위의 모든 경우의 수를 최종적인 답 ans에 더해줘야 한다.
        */
			ans+= right-i;
		}
		
		System.out.println(ans);
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		arr= new int[N];
		
		for(int i =0;i<N;i++) {
			arr[i] = sc.nextInt();
		}
		
		two_pointer();
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 2번째 줄 틀렸습니다 이유 : ans은 최악의 경우 int형 데이터가 처리하는 범위를 넘어선다. 따라서 long으로 ans의 자료형을 설정해줘야 한다.