🎯문제
비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.
- 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
- 부분 수열의 합은 k입니다.
- 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
- 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.
수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.
제한사항
- 5 ≤ sequence의 길이 ≤ 1,000,000
- 1 ≤ sequence의 원소 ≤ 1,000
- sequence는 비내림차순으로 정렬되어 있습니다.
- 5 ≤ k ≤ 1,000,000,000
- k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.
입출력 예
| sequence | k | result |
|---|---|---|
| [1, 2, 3, 4, 5] | 7 | [2, 3] |
| [1, 1, 1, 2, 3, 4, 5] | 5 | [6, 6] |
| [2, 2, 2, 2, 2] | 6 | [0, 2] |
입출력 예 설명
입출력 예 #1
[1, 2, 3, 4, 5]에서 합이 7인 연속된 부분 수열은 [3, 4]뿐이므로 해당 수열의 시작 인덱스인 2와 마지막 인덱스 3을 배열에 담아 [2, 3]을 반환합니다.
입출력 예 #2
[1, 1, 1, 2, 3, 4, 5]에서 합이 5인 연속된 부분 수열은 [1, 1, 1, 2], [2, 3], [5]가 있습니다. 이 중 [5]의 길이가 제일 짧으므로 해당 수열의 시작 인덱스와 마지막 인덱스를 담은 [6, 6]을 반환합니다.
입출력 예 #3
[2, 2, 2, 2, 2]에서 합이 6인 연속된 부분 수열은 [2, 2, 2]로 3가지 경우가 있는데, 길이가 짧은 수열이 여러 개인 경우 앞쪽에 나온 수열을 찾으므로 [0, 2]를 반환합니다.
✏️풀이
코드
class Solution {
public int[] solution(int[] sequence, int k) {
// 가장 짧은 길이, 수열의 합, 수열의 시작 위치
int min = Integer.MAX_VALUE, sum = 0, start = 0;
int[] answer = new int[2];
// 수열의 길이만큼 반복
for(int i = 0; i < sequence.length; i++) {
// 값을 더해줌
sum += sequence[i];
// 수열의 합이 k보다 클 경우
while(sum > k) {
// k보다 작거나 같아질 때까지 시작 위치를 옮겨가며 값을 빼줌
sum -= sequence[start++];
}
// 수열의 합이 k과 같다면
if(sum == k) {
// 시작 위치와 종료 위치의 길이가 min보다 작은지 비교
if(min > (i - start)) {
// min보다 작다면 min값을 변경해주고
min = i - start;
// answer에 값을 저장
answer[0] = start;
answer[1] = i;
}
}
}
return answer;
}
}설명
배열의 구간을 활용하였다.
아이디어는 이전에 풀었던 여러 방법들에 비해 매우 단순한 편에 속하는 것 같다.
반복문을 진행하면서 수열의 값을 더해서 수열의 합을 구해준다. 이때 수열의 합이 k보다 크다면 k보다 작거나 같아질 때까지 수열의 시작 위치부터 값을 빼준다. 수열의 합이 k보다 작거나 같아진다면 while문을 빠져나오게 된다.
이후 수열의 합을 확인해서 k와 같다면 min 값과 i - start를 비교해준다. min 값은 수열의 합이 k를 만족하는 수열의 (종료 위치 - 시작 위치)의 최솟값을 나타낸다.
i - start가 min보다 작을 경우 min 값을 변경해주고 answer에 시작, 종료 위치를 저장해준다.
위의 과정을 예를 들어서 설명해보면
| sequence | k | result |
|---|---|---|
| [1, 2, 3, 4, 5] | 7 | [2, 3] |
라는 값이 있다고 할 때,
sum = 0, min = Integer.MAX_VALUE, start = 0으로 초기화가 되어있다.
처음 반복문을 통해 sum = 1이 된다. while문과 if문 둘 다 성립하지 않기 때문에 계속 반복문을 진행한다. 2, 3도 더해주고 반복문을 진행한다.
4를 더해줄 때, sum의 값는 10이다. sum이 k보다 크기 때문에 while문에 들어가게 된다.
sum에서 수열의 시작 위치인 sequence[start]를 빼주고 start의 위치를 옮겨준다.
sum -= sequence[start++] 를 진행하면 10 - 1 = 9 이기 때문에 sum은 9가 되고, start = 1이 된다.
여전히 k보다 크기 때문에 위의 과정을 한번 더 반복한다. 9 - 2 = 7, start = 2가 된다.
while문을 빠져나온 뒤 sum의 값은 7이고 이는 if문에 성립한다.
if문에서는 min 값과 비교를 진행한다. 현재 min값은 Integer.MAX_VALUE이기 때문에 i - start가 더 작다. min = i - start = 3 - 2 = 1로 값을 변경해주고 answer에 시작과 종료의 인덱스를 넣어준다.
이처럼 위의 과정을 반복한 뒤에 나온 answer 배열을 반환하면 문제를 해결할 수 있다!
💡느낀 점
시간초과 때문에 힘들었다고 생각한지 얼마 안돼서 바로 이번 문제도 시간초과가 발목을 잡았다. 하지만 오늘은 다른 알고리즘 방식을 적용하여 문제를 해결할 수 있었다. 시간 역시도 초과가 나지 않고 생각보다 훨씬 좋은 효율을 보여 한층 성장한 기분이 들었다. 이렇게 문제를 풀면서 재밌기만 했으면 좋겠지만.. 안되겠지..?
링크
