[백준/C++] 전화번호 수수께끼 (No.14369, 14370)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음에 완전탐색을 해야하나? 생각이 들었다.

그런데 0~9 를 영어로 표현하면 0은 'Z' 처럼 한번만 나와서 빠르게 0의 개수를 파악할 수 있다는 생각에 각 수를 영어로 표현하기 시작했다.

 

처음에는 Z나 8의 G처럼 구분되는 수만 빼려고 했는데, 잘 생각해보니 0을 빼면 Z, E, R, O 각 글자가 하나씩 빠지면서 문자의 개수로 특정 수가 몇 개 인지 파악이 되겠다는 생각이 들었다.

 

그렇게 알파벳의 개수로 숫자가 몇 개 인지 파악할 수 있는 경우를 구해나갔고 알파벳의 개수를 잘 세면 매우 빠르게 문제를 풀 수 있음을 파악했다.

 

0~9를 알파벳으로 표현해 구분하면 아래와 같이 표현할 수 있다. 

 

ZERO ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE
-> Z EEEEEEEEE RRR OOOO NNNN TTT W HH FF U IIII VV SS X G

 

이를 이용해 숫자를 제거해 나가는 순서를 구했다.

-> 0, 2, 4, 5, 6, 7, 8, 1, 3, 9

 

위 순서대로 알파벳의 수를 세면 빠르게 전화번호를 구할 수 있다.

 

[아이디어 정리]

1. 숫자를 영어로 바꾼다.
2. 이후 특정 숫자에만 있는 알파벳을 찾아 그 알파벳의 수 만큼 숫자로 바꾼다.
3. 알파벳을 숫자를 바꿨으므로 바꾼 알파벳들의 개수를 빼준다.
4. 위 방법을 이용해 알파벳의 개수를 세는 것으로 모든 알파벳을 숫자로 바꿀 수 있다. (순서 :0, 2, 4, 5, 6, 7, 8, 1, 3, 9)
5. 전화번호는 오름차순이므로 0부터 순서대로 개수를 출력한다.

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <queue>
using namespace std;

int conv(char c)
{
    return c - 'A';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    for (int TC=1; TC<=N; TC++)
    {
        string str;
        cin >> str;
        //"ZERO ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE"
        // Z EEEEEEEEE RRR OOOO NNNN TTT W HH FF U IIII VV SS X G
        
        // O: Z, 2: W, U:4, F: 5, X:6, S,V :7, G:8, O:1, T:3, E:9
        // 위 순서대로 검증하면 됨
        vector<int> numCnt(10,0);
        vector<int> alphaCnt(26, 0);
        for (int i=0; i<str.size(); i++)
        {
            alphaCnt[str[i] - 'A'] += 1;
        }
        int tmpC;
        //0
        tmpC = alphaCnt[25];
        numCnt[0] += tmpC;
        alphaCnt[conv('Z')] -= tmpC, alphaCnt[conv('E')] -= tmpC, alphaCnt[conv('R')]-=tmpC, alphaCnt[conv('O')]-=tmpC;
        //2
        tmpC = alphaCnt[conv('W')];
        numCnt[2] += tmpC;
        alphaCnt[conv('T')] -= tmpC, alphaCnt[conv('W')] -= tmpC, alphaCnt[conv('O')] -= tmpC;
        //4
        tmpC = alphaCnt[conv('U')];
        numCnt[4] += tmpC;
        alphaCnt[conv('F')] -= tmpC, alphaCnt[conv('O')] -= tmpC, alphaCnt[conv('U')] -= tmpC, alphaCnt[conv('R')] -= tmpC;
        //5
        tmpC = alphaCnt[conv('F')];
        numCnt[5] += tmpC;
        alphaCnt[conv('F')] -= tmpC, alphaCnt[conv('I')] -= tmpC, alphaCnt[conv('V')] -= tmpC, alphaCnt[conv('E')] -= tmpC;
        //6
        tmpC = alphaCnt[conv('X')];
        numCnt[6] += tmpC;
        alphaCnt[conv('S')] -= tmpC, alphaCnt[conv('I')] -= tmpC, alphaCnt[conv('X')] -= tmpC;
        //7
        tmpC = alphaCnt[conv('S')];
        numCnt[7] += tmpC;
        alphaCnt[conv('S')] -= tmpC, alphaCnt[conv('E')] -= tmpC, alphaCnt[conv('V')] -= tmpC, alphaCnt[conv('E')] -= tmpC, alphaCnt[conv('N')] -= tmpC;
        //8
        tmpC = alphaCnt[conv('G')];
        numCnt[8] += tmpC;
        alphaCnt[conv('E')] -= tmpC, alphaCnt[conv('I')] -= tmpC, alphaCnt[conv('G')] -= tmpC, alphaCnt[conv('H')] -= tmpC, alphaCnt[conv('T')] -= tmpC;
        //1
        tmpC = alphaCnt[conv('O')];
        numCnt[1] += tmpC;
        alphaCnt[conv('O')] -= tmpC, alphaCnt[conv('N')] -= tmpC, alphaCnt[conv('E')] -= tmpC;
        //3
        tmpC = alphaCnt[conv('T')];
        numCnt[3] += tmpC;
        alphaCnt[conv('T')] -= tmpC, alphaCnt[conv('H')] -= tmpC, alphaCnt[conv('R')] -= tmpC, alphaCnt[conv('E')] -= tmpC, alphaCnt[conv('E')] -= tmpC;
        //9
        tmpC = alphaCnt[conv('E')];
        numCnt[9] += tmpC;
        alphaCnt[conv('N')] -= tmpC, alphaCnt[conv('I')] -= tmpC, alphaCnt[conv('N')] -= tmpC, alphaCnt[conv('E')] -= tmpC;
        
        cout << "Case #" << TC << ": ";
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < numCnt[i]; j++) {
                cout << i;
            }
        }
        cout << "\n";
    }

    return 0;
}

 

---

 

숫자를 알파벳으로 변경해 보면 쉽게 문제의 풀이방법을 파악할 수 있는 문제였다.

 

https://www.acmicpc.net/problem/14370