문제 소개
이번 문제는 길이가 n인 모든 스트로보그램 숫자(strobogrammatic number)를 찾는 것입니다. 스트로보그램 숫자란 숫자를 180도 회전했을 때 원래 모양과 똑같이 보이는 수를 의미합니다.
예를 들어 입력이 n = 2라면 출력은 ["11", "69", "88", "96"]이 됩니다. '11'과 '88'은 회전해도 그대로이며, '69'는 회전하면 '96'처럼 보이지만 좌우가 뒤집힌 형태로 동일하게 인식됩니다.
회전 가능한 숫자 조합
모든 숫자가 회전 후에도 유효한 것은 아닙니다. 180도 회전 시 성립하는 조합은 다음과 같습니다.
- 0 → 0
- 1 → 1
- 8 → 8
- 6 ↔ 9 (회전 시 서로 뒤바뀜)
반면 2, 3, 4, 5, 7은 회전했을 때 올바른 숫자가 되지 않으므로 사용할 수 없습니다.
해결 접근 방법
이 문제는 중앙에서 바깥쪽으로 자릿수를 확장해 나가는 방식으로 해결할 수 있습니다. 단계별 알고리즘은 다음과 같습니다.
- 결과를 담을 배열 ret을 정의합니다.
- n이 홀수라면 중앙에 위치할 수 있는 숫자인 "0", "1", "8"을 ret에 차례로 추가합니다.
- n이 짝수라면 빈 문자열("")을 ret에 추가합니다.
- n > 1인 동안 n을 2씩 감소시키며 다음 작업을 반복합니다.
- 새로운 임시 배열 temp를 정의합니다.
- ret의 각 문자열 s에 대해 다음을 temp에 추가합니다.
- n > 3인 경우에만 "0" + s + "0"을 추가합니다. (가장 바깥쪽 자리에 0이 오는 것을 방지)
- "1" + s + "1", "8" + s + "8", "6" + s + "9", "9" + s + "6"을 추가합니다.
- 반복이 끝날 때마다 ret을 temp로 갱신합니다.
- 모든 과정이 완료되면 ret을 반환합니다.
여기서 조건 n > 3이 핵심입니다. 마지막 반복 단계는 곧 가장 바깥쪽 두 자리를 채우는 단계이므로, 이때 0을 추가하면 선행 0(leading zero)이 생겨 잘못된 결과가 됩니다. 따라서 안쪽 자리에만 0을 허용하는 것입니다.
C++ 구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<string> findStrobogrammatic(int n) {
vector<string> ret;
if (n & 1) {
ret.push_back("0");
ret.push_back("1");
ret.push_back("8");
}
else {
ret.push_back("");
}
for (; n > 1; n -= 2) {
vector<string> temp;
for (int i = 0; i < ret.size(); i++) {
string s = ret[i];
if (n > 3) {
temp.push_back("0" + s + "0");
}
temp.push_back("1" + s + "1");
temp.push_back("8" + s + "8");
temp.push_back("6" + s + "9");
temp.push_back("9" + s + "6");
}
ret = temp;
}
return ret;
}
};
main(){
Solution ob;
print_vector(ob.findStrobogrammatic(3));
}입력
3
출력
[101, 808, 609, 906, 111, 818, 619, 916, 181, 888, 689, 986]
실행 결과 분석
n = 3인 경우를 살펴보면, 가운데 자리에는 0, 1, 8이 올 수 있고 양 끝 자리 쌍은 (1,1), (8,8), (6,9), (9,6)의 네 가지 조합이 가능합니다. 따라서 총 4 × 3 = 12개의 스트로보그램 숫자가 생성되며, 출력 결과와 정확히 일치하는 것을 확인할 수 있습니다.
이 알고리즘은 각 단계마다 기존 결과의 양쪽에 새로운 자릿수 쌍을 덧붙이는 방식으로 동작하므로, 연산 횟수가 결과 숫자의 개수에 비례하여 매우 효율적입니다. 특히 재귀 없이 반복문만으로 구현되어 코드가 간결하고 이해하기 쉽다는 장점이 있습니다.