양의 정수로 이루어진 배열에서 연속적으로 증가하는 숫자들로 구성된 가장 긴 부분 배열의 길이를 구하는 함수를 while 문을 사용해 작성해 보겠습니다.
문제 이해하기
배열 내에서 값이 1씩 연속해서 증가하는 구간 중 가장 긴 구간의 길이를 반환하면 됩니다.
예를 들어, 입력 배열이 다음과 같다면 −
const input = [6, 7, 8, 6, 12, 1, 2, 3, 4] --> [1,2,3,4]
연속된 숫자 구간은 [1, 2, 3, 4]가 가장 길므로 출력 결과는 다음과 같습니다.
4
또 다른 예시로, 입력 배열이 다음과 같다면 −
const input = [5, 6, 1, 8, 9, 7] --> [8,9]
연속된 숫자 구간은 [8, 9]뿐이므로 출력 결과는 다음과 같습니다.
2
코드 구현
그럼 이제 while 문을 활용한 함수 코드를 작성해 보겠습니다. 핵심 아이디어는 배열을 처음부터 끝까지 순회하면서, 현재 요소가 바로 앞 요소보다 정확히 1 크면 카운트를 늘리고, 그렇지 않으면 카운트를 1로 초기화하는 것입니다. 그리고 순회하는 동안 최대 카운트 값을 계속 갱신합니다.
const arr = [6, 7, 8, 6, 12, 1, 2, 3, 4];
const arr1 = [5, 6, 1, 8, 9, 7];
const findLongestSub = arr => {
let count = 1, len = 0, max = 1;
while(len < arr.length){
if(arr[len] === arr[len - 1] + 1){
count++;
if(max < count){
max = count;
}
}else{
count = 1;
};
len++;
};
return max;
};
console.log(findLongestSub(arr));
console.log(findLongestSub(arr1));동작 원리 살펴보기
- count: 현재 진행 중인 연속 구간의 길이를 저장하며, 초기값은 1입니다.
- len: 배열을 순회하는 인덱스 역할을 하는 변수입니다.
- max: 지금까지 발견한 가장 긴 연속 구간의 길이를 저장합니다.
while 루프 안에서 현재 요소 arr[len]이 이전 요소 arr[len - 1] + 1과 같으면 두 숫자가 연속된 것이므로 count를 1 증가시키고, 그 값이 max보다 크면 max를 갱신합니다. 연속되지 않는 경우에는 count를 1로 되돌려 새로운 구간 탐색을 시작합니다.
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
4 2
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)으로 매우 효율적이며, 추가 공간도 상수 수준(O(1))만 필요합니다.