요새 풀이

• 문제(알고스팟): https://algospot.com/judge/problem/read/ITES
• 제한시간: 15초

문제에서 주의할 점

• 입력을 직접 생성해야 한다.
  • A[0] = 1983 A[i] = (A[i-1] * 214013 + 2531011) % 2^32
  • 2^32 은 Integer의 범위를 벋어난다. 따라서 long이나 double을 사용해야 한다.
  • Math.pow(2, 32)을 매번 호출하면 느릴 수 있다.
• 테스트 케이스 C(1 <= C <= 20)
• 의미있는 값 (비교해야 하는 값) K(1 <= K <= 5,000,000) - 오백만
• 순차적으로 입력되는 입력값 N(1 <= N <= 50,000,000) - 오천만

최악의 경우 5천만개의 입력이 있을 수 있다. 따라서, 입력을 생성하고 이를 어딘가에 저장하는 형태를 취하면, 시간 초과 또는 메모리 초과가 발생한다.

결국 입력을 집접 순차적으로 생성하면서, 해당 입력값을 가지고, 의미있는 값을 바로 바로 비교하는 행태를 취해야 한다.

문제에서 주어진 힌트

• 문제에서 수열 {1,4,2,1,4,3,1,6}, K가 7 인 부분 수열을 구할때

  • {1,4,2} , {4,2,1} , {2,1,4}, {4,3}, {1,6} 순서대로 구하라고 되어 있다.

  • 즉 1 입력되고 {1} K 비교

  • 4 입력되고 {1, 4} K비교

  • 2 입력되고 {1,4,2} K비교--> 답이 나왔음 그럼 가장먼저 입력한 1 제외 {4,2}

  • 1 입력되고 {4,2,1} K비교 --> 답이 나왔음 그럼 가장먼저 입력한 4 제외 {2,1}

• 위와 같은 수서로 된다고 문제에서 알려주고 있다.

패턴을 보면 Queue형태를 취하고 있다는 것을 알 수 있다.

풀이코드

Java로 풀이함

3가지 방법을 사용해 보았음

1) Queue 인터페이스에, LinkedList로 구현

2) LinkedList을 그냥 Queue처럼 사용

3) 배열을 하나 만들어서 Queue로 구현

14초 선에서 패스됨

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class ITES {
    public static int K, N;
    public static double AIndexValue; // A[i]
    public static double m = Math.pow(2, 32); // 4294967296 (2^32)
    public static double b = 2531011; // 2531011 % m 동일 
    public static double d = 214013; // 214013 % m 동일

    public static int nextSignal() {
        AIndexValue = (AIndexValue * d + b) % m;
        return (int)(AIndexValue % 10000) + 1;
    }

    private static String getITES() {
        AIndexValue = 1983;
        Queue<Integer> signalQ = new LinkedList<Integer>();
        int sameKCount = 0;
        int sum = 0; // all queue signal sum

        for (int n = 0; n < N; n++) {
            int signal = nextSignal();

            // add input signal in queue
            signalQ.add(signal);
            sum = sum + signal;

            if (sum == K) {
                sameKCount++;
                // remove first input signal in queue
                sum -= signalQ.poll();
            } else if (sum < K) {
                continue;
            }

            // remove previous input signal in queue
            while (sum > K) {
                sum -= signalQ.poll();

                if (sum == K) {
                    sameKCount++;
                }
            }
        }

        return sameKCount + "\n";
    }

    private static String getITESArray() {
        AIndexValue = 1983;
        // 큐를 직접 구현 안하려고 LinkedList썻는데 시간 초과.
        // 메모리 크기 때문에 큐의 크기를 너무 크게 하면 안될꺼 같음.
        // K 의 max 는 5백만
        // value 는 % 10000 + 1 하니깐 결국 최대값 10000
        // 10000이 500개 있으면 5백만 나옴. (최선일때 500개...)
        // 만약 value가 1, 1, 1, 1, 1, 이런식이라면, (최악일때)5백만개 필요.
        // 5백만개 커버되나 확인필요.
        // int 는 4byte 이고 1000개 하면 4000 byte == 약 4k
        // 1만개 하면 40k, 10만개 400k, 100만개 4000k, 5백만개 20000k
        int queue[] = new int[5000001];
        int qHeadPoint = 0;
        int qTailPoint = 0;

        int sameKCount = 0;
        int sum = 0; // all queue signal sum

        for (int n = 0; n < N; n++) {
            int signal = nextSignal();

            // add input signal in queue
            queue[qTailPoint] = signal;
            qTailPoint++;
            if (qTailPoint > 5000000) {
                qTailPoint = 0;
            }

            sum = sum + signal;

            // remove previous input signal in queue
            while (sum > K) {
                sum -= queue[qHeadPoint];
                qHeadPoint++;
                if (qHeadPoint > 5000000) {
                    qHeadPoint = 0;
                }
            }

            if (sum == K) {
                sameKCount++;

                // remove first input signal in queue
                sum -= queue[qHeadPoint];
                qHeadPoint++;
                if (qHeadPoint > 5000000) {
                    qHeadPoint = 0;
                }
            }
        }

        return sameKCount + "\n";
    }

    private static String getITESLinkedList() {
        LinkedList<Integer> queue = new LinkedList<Integer>();
        AIndexValue = 1983;
        int sameKCount = 0;
        int sum = 0;

        for (int n = 0; n < N; n++) {
            int signal = nextSignal();
            queue.add(signal);
            sum = sum + signal;

            // remove previous input signal in queue
            while (sum > K) {
                sum -= queue.removeFirst();
            }

            if (sum == K) {
                sameKCount++;
            }
        }

        return sameKCount + "\n";
    }
    public static void main(String[] args) throws Exception {
        long start = System.currentTimeMillis();
        System.setIn(new FileInputStream("pro/study/structure/inputs/ITESSample.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int totalTC = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < totalTC; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            bw.write(getITESArray());
        }

        bw.write(System.currentTimeMillis() - start + "ms\n");

        br.close();
        bw.flush();
        bw.close();
    }
}