[JAVA] 백준 슬라이딩 윈도우 부수기

 

서론

매번 후순위로 밀리던 슬라이딩 윈도우 문제를 풀어보려고 한다.

 

 

2559 수열 - 실버3

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

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());

    st = new StringTokenizer(br.readLine());
    int[] arr = new int[n];
    int maxSum = -10_000_001;
    int sum= 0;
    int tmp = k - 1;
    for (int i =0; i<n; i++) {
        arr[i] = Integer.parseInt(st.nextToken());

        sum += arr[i];

        if (i < tmp) {
            continue;
        }

        if (i >= k) {
            sum -= arr[i - k];
        }

        if (sum > maxSum) {
            maxSum = sum;
        }
    }

    System.out.println(maxSum);
}

그냥 앞뒤 숫자를 큐스택처럼 빼는 문제였다. 어렵지 않다

 

 

21921 블로그 - 실버3

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

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int x = Integer.parseInt(st.nextToken());

    st = new StringTokenizer(br.readLine());
    int[] visitorCnt = new int[n];

    int tmp = x - 1;
    int cnt = 0;
    int maxSum = 0;
    int currentSum  =0;
    
    for (int i =0; i<n; i++) {
        visitorCnt[i] = Integer.parseInt(st.nextToken());
        currentSum += visitorCnt[i];

        if (i < tmp)
            continue;

        if (i > tmp) {
            currentSum -= visitorCnt[i-x];
        }

        //갱신작업
        if (currentSum == maxSum) {
            cnt ++;
        }

        if (currentSum > maxSum) {
            maxSum = currentSum;
            cnt = 1;
        }
    }

    //출력
    if (maxSum == 0) {
        System.out.println("SAD");
    } else {
        System.out.println(maxSum + "\n" + cnt);
    }
}

윗 문제와 굉장히 유사하다. 어렵지 않다

 

 

12891 DNA 비밀번호 - 실버2

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

class Main {
    static int[] currentAlpha;
    static int[] requiredAlpha;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        requiredAlpha = new int[4];
        currentAlpha = new int[4];
        
        int s = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        String input = br.readLine();
        
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            requiredAlpha[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < p; i++) {
            increaseCurrentAlpha(input.charAt(i));
        }

        int result = 0;
        if (check()) {
            result++;
        }

        for (int i = 1; i < input.length() + 1 - p; i++) {
            decreaseCurrentAlpha(input.charAt(i - 1));
            increaseCurrentAlpha(input.charAt(i + p - 1));
            
            if (check()) {
                result++;
            }
        }

        System.out.println(result);
    }

    private static void decreaseCurrentAlpha(char c) {
        if (c == 'A') {
            currentAlpha[0]--;
        } else if (c == 'C') {
            currentAlpha[1]--;
        } else if (c == 'G') {
            currentAlpha[2]--;
        } else if (c == 'T') {
            currentAlpha[3]--;
        }
    }

    private static boolean check() {
        boolean pass;
        pass = true;
        for (int j = 0; j < 4; j++) {
            if (requiredAlpha[j] > currentAlpha[j]) {
                pass = false;
                break;
            }
        }
        return pass;
    }

    private static void increaseCurrentAlpha(char c) {
        if (c == 'A') {
            currentAlpha[0]++;
        } else if (c == 'C') {
            currentAlpha[1]++;
        } else if (c == 'G') {
            currentAlpha[2]++;
        } else if (c == 'T') {
            currentAlpha[3]++;
        }
    }
}

" 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다."라는 조건때문에 쉬워진 문제인 것 같다. 알파벳이 26개밖에 안되기 때문에 배열로 최적화한 풀이들이 많아서 재미있었다. 

 

 

2531 회전 초밥 - 실버1

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

class Main {
    static int max;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int plateCnt = Integer.parseInt(st.nextToken());
        int typeCnt = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int coupon = Integer.parseInt(st.nextToken());

        int[] plate = new int[plateCnt+k-1]; //k-1개만큼 배열 늘리기
        int[] current = new int[typeCnt+1]; //접시타입별 개수 저장용
        int currentTypeCnt = 0;
        max = 0;

        for (int p =0; p<plate.length; p++) {
            //입력받기
            if (p < plateCnt) {
                plate[p] = Integer.parseInt(br.readLine());
            }

            int type = plate[p];
            
            //현재값 갱신
            current[type] ++;
            if (current[type] == 1) {
                currentTypeCnt++;
            }

            //사이클 갱신용
            if (p < k-1) {
                plate[plateCnt + p] = type;
                continue;
            }

            //앞에꺼 빼주기
            if (p >= k) {
                int prevType = plate[p - k];
                current[prevType] --;
                if (current[prevType] == 0) {
                    currentTypeCnt--;
                }
            }

            //max값 갱신
            updateMax(currentTypeCnt, current, coupon);
        }

