[SIM] 16113번 시그널

16113번 시그널

 

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

 

문제

zxcvber는 외계인을 연구하는 과학자다. 그는 지난 10년간 우주에서 오는 시그널를 연구했지만, 아무런 성과가 없었다. 그러던 어느 날, 갑자기 우주에서 이상한 시그널이 오기 시작했다. zxcvber는 매우 기뻐하며 시그널을 받아서 분석해보았다. 시그널은 0과 1로 이루어져 있는데, 여기서는 편의상 0을 ".", 1을 "#"으로 표시한다. 시그널은 다음과 같았다.

###.....###.#..####.#.......#.#....####.....###.#....##.#.......#.#....####.....###.#....#

 

다른 여러 시그널들을 분석해본 결과, zxcvber는 시그널의 길이가 항상 5의 배수라는 것을 알게 되었다. 시그널을 다섯 개로 쪼개면 뭔가 규칙이 보이지 않을까 생각한 zxcvber는 시그널을 같은 길이의 5개의 시그널로 쪼갰다. 그러자 놀라운 일이 벌어졌다. 아래는 시그널을 쪼갠 뒤 "#"을 검은색, "."을 흰색으로 표시한 그림이다.

 

시그널은 디지털 숫자를 나타내고 있었다! 1-3열에 8, 9-11열에 3, 13열에 1, 그리고 16-18열에 7이 나타난 것이다. 이 숫자들이 특별한 의미를 갖고 있을 것이라 생각한 zxcvber는 다른 시그널들도 해독을 하기 시작했다. 하지만 시그널들의 길이가 너무 길어서, 일일히 손으로 확인하기에는 한계가 있었다. 다만, 짧은 시그널들을 분석하면서 zxcvber는 시그널의 규칙들을 파악할 수 있었다.

1. 시그널은 "."과 "#"으로 이루어져 있다.
2. 시그널을 해독한 결과에는 반드시 숫자가 1개 이상 있다.
3. 시그널에 등장하는 모든 "#"은 올바른 숫자 패턴에 포함되어 있다.
4. 숫자와 숫자 사이에는 1열 이상의 공백이 있다. 여기서 공백은, 열의 성분이 모두 "."인 열을 의미한다.
5. 0부터 9는 아래와 같이 나타난다. 역시 "#"을 검은색, "."을 흰색으로 표시했다.

 

주의할 점은, 1은 다른 숫자들과는 다르게 1열을 차지한다는 것이다. zxcvber를 도와 시그널을 해독해보자!지민이는 새로운 컴퓨터를 샀다. 하지만 새로운 컴퓨터에 사은품으로 온 LC-디스플레이 모니터가 잘 안나오는 것이다. 지민이의 친한 친구인 지환이는 지민이의 새로운 모니터를 위해 테스트 할 수 있는 프로그램을 만들기로 하였다.

 

입력

입력의 첫 줄에는 시그널의 길이 N(5 ≤ N ≤ 100,000, N은 5의 배수)이 주어진다.

다음 줄에 시그널이 주어진다. zxcvber가 찾아낸 규칙을 따르는 시그널만이 입력으로 주어진다.

 

출력

첫 번째 줄에 시그널을 해독하여 나오는 숫자들을 순서대로 출력한다.

 

예제 입력

40
###..#..#.#..#..###..#..#.#..#..###..#..

 

예제 출력

81

 

해결방법

주어진 문제를 분석하여 구현하는 시뮬레이션 문제이다

 

 

⭐️ 솔루션 ⭐️

1을 제외한 나머지 숫자에 대해 배열을 생성한 뒤, 숫자의 일치 여부를 파악한다

 

전체적인 흐름은 아래와 같다

1. 미리 0, 2~9 에 대해 3차원 배열을 통해 좌표값을 저장시켜준다
2. 시그널의 수를 5로 나눠 열의 개수를 파악하여 시그널을 2차원 배열에 넣어준다
3. 0행 0열 ~ 0행 col열 까지 접근하여 값이 '#' 인 곳에 대해 chkNum 함수를 실행한다
4. 0, 2~9 까지 일치 여부를 파악한 뒤, 일치하면 해당 숫자를, 일치하지 않으면 1을 리턴해준다

 

 

 

소스코드

문제 해결 시간 : 1h

메모리 : 2612 KB

시간 : 4 ms

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

int number[9][5][3] = {
    // 2
    {{1,1,1},{0,0,1},{1,1,1},{1,0,0},{1,1,1}},
    // 3
    {{1,1,1},{0,0,1},{1,1,1},{0,0,1},{1,1,1}},
    // 4
    {{1,0,1},{1,0,1},{1,1,1},{0,0,1},{0,0,1}},
    // 5
    {{1,1,1},{1,0,0},{1,1,1},{0,0,1},{1,1,1}},
    // 6
    {{1,1,1},{1,0,0},{1,1,1},{1,0,1},{1,1,1}},
    // 7
    {{1,1,1},{0,0,1},{0,0,1},{0,0,1},{0,0,1}},
    // 8
    {{1,1,1},{1,0,1},{1,1,1},{1,0,1},{1,1,1}},
    // 9
    {{1,1,1},{1,0,1},{1,1,1},{0,0,1},{1,1,1}},
    // 0
    {{1,1,1},{1,0,1},{1,0,1},{1,0,1},{1,1,1}}
};

int n;
int map[5][20001];
char ch;
string ans;

// 행과 열의 좌표를 받아 0,2~9 까지 확인을 하여 일치하면 해당 숫자를 반환
int chkNum(int row,int col){
    // 0, 2~9 확인
    for(int t=0; t<9; t++){
        bool flag = true;
        
        for(int i=0; i<5; i++){
            for(int j=0; j<3; j++){
                if(map[row+i][col+j] != number[t][i][j]){
                    flag = false;
                    break;
                }
            }
            if(!flag) break;
        }
        
        // 모든 좌표가 일치한다면 인덱스+2 리턴
        if(flag)
            return t+2;
    }
    
    // 위의 경우가 모두 아니라면 1 리턴
    return 1;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    int col = n / 5;
    
    for(int i=0; i<5; i++){
        for(int j=0; j<col; j++){
            cin >> ch;
            if(ch == '#')
                map[i][j] = 1;
            else
                map[i][j] = 0;
        }
    }
    
    ans = "";
    
    // 0행 0~col열을 반복문으로 돌며 숫자를 파악함
    int j = 0;
    while(j < col){
        if(map[0][j] == 1){
            int num = chkNum(0,j);
            
            if(num == 10){
                ans += "0";
                j += 3;
            }else if(num == 1){
                ans += to_string(num);
                j += 1;
            }else{
                ans += to_string(num);
                j += 3;
            }
        }else{
            j++;
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}