[백준2559/투포인터] 수열

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

2559번: 수열

문제가 워낙 쉬워서 문제풀이 구상없이 바로 코딩했다.

1. 아이디어 - 연달아있는 세개를 더한값과 그 다음값을 더하고 인덱스 1의 값을 뺀값이 같은지 비교하며 max값 갈아치우기 2. 시간복잡도 - O(N) = 100,000 < 2억 (가능) 3. 변수 - max값 : int - 온도리스트 : int[] - 앞 포인터의 합, 뒷포인터의 합 를 기준으로 풀어보았다.

 

1트

public class twoPointer2559 {
    static int N;
    static int K;
    static int[] tempList;
    static int preSum = 0;
    static int nextSum;
    static int max;

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        K = scanner.nextInt();

        tempList = new int[N];
        for (int i = 0; i < N; i++) {
            tempList[i] = scanner.nextInt();
        }

        countMax();
        System.out.println(max);
    }

    private static void countMax(){
        for (int i = 0; i < K; i++) {
            preSum += tempList[i];
        }

        for (int i = 0; i < N-K; i++) {
            nextSum = preSum - tempList[i] + tempList[i+K];
            max = Math.max(preSum,nextSum);
            preSum = nextSum;
        }

    }
}

인데 채점에서 틀렸다.
질문 게시판을 보니 전부 음수인 케이스가 커버 불가능했다.

예를들어 이런 케이스이면..

10 2
-3 -2 -4 -9 -1 -3 -7 -13 -8 -3

그리고 애당초 max할당 부분에서 max와 nextSum을 비교해야했는데 이전값을 비교했다.

 

2트

package com.JavaPractice;


import java.util.Scanner;

/*
문제링크 : https://www.acmicpc.net/problem/2559
* 1. 아이디어
* - 연달아있는 세개를 더한값과 그 다음값을 더하고 인덱스 1의 값을 뺀값이 같은지 비교하며 max값 갈아치우기
*
* 2. 시간복잡도
* - O(N) = 100,000 < 2억 (가능)
* 3. 변수
* - max값 : int
* - 온도리스트 : int[]
* - 앞 포인터의 합, 뒷포인터의 합
* */
public class twoPointer2559 {
    static int N;
    static int K;
    static int[] tempList;
    static int preSum = 0;
    static int nextSum;
    static int max;

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        K = scanner.nextInt();

        tempList = new int[N];
        for (int i = 0; i < N; i++) {
            tempList[i] = scanner.nextInt();
        }

        countMax();
        System.out.println(max);
    }

    private static void countMax(){
        for (int i = 0; i < K; i++) {
            preSum += tempList[i];
        }
        max = preSum;

        // nextSum으로 비교하는 방식이라면 음수인경우
        for (int i = 0; i < N-K; i++) {
            nextSum = preSum - tempList[i] + tempList[i+K];
            max = Math.max(max,nextSum);
            preSum = nextSum;
        }

    }
}

 

맞았다

 

이런 문제인 경우 max의 값이 int를 넘어가는 경우도 있으니 long을 사용해야하는지 O(N)계산을 해봐야한다.