        System.out.println(max);
    }

    private static void updateMax(int currentTypeCnt, int[] current, int coupon) {
        int tmpCurrentTypeCnt = currentTypeCnt;

        //쿠폰고려해서 typecnt 갱신
        if (current[coupon] ==0) {
            tmpCurrentTypeCnt++;
        }

        if (tmpCurrentTypeCnt > max) {
            max = tmpCurrentTypeCnt;
        }
    }
}

사이클만 고려하면 어렵지 않은 문제다. 

슬라이딩윈도우 초기값을 채우는 과정과 사이클을 위한 배열 추가값을 더하는 과정을 한 번에 진행하느라 코드가 깔끔하지 못한 것 같다. 나중에 나도 못알아볼 것 같아서 주석이라도 열심히 달았다

 

 

15565 귀여운 라이언 - 실버1

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

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());

    //라이언 인형 위치 저장용
    int[] lion = new int[n]; //최대 라이언인형 개수는 n개 -> n개로 넉넉하게 잡음
    int lionIdx=  0; //저장된 라이언 인형 개수

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; i++) {
        int doll = Integer.parseInt(st.nextToken());
        if (doll == 1) {
            lion[lionIdx++] = i;
        }
    }

    //전체 라이언인형 개수가 k보다 작으면 -1 출력 후 종료
    if (lionIdx < k) {
        System.out.println(-1);
        return;
    }

    //lion인형 k개를 유지하면서 범위크기 비교
    int min= Integer.MAX_VALUE;
    int end = lionIdx - k + 1;
    for (int i = 0; i< end; i++) {
        int nextIdx = i + k - 1;
        int tmp = lion[nextIdx] - lion[i] + 1;
        if (tmp < min) {
            min = tmp;
        }
    }

    System.out.println(min);
}

원래는 전체 배열에 대해서 start와 end를 조절하면서 라이언 인형 개수를 맞추고자 했는데, 조금만 생각을 틀면 훨씬 빨리 구할 수 있는 방법이 있었다. 내가 생각한 풀이는 아니고 인터넷 풀이를 참고해서 풀었다. (참고한 블로그: https://chan-it-note.tistory.com/100)

1. 라이언 인형 위치만 배열에 저장한다
2. 라이언 인형 배열에서 투포인터를 사용하여 라이언인형 K개일 때 최소 범위사이즈를 구한다

 

 

1593 문자 해독 - 골드5

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

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int wordLength = Integer.parseInt(st.nextToken());
    int totalLength = Integer.parseInt(st.nextToken());

    String word = br.readLine();
    String totalWord = br.readLine();

    int[] wordCnt = new int[58];
    for (int i = 0; i < wordLength; i++) {
        wordCnt[word.charAt(i) - 'A']++;
    }

    //초기값 넣기
    int[] currentCnt = new int[58];
    for (int i = 0; i < wordLength; i++) {
        currentCnt[totalWord.charAt(i) - 'A']++;
    }

    int result = 0;
    if (Arrays.equals(currentCnt, wordCnt)) {
        result++;
    }
    
    //슬라이딩 윈도우 수행
    int endWindow = totalLength - wordLength + 1;
    for (int i = 1; i < endWindow; i++) {
        currentCnt[totalWord.charAt(i-1) - 'A']--;
        currentCnt[totalWord.charAt(i+wordLength - 1) - 'A']++;

        if (Arrays.equals(currentCnt, wordCnt)) {
            result++;
        }
    }

    System.out.println(result);
}

슬라이딩 윈도우 방법으로 하나씩 비교하면 되는 문제다.

항상 배열 값 하나하나 비교하는 방식을 사용했는데, 다른 풀이를 보다가 Arrays.equals로 비교가능하다는 걸 알게되었다.

 

 

2096 내려가기 - 골드5

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

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());

    int[] minScore = new int[3];
    int[] maxScore = new int[3];

    for (int i = 0; i < n; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        int[] tmpMinScore = new int[3];
        tmpMinScore[0] = getMin(minScore[0], minScore[1]) + a;
        tmpMinScore[1] = getMin(minScore[0], minScore[1], minScore[2]) + b;
        tmpMinScore[2] = getMin(minScore[1], minScore[2]) + c;

        minScore = tmpMinScore;

        int[] tmpMaxScore = new int[3];
        tmpMaxScore[0] = getMax(maxScore[0], maxScore[1]) + a;
        tmpMaxScore[1] = getMax(maxScore[0], maxScore[1], maxScore[2]) + b;
        tmpMaxScore[2] = getMax(maxScore[1], maxScore[2]) + c;

        maxScore = tmpMaxScore;
    }

    int realMax = 0;
    int realMin = Integer.MAX_VALUE;

    for (int i = 0; i < 3; i++) {
        realMax = Math.max(realMax, maxScore[i]);
        realMin = Math.min(realMin, minScore[i]);
    }

    System.out.println(realMax + " " + realMin);
}

