백준 5671번 [호텔 방 번호](C++) -yes6686- 티스토리

백준 문제 풀이: 5671

---

문제 링크: https://www.acmicpc.net/problem/5671

문제 설명:

호텔 방 번호 중에서 각 자리 숫자가 중복되지 않는 번호의 개수를 구하는 문제입니다. 주어진 범위 n부터 m까지 각 방 번호를 조사하여, 중복되지 않는 번호의 개수를 출력합니다.

---

문제 해결 코드

// 호텔 방 번호 문제의 최적화된 코드
#include <iostream>
#include <string>
#include <cstring> // memset 사용을 위한 헤더
using namespace std;

int arr[10]; // 0~9까지 숫자의 빈도 저장

int main() {
    ios::sync_with_stdio(false); // 입출력 속도 향상
    cin.tie(NULL); // cin과 cout의 동기화를 끊음

    int n, m; // 방 번호의 시작(n)과 끝(m)
    while (cin >> n >> m) { // EOF 입력까지 처리
        int cnt = 0; // 중복되지 않은 방 번호 개수
        for (int i = n; i <= m; i++) {
            string s = to_string(i); // 숫자를 문자열로 변환
            bool isUnique = true; // 중복 여부 확인
            memset(arr, 0, sizeof(arr)); // 배열 초기화

            for (char c : s) {
                int digit = c - '0';
                arr[digit]++;
                if (arr[digit] > 1) { // 숫자가 중복된 경우
                    isUnique = false;
                    break;
                }
            }
            if (isUnique) cnt++; // 중복이 없으면 카운트 증가
        }
        cout << cnt << '\n'; // 결과 출력
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 각 번호를 문자열로 변환하여 각 자리 숫자의 빈도를 배열로 관리하고, 중복 여부를 확인합니다.
• 구현 세부사항:
• to_string(i): 현재 방 번호를 문자열로 변환하여 각 자리 숫자에 접근합니다.
• arr[digit] > 1: 특정 숫자가 두 번 이상 등장하면 해당 번호는 중복된 번호로 처리됩니다.
• memset(arr, 0, sizeof(arr)): 다음 번호를 검사하기 전에 숫자 빈도 배열을 초기화합니다.
• 시간 복잡도 분석:
• 방 번호 범위 [n, m]의 크기가 R이라 할 때, 각 번호의 자리 수를 L라 하면, 최악의 경우 복잡도는 O(R * L)입니다.
• 각 방 번호에 대해 자리 수 확인이 O(L)이고, 전체 번호를 순회하므로 O(R)입니다.

---

결과

최적화된 코드로 범위 내의 방 번호를 효율적으로 탐색합니다. 문자열 변환과 배열을 이용한 중복 확인 방식은 명확하고 직관적입니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!