C++로 4와 7로만 이루어진 수열에서 주어진 수의 위치 찾기

이 문제에서는 하나의 수 N이 주어지며, 4와 7로만 구성된 수열에서 해당 수가 몇 번째 위치에 있는지 찾아야 합니다. 4와 7만으로 이루어진 수열은 다음과 같습니다.

4, 7, 44, 47, 74, 77, 444, ...

예시를 통해 문제를 이해해 보겠습니다.

입력

N = 5

출력

74

설명

수열의 처음 5개 항은 4, 7, 44, 47, 74입니다.

풀이 접근법

이 문제의 가장 간단한 풀이 방법은 수열 속에 숨어 있는 규칙성(패턴)을 찾는 것입니다.

수열을 자세히 관찰하면 다음과 같은 특징을 발견할 수 있습니다.

• 짝수 번째 위치에 있는 수는 항상 끝자리가 7입니다.
• 홀수 번째 위치에 있는 수는 항상 끝자리가 4입니다.

따라서 주어진 수를 한 자리씩 확인하면서, 각 자릿수에 따라 위치 값을 갱신하는 방식으로 수열에서의 위치를 계산할 수 있습니다.

현재 자릿수가 4라면 위치는 아래와 같이 갱신됩니다.

position = (position * 2) + 1

현재 자릿수가 7이라면 위치는 아래와 같이 갱신됩니다.

position = (position * 2) + 2

즉, 4를 이진법의 1로, 7을 2로 치환하여 왼쪽 자릿수부터 차례대로 계산하는 것과 같은 원리입니다. 이 방식은 수의 길이가 길어져도 빠르게 위치를 구할 수 있으며, 시간 복잡도는 자릿수에 비례하는 O(k)입니다.

이 풀이의 동작을 보여주는 프로그램입니다.

예제 코드

#include <iostream>
using namespace std;

int findNumPosition(string num){
    int position = 0;
    for (char digit : num) {
        position *= 2;
        if (digit == '4')
            position += 1;
        else
            position += 2;
    }
    return position;
}

int main() {
    string num = "74774";
    cout << "수열에서 이 수의 위치는 " << findNumPosition(num);
    return 0;
}

출력

수열에서 이 수의 위치는 53

위 예제에서 입력 수 "74774"는 수열에서 53번째 위치에 있는 수임을 확인할 수 있습니다.