[백준/JAVA] 2559번: 수열

🔺 문제

2559번: 수열

 

 

🔺 코드

1) 누적 합 풀이

- 시간 복잡도 : O(N)

import java.util.*;
import java.io.*;
 
public class Main {
    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 range = Integer.parseInt(st.nextToken());
        
        int[] A = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        // 누적 합 구하기
        int[] sum = new int[N];
        sum[0] = A[0];
        for(int i = 1 ; i < N ; i++) {
            sum[i] = sum[i-1] + A[i];
        }
 
        int max = sum[range - 1];
        for(int i = range - 1 ; i < N ; i++) {
            if(i >= range) {
                max = Math.max(max, sum[i] - sum[i-range]);
            }
        }
        
        System.out.println(max);
        
    }
}

✅ 해결 아이디어
✔ 누적 합 (prefix sum)
1. 값을 입력받고, 이를 기반으로 누적 합 배열 sum을 만든다. (Line 19-23)
2. 누적 합을 구하고, 이 중 최댓값을 구한다. (Line 27-29)

 

 

 

2) 슬라이딩 윈도우 풀이

- 시간 복잡도 : O(N)

import java.util.*;
import java.io.*;
 
public class Main {
    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 range = Integer.parseInt(st.nextToken());
        
        int[] A = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        // 슬라이딩 윈도우
        int sum = 0;
        int max = 0;
        
        for(int i = 0 ; i < N ; i++) {
            sum += A[i];
            
            if(i == range - 1) { // 최초에 나온 합을 최댓값으로 잡아 놓음
                max = sum;
            }
            if(i >= range) { // ⭐ 처음 길이를 벗어났을 때부터 한칸씩 밀며 최댓값 비교
                sum -= A[i - range];
                max = Math.max(max, sum);
            }
        }
        
        System.out.println(max);
    }
}

 

---

🔺 다른 풀이들

- 누적합, 슬라이딩 윈도우, 투 포인터 다 사용하셨다.

[자바] 백준 2559 - 수열 (boj java)

 

 

- 그냥 2중 for문으로 푸신 분들도 좀 있었다.

[백준] 수열 2559 [JAVA]

---

💬 느낀 점

슬라이딩 윈도우로 풀려고 했는데...

편한 누적 합으로 풀어버렸다...

 

다음엔 꼭 슬라이딩 윈도우로도 풀어보게따💪

 

1회독	2회독	3회독	4회독	5회독
V	11.28

 

 

(+ 11.28 2회독)

2중 for문으로 풀어버렸는데 다음에는 꼭 누적합/슬라이딩 윈도우로 풀어보겠다...

2중 for문 코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    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[] arr = new int[N];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int max = Integer.MIN_VALUE;
        
        for(int i = 0 ; i <= N - K ; i++) {
            int tmp = 0;
            for(int j = i ; j < i + K ; j++) {
                tmp += arr[j];
            }
            System.out.println(tmp);
            max = Math.max(max, tmp);
        }
 
        System.out.println(max);
    }
}
 

 

---

(참고)

✔ 슬라이딩 윈도우 풀이 참고

(Java) 백준 2559 - 수열

 

 

✔ 슬라이딩 윈도우 알고리즘 설명

[알고리즘] 투 포인터, 슬라이딩 윈도우 알고리즘 자바 구현 (백준 2003, 2559)