13144 List of Unique Numbers [JAVA]

문제 풀이

https://www.acmicpc.net/problem/13144

주어진 N 길이의 수열에 대해 연속된 1개 이상의 수를 뽑았을 때 중복되지 않는 경우의 수를 구하면 된다.

 

이걸 조금 쪼개서 생각해보면

중복되지 않은 수열 A에 포함된 수 a가 추가될 때 경우의 수를 구해나가는 방식으로 쪼갤 수 있다.

즉, 1 2 3 이라는 수열에 1,2,3중 하나가 추가되는 경우를 생각해볼 수 있다.

 

각 경우에 대해 추가 후 새롭게 A를 만드는 경우는 아래 3가지다.

1 2 3 + 1 ->  2 3 1

1 2 3 + 2 -> 3 2

2 3 + 3 -> 3

 

또 여기서, 새롭게 A를 만들기 전에 기존 배열을 활용하여 만들 수 있는 경우의 수는

1 / 1 2 / 1 2 3

1 / 1 2 / 1 2 3 / 2 / 2 3

1/ 1 2 / 1 2 3 / 2 / 2 3 / 3

위와 같다.

잘 보면 공통점이 보인다.

 

제일 처음 수가 중복된 경우 현재 A의 길이만큼 경우가 추가된다.

그다음 수가 중복된 경우 현재 A의 길이 + (현재 A의 길이-1) 만큼 추가가 된다.

그 다음 수가 중복된 경우 A len + A len -1 + A len -2 가 추가된다.

 

즉, 이 문제를 위 식으로 치환해서 풀어낼 수 있다.

 

이를 위해 현재 A의 head의 idx를 저장하고 현재 A의 길이 len을 저장해야 한다.

 

만약 중복되었다면 중복된 위치 +1 의 위치가 다음 head가 될 것이고

이전 head ~ 중복된 위치 (pos)까지의 길이만큼은 len에서 빼주어야 한다.

 

이 과정을 n길이에 대해 쭉 반복해주면 해결된다.

 

여기서 주의할 점은 문제의 메모리 범위가 32MB밖에 되지 않는다는 점이다.

처음에는 Map을 사용해서 그런가 싶어 10만짜리 배열 두개로 변경해서 제출해봤지만 계속해서 메모리 초과가 발생했다.

 

1메가도 되지 않는 배열인데 이유가 뭘까 찾다 Scanner에서  BufferedReader로 바꿔봤더니.. 바로 통과가 되었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] numToIdxArr = new int[100001];
        Arrays.fill(numToIdxArr, -1);
        long cnt = 0;
        int head = 0;
        long len = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());

        int i = 0;
        while (st.hasMoreTokens()){
            arr[i] = Integer.parseInt(st.nextToken());
            if(numToIdxArr[arr[i]] >= 0){
                int pos = numToIdxArr[arr[i]];

                long mLen = len - (pos-head + 1);
                cnt += (((len+1)*len)/2 - ((mLen+1)*mLen)/2);

                for (int j = head; j <= pos; j++) {
                    numToIdxArr[arr[j]] = -1;
                }

                len -= (pos-head) + 1;
                head = pos + 1;
            }
            numToIdxArr[arr[i]] = i;
            len++;
            i++;
        }
//        for (int i = 0; i < n; i++) {
//            arr[i] = sc.nextInt();
//            if(numToIdxArr[arr[i]] >= 0){
//                int pos = numToIdxArr[arr[i]];
//                // math will reduce cal time
//                // len 5 , 2 idx change ->  5 + 4 +3
//                // 5 , p 2 h 0 -> p-h = 2
//                // h = 1 p =4 len 7
//                // x 1 2 3 4 5 6 7 4
//                // 7 + 6 + 5 +4
//                // 7 - (4-1+1)=3
//                //
//
//                long mLen = len - (pos-head + 1);
//                cnt += (((len+1)*len)/2 - ((mLen+1)*mLen)/2);
////                for (int j = 0; j <= (pos-head); j++) {
////                    cnt += len-j;
////                }
//
//                for (int j = head; j <= pos; j++) {
//                    numToIdxArr[arr[j]] = -1;
//                }
//
//                len -= (pos-head) + 1;
//                head = pos + 1;
//            }
//            numToIdxArr[arr[i]] = i;
//            len++;
//        }

        cnt += ((len+1)*len)/2;

        System.out.println(cnt);
    }


}