백준 1436번 영화감독 숌, C++

🎬 [백준 1436] 영화감독 숌 - 문자열 없이 종말의 수 구하기 (C 스타일 구현)

🔍 문제 설명

숫자 중에서 "666"이라는 연속된 숫자가 포함된 수들을 종말의 수라고 한다. 이 종말의 수들 중에서 N번째로 작은 수를 출력하는 것이 목표이다.

• 1번째 종말의 수 → 666
• 2번째 종말의 수 → 1666
• 3번째 종말의 수 → 2666
• 10번째 종말의 수 → 6669
• 10000번째 종말의 수는?

---

🧠 사고 흐름: 단계별 접근

🧩 1단계: 숫자를 조합해보자 (i * 1000 + 666)

처음에는 종말의 수를 수식으로 만들 수 있다고 생각함. → i * 1000 + 666이면 0666, 1666, 2666, …이 가능하니까?

❌ 문제점

• 666이 포함된 숫자가 조합으로는 중복되기 쉽다.
• 예: 0666이 이미 나왔는데, 0 * 1000 + 666 = 666이 또 나옴
• 중복 제거가 까다롭고, 전체 순서를 유지하기 힘들다

---

🧩 2단계: 조합, 순열 시도

• 666이 포함되는 자릿수를 바꿔서 조합 생성
• 예: 6__66, 66__, __666, __6_66 등

❌ 문제점

• 가능한 숫자가 너무 많고
• n번째 수를 찾으려면 정렬까지 해야 하므로 복잡하다
• 결국 비효율적 + 순서 보장 어려움

---

✅ 3단계: 숫자를 하나씩 증가시키며 검사

• 666부터 시작해서 1씩 증가하며 숫자에 "666"이 들어가는지 직접 검사
• 조건에 맞는 수만 배열에 저장하고, n번째를 출력

✅ 장점

• 매우 직관적
• 순서가 자동으로 보장됨
• 구현이 단순하면서도 정확도 100%

---

🔧 전체 코드 (문자열 없이 직접 구현)

#include <iostream>
#include <cstring>
using namespace std;

bool check_666(char* arr) {
    int n = strlen(arr);
    for (int i = 0; i <= n - 3; i++) {
        if (arr[i] == '6' && arr[i + 1] == '6' && arr[i + 2] == '6') {
            return true;
        }
    }
    return false;
}

int digits(int n) {
    int count = 0;
    while (n > 0) {
        n = n / 10;
        count++;
    }
    return count;
}

char* to_str(int n, int digit) {
    char* arr = new char[digit + 1];
    arr[digit] = '\0';
    for (int i = digit - 1; i >= 0; i--) {
        arr[i] = n % 10 + '0';
        n = n / 10;
    }
    return arr;
}

int arr[10001] = { 0, };

int main(void) {
    int n, k = 0;
    cin >> n;
    for (int i = 666; k < 10000; i++) {
        char* str = to_str(i, digits(i));
        if (check_666(str)) {
            arr[k] = i;
            k++;
        }
        delete[] str;
    }
    cout << arr[n - 1] << endl;
    return 0;
}

---

✅ 개선 가능한 부분 요약

항목	현재 방식	개선 방향
문자열 변환	char* 수동 변환	숫자 자체에서 666 연속 검사
종료 조건	k < 10000	✔ 적절함
메모리 해제	delete[]	✔ 적절함
정렬, 중복	없음	✔ 중복 없음

---

✅ 개선 아이디어 (논리 설명)

🔧 문제점 (기존 코드의 병목)

• 매 숫자마다 to_str()로 char* 생성 → 동적 할당/해제 반복 → 시간, 메모리 낭비
• strlen() + 문자열 인덱싱 → 오버헤드 발생

💡 개선 전략

• 숫자를 직접 다루며 666 연속 여부를 검사
• n % 10으로 끝자리부터 검사하며 6이 몇 번 연속으로 나오는지 확인
• 3번 연속 나오면 즉시 종말의 수로 판정

---

🧠 개선된 전체 코드

#include <iostream>
using namespace std;

bool has_666(int n) {
    int consecutive = 0;
    while (n > 0) {
        if (n % 10 == 6) {
            consecutive++;
            if (consecutive == 3) return true;
        } else {
            consecutive = 0;
        }
        n /= 10;
    }
    return false;
}

int main() {
    int n;
    cin >> n;

    int count = 0;
    int number = 666;

    while (true) {
        if (has_666(number)) {
            count++;
            if (count == n) {
                cout << number << endl;
                return 0;
            }
        }
        number++;
    }
}

---

✅ 단계별 코드 해설

✅ 1단계: "666" 연속 판별 함수

bool has_666(int n) {
    int consecutive = 0;
    while (n > 0) {
        if (n % 10 == 6) {
            consecutive++;
            if (consecutive == 3) return true;
        } else {
            consecutive = 0;
        }
        n /= 10;
    }
    return false;
}

• n % 10으로 끝자리를 확인하며 6이 연속 몇 번 나오는지 추적
• 연속 3번이면 true 리턴
• 문자열 없이 숫자만으로 구현 → 훨씬 빠름

✅ 2단계: 숫자를 666부터 하나씩 검사

int count = 0;
int number = 666;

while (true) {
    if (has_666(number)) {
        count++;
        if (count == n) {
            cout << number << endl;
            return 0;
        }
    }
    number++;
}

• 666부터 하나씩 검사
• 종말의 수를 찾을 때마다 count++
• n번째 종말의 수를 찾으면 출력하고 종료

---

✅ 성능 비교

기준	기존 코드 (char*)	개선 코드 (int)
문자열 변환	필요함	없음
동적 메모리	매 루프마다 new/delete	없음
연속성 판별	char[] 인덱스	% 연산 사용
시간 복잡도	느림 (문자열 처리)	빠름
공간 효율성	char* 메모리 필요	숫자만 사용

---

✅ 정리

항목	내용
핵심 개선	char* 없이 숫자로 연속된 6 확인
속도	훨씬 빠르고 안정적
구현 난이도	오히려 더 간단함
추천 대상	입력 크기 커질수록 유리, 백준 1436번 완전 정답 가능 코드