슬라이딩 윈도우보단 dp로 보는게 맞는 문제인 것 같다.

 

 

3078 좋은 친구 - 골드4

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

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    //좋은 친구 쌍 = 결과값
    long goodFriendPairCnt = 0L;

    int n = Integer.parseInt(st.nextToken());
    int windowSize = Integer.parseInt(st.nextToken()) + 1; //넘으면 친구가 아니다 = 같으면 친구다

    //이름 입력 받기
    int[] nameLen = new int[n];
    for (int i = 0; i < n; i++) {
        nameLen[i] = br.readLine().length();
    }

    //현재까지 이름 길이 개수 저장 - 시간줄이기 용
    int[] currentCnt = new int[21];
    for (int i=0; i<windowSize; i++) {
        currentCnt[nameLen[i]] ++;
    }

    //초기 비교, 좋은 친구 쌍 갱신
    for (int i =0; i<21; i++) {
        if (currentCnt[i] > 1) {
            goodFriendPairCnt += ((long)(currentCnt[i]) * (currentCnt[i] - 1) / 2);
        }
    }

    //슬라이딩 윈도우 -> 추가된 애랑 앞에 친구들 비교만 하면 됨
    for (int i = windowSize; i< n; i++) {
        currentCnt[nameLen[i - windowSize]]--;
        currentCnt[nameLen[i]]++;
        
        goodFriendPairCnt += (currentCnt[nameLen[i]] - 1);
    }

    System.out.println(goodFriendPairCnt);
}

이름 길이 개수를 저장하지 않아서 시간초과가 발생했고, 친구 쌍 개수가 300,000 * 300,000 = 90,000,000,000 정도로 int 최대값을 넘어가는 경우를 고려하지 않아서 한 번 틀렸다.

 

슬라이딩 윈도우 과정에서 빠르게 비교할 수 있도록 개수값을 캐싱해두는 것과, 숫자범위만 잘 처리해주면 어렵지는 않은 문제다.

 

 

15961 회전 초밥 - 골드4

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

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int typeCnt = Integer.parseInt(st.nextToken());
    int winSize = Integer.parseInt(st.nextToken());
    int couponNum = Integer.parseInt(st.nextToken());

    int[] tmpArr = new int[winSize]; //i % winSize 값을 임시로 채울 배열
    int[] frontArr = new int[winSize]; //0 ~ winSize 값을 채우는 배열
    int[] currentCnt = new int[typeCnt + 1]; //초밥 타입별 개수 저장할 배열

    int currentTypeCnt = 0; //현재까지 타입개수
    int maxTypeCnt = 0; //결과

    //windowSize까지 채워주기
    for (int i = 0; i < winSize; i++) {
        int num = Integer.parseInt(br.readLine());
        frontArr[i] = num;
        tmpArr[i] = num;

        currentCnt[num]++;
        if (currentCnt[num] == 1) {
            currentTypeCnt++;
        }
    }

    int plusFood = (currentCnt[couponNum] == 0) ? 1 : 0; //쿠폰 초밥 추가 가능여부
    if (currentTypeCnt + plusFood > maxTypeCnt) {
        maxTypeCnt = currentTypeCnt + plusFood;
    }

    //슬라이딩 윈도우
    for (int i = winSize; i < n; i++) {
        int num = Integer.parseInt(br.readLine());

        //현재 값 추가
        currentCnt[num]++;
        if (currentCnt[num] == 1) {
            currentTypeCnt++;
        }

        //이전값 계산 -> tmpArr 에 저장해둔 값 사용
        int prevNum = tmpArr[(i - winSize) % winSize];
        currentCnt[prevNum]--;
        if (currentCnt[prevNum] == 0) {
            currentTypeCnt--;
        }

        plusFood = (currentCnt[couponNum] == 0) ? 1 : 0; //쿠폰 초밥 추가 가능여부
        if (currentTypeCnt + plusFood > maxTypeCnt) {
            maxTypeCnt = currentTypeCnt + plusFood;
        }

        tmpArr[i % winSize] = num;
    }

    //마지막 값들 처리
    for (int i = 0; i < winSize - 1; i++) {
        int prevNum = tmpArr[(n - winSize + i) % winSize];
        currentCnt[prevNum]--;
        if (currentCnt[prevNum] == 0) {
            currentTypeCnt--;
        }

        //미리 저장해둔 값 사용
        currentCnt[frontArr[i]]++;
        if (currentCnt[frontArr[i]] == 1) {
            currentTypeCnt++;
        }

        plusFood = (currentCnt[couponNum] == 0) ? 1 : 0; //쿠폰 초밥 추가 가능여부
        if (currentTypeCnt + plusFood > maxTypeCnt) {
            maxTypeCnt = currentTypeCnt + plusFood;
        }
    }

    System.out.println(maxTypeCnt);
}

