분류 - 투포인터
레벨 - 골드4
문제
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
출력
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
예제 입력 1 복사
10 15 5 1 3 5 10 7 4 9 2 8
예제 출력 1 복사
2
풀이
투포인터를 활용한풀이에요. 이 문제 역시 전에 C++로 풀어본 문제인데 맨 처음에는 구간합을 구한 값을 N-1부터 확인하면서 lower_bound(이진탐색)을 통해 S- arr[N-1]값을 찾아서 그 값이 arr[N-1]-찾은 값이 S보다 큰 것을 찾아 그 길이 중 가장 짧은 것을 비교하는 풀이를 했었는데요.
이것은 투포인터를 이용하여 길이를 조정해가며 푸는 풀이입니다.
요번부터는 대부분의 기업이 사용하는 Programmers의 양식과 최대한 유사하게 solution함수를 만들어서 사용할 예정이에요.
1. N과 S를 각각 받아 저장하고 수열을 받아 arr에 저장한 후 맨 앞에 0을 추가해준다. 0을 추가해 주는 이유는 구간합을 사용해 길이를 구할 때 사용하기 편하려고 그렇게 했다. (아래에 설명)
- solution -
2. prefSum은 구간합을 저장하는 배열로 prefSum[k] = arr[0]~arr[k]까지의 합을 저장하는 배열이다.
prefSum[1]= arr[1]+prefSum[0](==0)이고 prefSum[2] = arr[2]+prefSum[1](arr[1]+prefSum[0])... 이기때문.
3. 만일 prefSum[N]이 S보자 작을 경우는 수열의 모든 수를 합한 값이 S보다 커질 수 없는 경우이므로 0을 리턴한다.
4. 아닐 경우에는 lt(왼쪽끝)와 rt(오른쪽 끝)인덱스를 지정하여 res(최소 길이)를 찾는다.
4-1. prefSum[rt]-prefSum[lt]는 (lt+1)~rt까지의 부분합을 구한 것이다. rt까지의 구간합(0~rt)에서 lt까지의 구간합(0~lt)을 빼면 0~rt까지 중 0~lt까지의 합만 뺀 것이기 때문에 (lt+1)~rt까지의 합을 구할 수 있는 것이다. 하지만 인덱스로 보면 rt-lt는 (lt+1)~rt의 길이가 된다.
4-2. 예를들어 rt가 4고 lt가 2라고 했을때 prefSum[4]-prefSum[2](10-3) 는 arr[3(lt+1)]과 arr[4(rt)]의 합(7)이다. 범위는lt+1~rt이지만 rt-lt는 이 길이인 2가 나온다.
4-3. 수열(arr)의 모든수를 더했을 때만 S가 나온다고 가정해보자. 만일 prefSum의 첫 인덱스부터 구간합이 더해진다면 길이를 구할 때 rt-lt+1을 해줘야 할것이다. 마지막 인덱스는 N-1이고 N-1-0을 한다고 해도 최대길이는 N이 나오기 때문이다. 따라서 위에서 arr의 맨 처음에 0을 넣어주고 총 길이를 N+1로 해주어 단순히 rt-lt가 길이가 나오도록 조정한 것이다.
5. 만약 prefSum[rt]-prefSum[lt]가 S보다 작을 때는 숫자를 더 더해줘야하기 때문에 rt를 늘려준다.
6. 만약 prefSum[rt]-prefSum[lt]가 S보다 크다면 최소길이를 구하기 위해 lt를 하나 늘려주고 전에 구한 res와 현재의 rt-lt중 작은 값을 취하고 res를 리턴해 준다.
7. 만일 rt가 N보다 커진다면 루프를 멈춘다.
코드
const input = require("fs").readFileSync("./dev/stdin").toString().trim().split("\n");
var line1 = input[0].trim().split(' ');
var arr = input[1].trim().split(' ').map(function(a){return parseInt(a);});
var N = line1[0];
var S = line1[1];
arr.unshift(0);
var solution = function(N, S, arr){
var prefSum = Array.from({length: parseInt(N)+1}, (v, i)=>0);
prefSum.forEach(function(_,i){
if(i==0) return;
prefSum[i]+=prefSum[i-1]+arr[i];
});
if(prefSum[N]<S){ // 모든 수의 합이 목표(S)보다 작을 때
return 0;
}
var lt = 0; rt = 0;
var res=N;
while(rt<=N){
if(prefSum[rt]-prefSum[lt]<S){
rt++;
}else{
res = Math.min(res,(rt-lt));
lt++;
}
}
return res;
}
console.log(solution(N, S, arr))
전에 풀었던 다른 방법의 참고용 코드
#include <iostream>
#include <vector>
using namespace std;
int N, S;
vector<int> arr;
int main() {
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(0);
cin >> N >> S;
arr.resize(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
if (i > 0)
arr[i] += arr[i - 1];
}
int ans = N;
for (int i = N - 1; i >= 0; i--) { // 까지
int len;
int sum = arr[i];
if (sum < S) break;
int lb = lower_bound(arr.begin(), arr.end(), arr[i] - S) - arr.begin();
if (arr[i] - arr[lb] >= S)
len = i - lb;
else if(lb>0 && arr[i] - arr[lb - 1] >= S)
len = i - lb + 1;
if (ans > len) ans = len;
}
if (arr.back() < S) cout << 0;
else cout << ans;
return 0;
}
'알고리즘 > BOJ 풀이(JS)' 카테고리의 다른 글
[BOJ] 최소비용 구하기(1916) (0) | 2021.05.12 |
---|---|
[BOJ] 멀티탭 스케줄링(1700) (0) | 2021.05.07 |
[BOJ] 빗물 (14719) (0) | 2021.05.07 |
[BOJ] 괄호의 값(2504) (0) | 2021.05.07 |
[BOJ]연산자 끼워넣기(14888) (1) | 2021.05.07 |
댓글