프로그래머스의 숫자의 표현 문제를 함께 풀어보도록 하겠습니다.
문제
Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.
- 1 + 2 + 3 + 4 + 5 = 15
- 4 + 5 + 6 = 15
- 7 + 8 = 15
- 15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.
예제
입력: 15
출력: 4풀이 1
이 문제를 푸는 가장 단순 무식한 방법은 문제에서 나오는 것처럼 모든 경우의 수를 따져보는 것입니다.
맨 처음에는 1부터 시작해서 1 + 2 + 3 + ... 이런 식으로 더하고, 그 다음에는 2부터 시작해서 2 + 3 + 4 ... 이런 식으로 더하고요.
더하다보면 합이 점점 커질 것이고 만약에 그 합이 n과 동일해진다면 n을 연속된 자연수로 표한하는 방법를 하나 찾은 것이 되겠죠?
만약에 그 합이 n을 넘어간다면, 해당 숫자에서 시작하는 연속된 자연수로는 n을 표현할 수 없다는 뜻입니다.
이 Brute force 알고리즘은 이중 루프를 사용하면 어렵지 않게 구현할 수 있는데요.
외부 루프에서는 연속된 자연수를 시작할 숫자를 1부터 n까지 증가시키고,
내부 루프에서는 합이 n보다 작은 동안 합을 더해나가면 됩니다.
그럼 파이썬으로 이 알고리즘을 구현해볼까요?
def solution(n):
count = 0
for num in range(1, n + 1):
total = 0
while total < n:
total += num
num += 1
if total == n:
count += 1
return count같은 코드를 자바스크립트로 구현하면 다음과 같습니다.
function solution(n) {
let count = 0;
for (let num = 1; num <= n; num++) {
let total = 0;
let cur = num;
while (total < n) {
total += cur;
cur++;
}
if (total == n) {
count++;
}
}
return count;
}이 풀이의 시간 복잡도는 이중 루프로 인해서 O(n^2)이 되며, 공간 복잡도는 정해진 개수의 변수 외에는 추가 메모리를 사용하지 않기 때문에 O(1)입니다.
풀이 2
이 문제처럼 연속되는 범위를 탐색할 때 매우 효율적인 풀이 기법이 있습니다. 바로 슬라이딩 윈도우(Sliding Window)인데요.
기본 아이디어는 두 개의 포인터를 사용하여 윈도우가 시작하는 지점과 끝나는 지점을 이동시키는거죠. 그러면 윈도우의 길이를 유기적으로 늘렸다가 줄였다가 하면서 전체 범위를 스캔하는 효과가 납니다.
문제에서 주어진 예제와 같이 15가 입력으로 주어진다면, 우리는 아래와 같이 연속된 자연수를 나열할 수 있습니다.
그리고 구간의 시작 포인터는 숫자 1에 위치시키고, 종료 포인터는 숫자 2에 위치시키겠습니다.
v
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
total = 1여기서 시작 포인터는 현재 범위에서 제거할 숫자를 가리키고, 종료 포인터는 현재 범위에서 추가할 숫자를 가리킵니다.
따라서 맨 처음에는 연속된 숫자의 합이 1이 되는데요.
합이 15보다 작기 때문에 종료 포인터를 증가시켜 숫자 2가 범위에 들어오게 합니다.
v
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
total = 1 + 2 = 3숫자 2가 범위에 들어와서 합이 3이 되었지만 여전히 15에 턱없이 모자랍니다.
종료 포인터를 또 증가시켜야 합니다.
v
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
total = 1 + 2 + 3 = 6여전히 15보다 작습니다. 종료 포인터를 또 증가시키겠습니다.
v
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
total = 1 + 2 + 3 + 4 = 10여전히 15보다 작습니다. 종료 포인터를 또 증가시키겠습니다.
v
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
total = 1 + 2 + 3 + 4 + 5 = 15
count = 1드디어 처음으로 합이 15가 되는 자연수의 범위를 찾았습니다.
여기서 다음으로 15를 표현할 수 있는 범위를 찾으려면 다시 균형을 깨뜨려야겠죠?
시작 포인터와 종료 포인터를 동시에 증가시키면 됩니다.
v
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
total = 2 + 3 + 4 + 5 + 6 = 20그랬더니 합이 15보다 커져버렸습니다.
시작 포인터를 증가시켜 범위에 맨 앞에 있는 숫자를 제거해줍니다.
v
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
total = 3 + 4 + 5 + 6 = 18여전히 합이 15보다 크니, 시작 포인터를 또 증가시킵니다.
v
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
total = 4 + 5 + 6 = 15
count = 1 + 1 = 2두 번째로 합이 15가 되는 자연수의 범위를 찾았네요.
첫 번째와 찾았을 때와 동일하게 시작 포인터와 종료 포인터를 동시에 증가시킵니다.
v
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
total = 5 + 6 + 7 = 18이제 합이 15보다 커졌으니, 시작 포인터를 증가시킵니다.
v
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
total = 6 + 7 = 13합이 15보다 작아졌으니, 종료 포인터를 증가시킵니다.
v
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
total = 6 + 7 + 8 = 21합이 15보다 커졌으니, 시작 포인터를 증가시킵니다.
v
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
total = 7 + 8 = 15
count = 2 + 1 = 3합이 15가 되는 세 번째 자연수의 범위를 찾았습니다.
마찬가지로 시작 포인터와 종료 포인터를 동시에 증가시켜야 할 것입니다.
이런식으로 두 개의 포인터와 계속해서 반복적으로 밀땅을 하다보면, 결국 시작 포인터는 마지막 숫자를 가리키고, 종료 포인터는 벗어나는 순간, 즉 더 이상 범위에서 제거할 수 있는 숫자가 없는 상황이 올 것입니다.
v
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
total = 15
count = 3 + 1 = 4여기서 합이 15가 되는 마지막 자연수 범위를 찾게 됩니다.
지금까지의 사고 과정을 정리해보면 다음과 같이 일반화 할 수 있습니다.
- 범위의 합이 n보다 작다면 합을 크게 만들기 위해서 종료 포인터를 증가시켜 범위의 맨 뒤에 있는 숫자를 추가한다.
- 범위의 합이 n보다 크다면 합을 작게 만들기 위해서 시작 포인터를 증가시켜 범위의 맨 앞에 있는 숫자를 제거한다.
- 범위의 합이 n과 같다면 n을 연속한 자연수들로 표현하는 새로운 방법을 하나 찾은 것이다. 이 때, 시작 포인터와 종료 포인터를 동시에 증가시킨다.
이 알고리즘을 그대로 파이썬으로 구현해볼까요?
def solution(n):
count = 0
low, high = 1, 2
total = 1
while low < high:
if total < n:
total, high = total + high, high + 1
elif total > n:
total, low = total - low, low + 1
else:
count += 1
total, high = total + high, high + 1
total, low = total - low, low + 1
return count같은 코드를 자바스크립트로 구현해보겠습니다.
function solution(n) {
let count = 0;
let low = 1,
high = 2;
let total = 1;
while (low < high) {
if (total < n) {
total += high++;
} else if (total > n) {
total -= low++;
} else {
count++;
total += high++;
total -= low++;
}
}
return count;
}이 알고리즘은 단일 루프로 시작 포인터와 종료 포인터 둘 중에 하나를 증가시키기 때문에 시간 복잡도가 O(2n) = O(n)이 됩니다.
공간 복잡도는 n과 상관 관계없이 항상 일정한 메모리를 소모하기 때문에 O(1)이 되겠습니다.