실버문제와 거의 동일한 문제다. 아마 입력값 범위만 달라진 것 같다.(시간초과가 날까봐 조마조마했다)

 

입력으로 들어오는 300만개 데이터를 다 저장할 수 없지만, 슬라이딩 윈도우를 위한 이전 값은 저장이 필요했다. 그래서 k크기만큼만 저장하고, 나머지 연산자를 열심히 사용해줬다. 

 

나는 총 세 부분으로 나눠서 문제를 풀었다. 

1. 0 ~ k-1까지 처리 (초기값 저장 위함)
2. k ~ n 까지 처리 (슬라이딩 윈도우로 갱신)
3. 0 ~ k-1까지 처리 (순환 처리)

 

저장소는 이전 값을 저장할 tmpArr 과 0~k-1까지 값을 저장할 frontArr을 사용하였다. 

슬라이딩 윈도우 과정에서 윈도우 사이즈를 벗어나 빼줘야하는 값은 tmpArr에서 빼왔고, 

순환 처리 과정에서는 frontArr 값을 사용했다.

 

 

23295 스터디 시간 정하기 1 - 골드3

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

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int manCnt = Integer.parseInt(st.nextToken());
    int time = Integer.parseInt(st.nextToken());

    int[] arr = new int[100_001]; //들어오고 나가는 사람 기록용(들어오면 1, 나가면 -1)
    int[] sum = new int[100_001]; //만족도 캐싱용

    //입력받기
    for (int i = 0; i < manCnt; i++) {
        int cnt = Integer.parseInt(br.readLine());

        for (int j = 0; j < cnt; j++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            arr[start]++;
            arr[end]--;
        }
    }

    int startTime = 0;
    int endTime = time;
    long maxScore = 0;
    long currentScore = 0;

    //초기값 계산
    int tmpScore = 0; //현재 나가거나 들어온 사람 값
    for (int i = 0; i < time; i++) {
        tmpScore += arr[i];
        sum[i] = tmpScore; //캐싱
        currentScore += tmpScore;
    }

    if (currentScore > maxScore) {
        maxScore = currentScore;
    }

    //슬라이딩 윈도우
    for (int i = time; i < arr.length; i++) {
        currentScore -= sum[i - time]; //캐싱한 값 빼주기

        tmpScore += arr[i];
        sum[i] = tmpScore;
        currentScore += tmpScore;

        if (currentScore > maxScore) {
            maxScore = currentScore;

            startTime = i - time + 1;
            endTime = i + 1; //시간범위는 1 더해줘야함
        }
    }

    System.out.println(startTime + " " + endTime);
}

감도 안잡혀서 풀이를 찾아봤다. 들어오고 나가는 사람의 수를 체크하고, 슬라이딩 윈도우 방식으로 최댓값을 구해주면 어렵지 않게 구할 수 있었다. 아이디어를 찾는 게 가장 중요했다. (+ 범위값을 잘 봐야한다. long으로 안하면 틀린다)

 

 

5444 시리얼 넘버 - 골드1

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

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int tcCnt = Integer.parseInt(br.readLine());
    for (int t = 0; t < tcCnt; t++) {
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] dp = new int[2][m];
        Arrays.fill(dp[0], -1);
        Arrays.fill(dp[1], -1);
        dp[1][0] = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int serialNum = Integer.parseInt(st.nextToken());
            int current = i % 2;
            int prev = (i + 1) % 2;

            for (int j = 0; j < m; j++) {
                if (dp[prev][j] == -1) {
                    continue;
                }

                dp[current][j] = Math.max(dp[current][j], dp[prev][j]);

                // 선택하는 경우
                int next = (j + serialNum) % m;
                if (dp[current][next] == -1 || dp[current][next] < dp[prev][j] + 1) {
                    dp[current][next] = dp[prev][j] + 1;
                }
            }
        }

        System.out.println(dp[(n - 1) % 2][0]);
    }
}

문제유형은 슬라이딩 윈도우라고 되어있는데, 그냥 순환하는 dp문제였다. 아이디어는 떠올렸는데 관련 문제를 푼 경험이 없어서 애를 먹었다.

 

dp배열 크기를 줄이기 위해 %m을 사용하였고, 이전 데이터를 누적하기 위해 2개의 행도 사용해줬다. 2개의 행도 %2로 굉장히 아껴썼다. 신박한 유형이라 굉장히 재미있었다!

 

 

마치며..

슬라이딩 윈도우의 느낌은 알았는데, 아직 범위를 고려해서 깔끔하게 코드를 짜는 숙련도는 부족한 것 같다. 한 10개는 더 풀어봐야할 듯 하다.