[백준/JAVA] 2559번: 수열
🔺 문제
2559번: 수열
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기
www.acmicpc.net
🔺 코드
1) 누적 합 풀이
- 시간 복잡도 : O(N)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
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);
}
}
|
cs |
✅ 해결 아이디어
✔ 누적 합 (prefix sum)
1. 값을 입력받고, 이를 기반으로 누적 합 배열 sum을 만든다. (Line 19-23)
2. 누적 합을 구하고, 이 중 최댓값을 구한다. (Line 27-29)
2) 슬라이딩 윈도우 풀이
- 시간 복잡도 : O(N)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
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);
}
}
|
cs |
🔺 다른 풀이들
- 누적합, 슬라이딩 윈도우, 투 포인터 다 사용하셨다.
[자바] 백준 2559 - 수열 (boj java)
문제 : boj2559 이하 설명에서 arr[i]는 입력으로 주어진 i번째 수를 뜻한다. 총 세 가지 방식으로 풀이를 진행한다. 1. 누적합 (prefix sum) prefix sum (누적합)을 미리 구해둬보자. 누적합 배열을 sumArr이라
nahwasa.com
- 그냥 2중 for문으로 푸신 분들도 좀 있었다.
[백준] 수열 2559 [JAVA]
출처 : www.acmicpc.net/problem/2559 문제 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 아래
hj-bank.tistory.com
💬 느낀 점
슬라이딩 윈도우로 풀려고 했는데...
편한 누적 합으로 풀어버렸다...
다음엔 꼭 슬라이딩 윈도우로도 풀어보게따💪
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 11.28 |
(+ 11.28 2회독)
2중 for문으로 풀어버렸는데 다음에는 꼭 누적합/슬라이딩 윈도우로 풀어보겠다...
2중 for문 코드 확인하기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
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);
}
}
|
cs |
(참고)
✔ 슬라이딩 윈도우 풀이 참고
(Java) 백준 2559 - 수열
슬라이딩 윈도우를 사용하는 문제이다. 기본 개념만 알고 있다면 쉽게 풀 수 있는 문제라서 슬라이딩 윈도우 개념 복습 차원에서 풀어보았다. 최종 코드 import java.io.BufferedReader; import java.io.InputSt
rovictory.tistory.com
✔ 슬라이딩 윈도우 알고리즘 설명
[알고리즘] 투 포인터, 슬라이딩 윈도우 알고리즘 자바 구현 (백준 2003, 2559)
투 포인터 알고리즘이란? ▶ 1차원 배열에 존재하는 순차적 부분 배열에 접근해야 할 때 두개의 점을 활용하여 중복 연산을 줄이는 알고리즘 예시 문제를 활용하여 알아보자. 문제 : https://www.acmi
hanyeop.tistory.com