[Algorithm][LeetCode 1550] Three Consecutive Odds

연속된 홀수 판별하기 (Three Consecutive Odds)

문제: 주어진 정수 배열 arr에 대해, 연속된 홀수 숫자 3개가 존재하면 true를 반환하고, 그렇지 않으면 false를 반환하라.

1. 접근 방식

1. 연속된 홀수의 개수를 카운트할 변수 count를 생성한다.
2. 배열을 순회하면서 현재 숫자가 홀수면 count를 1 증가시킨다.
3. 짝수가 나오면 count를 0으로 초기화한다.
4. count가 3이 되는 순간 true를 반환한다.
5. 끝까지 반복했지만 3이 되지 않으면 false를 반환한다.

2. 자바스크립트 코드

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var threeConsecutiveOdds = function(arr) {
    let count = 0;
    for (let num of arr) {
        if (num % 2 === 1) { // 문제 constraints 상 양의 정수이므로 Math.abs는 생략 가능
            count++;
            if (count === 3) return true;
        } else {
            count = 0;
        }
    }
    return false;
};

3. 예시

threeConsecutiveOdds([2, 6, 4, 1]); 
// 출력: false

threeConsecutiveOdds([1, 2, 34, 3, 4, 5, 7, 23, 12]);
// 출력: true (연속된 홀수 [5, 7, 23] 존재)

4. 소수 탐색 문제로 바뀌었을 경우

만약 "3개의 연속된 소수"를 찾는 문제라면 아래와 같이 소수 판별 함수를 따로 작성해야 한다.

function isPrime(n) {
    if (n < 2) return false;
    for (let i = 2; i * i <= n; i++) {
        if (n % i === 0) return false;
    }
    return true;
}

소수 판별에서 i * i <= n까지만 검사해도 되는 이유

1. 어떤 수 n이 합성수라면, n = a × b 형태로 표현 가능하다.
2. 만약 a > √n이고 b > √n이라면 a × b > n이 되어 모순이다.
3. 즉, a나 b 중 하나는 반드시 √n 이하이어야 한다.

예를 들어, n = 100일 때:

• 곱셈쌍: 2×50, 4×25, 5×20, 10×10, 20×5, 25×4, 50×2
• 10×10 이후는 앞의 쌍을 뒤집은 것에 불과하므로 중복이다.
• 따라서 √100 = 10까지만 검사해도 모든 경우를 확인한 것과 같다.

5. 마무리

이 문제는 기본적인 순회와 조건문만으로 풀 수 있지만, 입력 조건이 소수처럼 바뀌면 약간의 수학적 지식이 필요하다.