C++로 숫자 직선 위에서 방문한 고유 지점 개수 구하기

문제 소개

0과 1로만 구성된 이진 문자열이 하나 주어집니다. 또한 어떤 사람이 current_pos 변수에 저장된 위치, 즉 숫자 직선 위의 한 점에서 출발한다고 가정합니다. 문자열을 앞에서부터 한 글자씩 읽어 나가면서, 문자가 '0'이면 한 칸 왼쪽(current_pos − 1)으로, '1'이면 한 칸 오른쪽(current_pos + 1)으로 이동합니다. 목표는 문자열 전체를 다 처리한 뒤, 그동안 방문했던 서로 다른 지점의 개수를 구하는 것입니다.

이 문제는 각 지점의 방문 횟수를 기록하는 방식으로 해결할 수 있습니다. 어떤 지점의 방문 횟수가 0이 아니라면 최소 한 번은 방문했다는 뜻이므로, 그런 지점의 개수를 모두 세면 곧 고유 지점의 총 개수가 됩니다.

입력 · 출력 예시

예시 1

입력:

Path[] = "001100", current_pos = 3

출력:

숫자 직선에서 방문한 고유 지점의 개수: 3

설명 — path[0]부터 시작하며 초기 위치는 3입니다.

Path[0]: 0 → 왼쪽 이동 ... current_pos = 2
Path[1]: 0 → 왼쪽 이동 ... current_pos = 1
Path[2]: 1 → 오른쪽 이동 ... current_pos = 2
Path[3]: 1 → 오른쪽 이동 ... current_pos = 3
Path[4]: 0 → 왼쪽 이동 ... current_pos = 2
Path[5]: 0 → 왼쪽 이동 ... current_pos = 1

방문한 서로 다른 위치는 총 3개로, 1, 2, 3입니다.

예시 2

입력:

Path[] = "010101", current_pos = 5

출력:

숫자 직선에서 방문한 고유 지점의 개수: 2

설명 — path[0]부터 시작하며 초기 위치는 5입니다.

Path[0]: 0 → 왼쪽 이동 ... current_pos = 4
Path[1]: 1 → 오른쪽 이동 ... current_pos = 5
Path[2]: 0 → 왼쪽 이동 ... current_pos = 4
Path[3]: 1 → 오른쪽 이동 ... current_pos = 5
Path[4]: 0 → 왼쪽 이동 ... current_pos = 4
Path[5]: 1 → 오른쪽 이동 ... current_pos = 5

방문한 서로 다른 위치는 총 2개로, 4와 5입니다.

알고리즘 접근 방법

0과 1로 이루어진 문자열을 path에 저장합니다.
current_pos에는 출발 위치가 저장됩니다.
getDistinctPoints(int current_pos, string path) 함수는 현재 위치와 경로를 입력받아 방문한 고유 지점의 개수를 반환합니다.
변수 len에는 경로 문자열의 길이가 저장됩니다.
배열 frequency[21]은 각 지점이 방문된 횟수를 저장합니다. 배열의 인덱스가 곧 지점 번호를 의미하며, 지점 범위는 0~20입니다.
경로 문자열을 처음부터 끝까지 순회합니다.
현재 문자가 '0'이면 왼쪽으로 한 칸 이동(current_pos − 1)하고, 새 위치의 방문 횟수를 frequency[current_pos]++로 증가시킵니다.
현재 문자가 '1'이면 오른쪽으로 한 칸 이동(current_pos + 1)하고, 마찬가지로 frequency[current_pos]++로 방문 횟수를 증가시킵니다.
순회가 끝나면 frequency 배열을 훑으면서 값이 0이 아닌 원소마다 count를 1씩 증가시킵니다.
count에는 방문한 고유 지점의 개수가 담기며, 이 값을 최종 결과로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

// 0~20 범위에서 방문한 고유 지점의 개수를 계산
int getDistinctPoints(int current_pos, string path){
    int len = path.length();   // 경로 길이
    int count = 0;
    int frequency[21] = {0};   // 각 지점의 방문 횟수 저장

    // 경로의 모든 문자를 순회
    for (int i = 0; i < len; i++) {
        if (path[i] == '0') {          // 왼쪽 방향
            current_pos--;
            frequency[current_pos]++;  // 방문 횟수 증가
        }
        else {                         // 오른쪽 방향
            current_pos++;
            frequency[current_pos]++;  // 방문 횟수 증가
        }
    }

    for (int i = 0; i < 21; i++)
        if (frequency[i] != 0)         // 방문한 적이 있다면 0이 아님
            count++;

    return count;
}

int main(){
    int current_pos = 3;
    string path = "011101100";
    cout << "숫자 직선에서 방문한 고유 지점의 개수: " << getDistinctPoints(current_pos, path);
    return 0;
}

실행 결과

숫자 직선에서 방문한 고유 지점의 개수: 5

복잡도 및 참고 사항

이 알고리즘은 경로 문자열을 한 번만 순회하므로 시간 복잡도는 O(N)이며, 크기가 고정된(21) 배열 하나만 사용하므로 공간 복잡도는 O(1)입니다. 다만 지점 범위가 0~20으로 제한되어 있다는 전제가 필요합니다. 만약 이동 범위가 넓어진다면 frequency 배열 대신 map<int,int> 같은 동적 자료구조를 사용하면 동일한 로직으로 확장할 수 있습니다.