크기가 n인 배열 A가 있다고 가정해 보겠습니다. 아말(Amal)은 다층 건물 안에서 계단을 오르며, 계단 하나를 오를 때마다 항상 1부터 다시 숫자를 세기 시작합니다. 예를 들어 3단짜리 계단과 4단짜리 계단 두 개를 연속해서 오른다면, 그는 1, 2, 3, 1, 2, 3, 4처럼 숫자를 말하게 됩니다.
배열 A에는 아말이 말한 이 숫자들이 순서대로 기록되어 있습니다. 우리가 구해야 할 것은 다음 두 가지입니다.
- 아말이 모두 몇 개의 계단을 올랐는지
- 각 계단이 몇 단으로 이루어져 있는지
예를 들어 입력이 A = [1, 2, 3, 1, 2, 3, 4, 5]라면, 1이 두 번 등장하므로 계단은 총 2개이고, 마지막 요소를 포함한 각 구간의 끝 값에 따라 출력은 2, [3, 5]가 됩니다.
문제 해결 접근 방식
핵심 아이디어는 매우 간단합니다. 새로운 계단을 오르기 시작할 때 반드시 1을 말한다는 점에 착안합니다.
- 배열에서 1이 등장하는 횟수 = 계단의 개수
- 1 바로 앞에 있는 값 = 직전 계단의 단 수
- 배열의 마지막 요소 = 마지막 계단의 단 수
이 규칙을 의사 코드로 표현하면 다음과 같습니다.
p = 0
n := A의 크기
i := 0으로 초기화, i < n인 동안 반복(i를 1씩 증가):
만약 A[i]가 1과 같다면:
p를 1 증가
p 출력
i := 1로 초기화, i < n인 동안 반복(i를 1씩 증가):
만약 A[i]가 1과 같다면:
A[i - 1] 출력
A[n - 1] 출력C++ 구현 예제
위 로직을 실제 C++ 코드로 구현하면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A) {
int i, p = 0;
int n = A.size();
// 1의 등장 횟수를 세어 계단 개수 구하기
for (i = 0; i < n; i++) {
if (A[i] == 1)
p++;
}
cout << p << endl;
// 1 앞의 값을 출력하여 각 계단의 단 수 구하기
for (i = 1; i < n; i++) {
if (A[i] == 1)
cout << A[i - 1] << ", ";
}
// 마지막 계단의 단 수 출력
cout << A[n - 1];
}
int main() {
vector<int> A = { 1, 2, 3, 1, 2, 3, 4, 5 };
solve(A);
}입력
{ 1, 2, 3, 1, 2, 3, 4, 5 }출력
2 3, 5
코드 설명
첫 번째 반복문에서는 배열 전체를 탐색하며 값이 1인 지점의 개수를 셉니다. 1은 새로운 계단을 시작하는 신호이므로, 그 개수가 곧 계단의 총 개수(p)가 됩니다.
두 번째 반복문에서는 값이 1인 지점을 찾으면 그 바로 앞의 값(A[i-1])을 출력합니다. 이 값은 해당 계단 구간의 마지막 숫자, 즉 그 계단의 단 수입니다. 반복문이 끝난 후에는 배열의 마지막 요소를 출력하여 마지막 계단의 단 수까지 완성합니다.
이 알고리즘은 배열을 두 번 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 문제를 해결할 수 있는 효율적인 방법입니다.