백준 1755번 [숫자놀이](C++) -yes6686- 티스토리

백준 문제 풀이: 1755번 [숫자놀이]

---

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

문제 설명:

주어진 숫자 범위 [N, M]에서 각 숫자를 영어 단어로 표현했을 때, 사전 순으로 정렬한 뒤 다시 숫자로 출력하는 문제입니다. 한 줄에 최대 10개의 숫자를 출력하며, 각 줄의 끝에는 줄바꿈이 포함됩니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

string alpha[10] = { "zero", "one", "two", "three", "four",
                     "five", "six", "seven", "eight", "nine" };

pair<string, int> str[101]; // 영어 단어와 숫자를 저장하는 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m; // 입력 범위 [N, M]
    int k = 0;

    // 각 숫자를 영어 단어로 변환
    for (int i = n; i <= m; i++) {
        string s = to_string(i);
        str[k].first += alpha[s[0] - '0']; // 첫 번째 자리
        str[k].second = i;                // 원래 숫자 저장

        if (s.size() == 2) { // 두 자리 숫자인 경우
            str[k].first += ' ';
            str[k].first += alpha[s[1] - '0']; // 두 번째 자리
        }
        k++;
    }

    // 사전 순 정렬
    sort(str, str + k);

    // 결과 출력
    for (int i = 1; i <= k; i++) {
        cout << str[i - 1].second << ' ';
        if (i % 10 == 0) cout << '\n'; // 10개 출력 후 줄바꿈
    }
}

---

코드 설명

위 코드는 숫자를 영어 단어로 변환하여 정렬한 후 다시 숫자로 출력합니다. 주요 로직은 다음과 같습니다:

1. 숫자 변환: 각 숫자를 문자열로 변환한 뒤, 자릿수마다 영어 단어로 변환하여 연결합니다.
2. 정렬: 숫자와 단어의 쌍을 사전 순으로 정렬합니다.
3. 출력: 정렬된 결과를 다시 숫자로 출력하며, 한 줄에 최대 10개의 숫자를 출력합니다.

시간 복잡도:

• 숫자 변환: O((M-N+1) × L), 여기서 L은 숫자의 평균 자릿수
• 정렬: O((M-N+1) log(M-N+1))

전체 시간 복잡도는 입력 범위와 숫자의 자릿수에 비례합니다.

---

결과

위 코드는 숫자를 정렬하고 출력하는 문제를 정확히 해결합니다. 최적화나 대체 접근 방안이 있다면 댓글로 의견을 남겨주세요!