아이디어

관찰

• 만약 한 점부터 시작해서 연속해서 최대한 수열을 뽑으면, 최대 수열 길이와 같은 수의 시작점이 같은 연속된 수열을 얻는다.
  • 예를 들어 첫 번째 자리에서 시작해서 최대한 수열을 늘리면 [1], [1, 2], [1, 2, 3] 3개를 얻는다.
  • 마찬가지로 두 번째 자리에서 시작해서 최대한 수열을 늘리다보면 [2], [2, 3], [2, 3, 1] 3개를 얻는다.
• 순서대로 모든 점을 시작점으로 잡고 최대한 수열을 늘려 길이를 누적하면 된다.
• 최적화: 만약 끝점이 전체 배열의 끝에 다다르면, 이후 어떤 시작점을 잡아도 전체 배열 끝까지 연속된 배열을 얻을 수 있다.
• 범위: 최악의 경우(N=100000, 중복되는 값) 결과는 $\sum_{i=1}^{N} i$ =5,000,050,000 (50억 5만)까지 늘어난다. 따라서 결과를 저장하거나 계산할 때는 long 형 변수를 사용해야 한다.

구현

• 포인터(입력받은 배열 A의 인덱스를 가리키는 변수) 2개 l, r를 만들고 0부터 시작한다.
• A[l~r] 범위에서 A[r+1] 값을 찾을 수 있는지 확인한다.
  • 만약 찾을 수 없었다면 수열의 오른쪽 끝(r)을 늘릴 수 있다.
  • 만약 찾았다면 이때까지 구했던 수열의 길이(r - l + 1)를 결과에 더해주고 시작점(l)을 옮겨준다.
• 최적화: r == N - 1이 되었다면, 시작점 루프를 빠져나와 종료하고, len(= r - l + 1) 부터 1까지의 합 = len * (len + 1) / 2를 구해 결과에 더해주고 계산을 끝낸다.
• 결과를 출력한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tk = null;

    static int N;
    static int[] A;

    public static void main(String[] args) throws Exception {
        N = Integer.parseInt(rd.readLine());

        long ans = 0L;

        A = new int[N];
        tk = new StringTokenizer(rd.readLine());
        for (int i=0; i<N; i++)
            A[i] = Integer.parseInt(tk.nextToken());

        int l, r;
        l = r = 0;
        while (true) {
            while (r < N - 1 && !searchRight(l, r)) r++;
            if (r == N - 1) break;
            ans += r - l + 1;
            l++;
        }
        long len = r - l + 1;
        ans += len * (len + 1) / 2;     // sum from 1 to len

        System.out.println(ans);
    }

    static boolean searchRight(int a, int b) {
        for (int i=a; i<=b; i++) {
            if (A[i] == A[b+1])
                return true;
        }
        return false;
    }
}

메모리 및 시간

• 메모리: 25356 KB
• 시간: 1420 ms

리뷰

• 수업 때 배웠던 sliding window (또는 찾아보니 inchworm이라고도 하는 것 같다.) 응용 문제
• 정수 범위 주의
• 계산 결과에 실수가 있었는데 어째 잘 나오길래 맞왜틀 한 10번은 한 것 같다.
  • 다양한 TC를 만들어보도록 하자. 특히 edge case 잘 파악하자.
• visit 쓸 생각을 왜 못했지??