1. 문제 설명
2. 접근 방식
KEY WORD
: 구간합
& 투 포인터
데이터 크기가 10^5 이라서 시간복잡도가 O(n^2) 이상이면 안된다. 따라서 한번의 조회안에 모든 것을 끝내야 한다. 그러기 위해서 누적합을 사용하여 문제를 풀었다. 진행 방식은 다음과 같다.
- 입력을 누적합 배열(sum) 형태로 만든다. (다만 진짜 누적합의 시작은 sum[1] 부터 시작하고, sum[0]=0 으로 비워둔다.)
- left, right 포인터를 만들고 다음과 같이 움직인다.
(1) sum[right] - sum[left] < M 이면 right를 움직인다.
(2) sum[right] - sum[left] == M 이면 (right-left) 길이 기록 후에, right를 움직인다.
(3) sum[right] - sum[left] > M 이면 (right - left) 길이 기록 후에 left를 움직인다.
🤔 sum[right] - sum[left] > M 인데 left를 ++ 하는 이유
구간합이 M 이상인 경우 중 길이가 제일 짧은 경우의 수의 길이를 출력해야 한다. sum[right] - sum[left] > M 인 값을 현재 만났는데, 또 right++ 을 해버리면 이미 충족한 M 이상이란 요건에서 길이는 더 길어지기에 쓸모 없다.
따라서 sum[right] - sum[left] > M 이면 길이 기록 후, left를 올려서, 칸 수를 줄인다.
M으로 맞아 떨어지지 않을 수 있기 떄문에 sum[right] - sum[left] > M인 경우도 세어야 한다.
3. 코드 분석
import java.io.*;
import java.util.*;
public class Main {
// 구간 합 + 투 포인터
// 전 구역의 누적합을 구한다.
// sum[right] - sum[left] 와 target 값을 비교해서, right나 left를 이동 시킨다.
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 M = Integer.parseInt(st.nextToken());
long [] sum = new long [N+1];
// 1. 누적합 만들기
st = new StringTokenizer(br.readLine());
sum[0] = 0;
sum[1] = Integer.parseInt(st.nextToken());
for (int i = 2; i <= N; i++) {
sum[i] = sum[i-1] + Integer.parseInt(st.nextToken());
}
// 2. 투포인터로 값 구하기
int left = 0, right = 0;
long cur_sum = 0;
long cur_len = Integer.MAX_VALUE;
while (right <= N){
cur_sum = sum[right] - sum[left];
if(cur_sum == M){
cur_len = Math.min(cur_len, right -left);
right++;
} else if (cur_sum < M) {
right++;
} else {
cur_len = Math.min(cur_len, right -left);
left++;
}
}
System.out.println(cur_len == Integer.MAX_VALUE? 0 : cur_len);
}
}
'알고리즘 > 문제 풀이' 카테고리의 다른 글
99클럽 코테 스터디 5일차 TIL + Programmers 베스트 앨범 (0) | 2024.07.27 |
---|---|
99클럽 코테 스터디 4일차 TIL + Programmers 문자열 압축 (0) | 2024.07.25 |
99클럽 코테 스터디 3일차 TIL + Programmers 숫자 문자열과 영단어 java (0) | 2024.07.24 |
[백준] 1300 K번째 수 java 이해하기 쉬운 풀이^^ 🌟 (0) | 2024.07.24 |
[프로그래머스] 광물 캐기 풀이 java (0) | 2024.07.23 |