정수로 이루어진 배열이 하나 주어졌다고 가정해 보겠습니다. 먼저 이 배열에서 만들 수 있는 모든 연속 부분 배열(contiguous subarray)을 구한 뒤, 각 부분 배열을 그 안의 최댓값으로 바꿉니다. 그리고 숫자 k가 추가로 주어졌을 때, 바뀐 값이 k보다 큰 부분 배열이 몇 개인지 세는 것이 이 문제의 목표입니다.
문제 예시
입력이 다음과 같다고 해보겠습니다.
input_array = [5, 6, 7, 8], k = 7
이때 출력은 4가 됩니다.
배열 [5, 6, 7, 8]에서 만들 수 있는 연속 부분 배열은 다음과 같습니다.
{5}, {6}, {7}, {8}, {5, 6}, {6, 7}, {7, 8}, {5, 6, 7}, {6, 7, 8}, {5, 6, 7, 8}
각 부분 배열을 해당 배열의 최댓값으로 바꾸면 아래와 같아집니다.
{5}, {6}, {7}, {8}, {6}, {7}, {8}, {7}, {8}, {8}
이중 값이 7보다 큰 집합은 총 4개입니다.
접근 방법
모든 부분 배열을 일일이 만들어 확인하면 비효율적입니다. 대신 반대로 생각하면 훨씬 간단해집니다. 전체 부분 배열의 개수에서 최댓값이 k 이하인 부분 배열의 개수를 빼면 곧바로 답을 얻을 수 있습니다.
- 길이가 n인 배열의 전체 부분 배열 개수는 n × (n + 1) / 2입니다.
- k 이하의 원소가 연속으로 이어지는 구간의 길이가 L이라면, 그 구간 내부에 완전히 포함되는 부분 배열은 L × (L + 1) / 2개이며, 이들은 모두 최댓값이 k 이하입니다.
- 따라서 배열을 한 번만 순회하면서 k 이하 원소의 연속 길이를 누적하면 O(n) 시간 복잡도로 답을 구할 수 있습니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- count := 0, consecutive := 0으로 초기화합니다.
- input_array의 각 원소 x에 대해 다음을 반복합니다.
- x > k이면 consecutive := 0으로 초기화합니다.
- 그렇지 않으면 consecutive를 1 증가시키고, 그 값을 count에 더합니다.
- 마지막으로 (배열 길이 × (배열 길이 + 1) / 2) − count를 반환합니다.
구현 예제
다음 파이썬 구현을 통해 더 잘 이해해 보겠습니다.
def solve(input_array, k):
count = 0
consecutive = 0
for x in input_array:
if x > k:
consecutive = 0
else:
consecutive += 1
count += consecutive
return len(input_array) * (len(input_array) + 1) // 2 - count
print(solve([5, 6, 7, 8], 7))입력
[5, 6, 7, 8], 7
출력
4