728x90

시그널

1 초 (추가 시간 없음) 512 MB 2257 709 601 32.002%

문제

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를 도와 시그널을 해독해보자!

입력

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

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

81

노트

예제 시그널을 8개씩 끊어서 읽으면 다음과 같다.

 

전형적인 구현, 문자열 문제이다.

 

숫자 한개를 살펴보면 1을 제외한 숫자는 가로 3칸에 세로 5칸인 모습이며 각 숫자들을 구별하기 위해 한칸씩 떨어진 형태임을 확인 할 수 있다.

 

주의해야 할 점은숫자 1의 경우 가로 1칸에 세로 5칸인 모습이므로, 숫자 '1'에만 예외를 두어 시그널을 숫자로 변환해야한다.

 

이 아이디어를 바탕으로 내가 생각한 풀이법은 아래와 같다.

 

1. 주어진 문자열은 5의 배수로 주어지므로 5로 나누어 세로 5칸 가로 N//5 칸의 2차원 배열을 만든다.

2. 같은 숫자를 탐색하지 않게 하기 위해 방문정보를 기록하기 위한 visited배열을 만든다.

3. 만들어진 2차원 배열의 0번째 행을 돌면서 숫자를 나타내는 '#'라면 숫자 '1'에 해당하는지 검사한다.

    3.1. 만약 1이라면 1을 출력하고 방문처리 후 계속 시그널 변환을 진행한다.

    3.2. 만약 1이 아니라면 해당 문자를 포함하고 있는 가로 3칸 세로 5칸의 부분배열을 만든 후 어떤 숫자에 해당하는지 검사하여 출력하고 시그널 변환을 계속한다.

 

이 풀이법을 사용하기 위해선 1을 제외한 모든 숫자들에 대해서 미리 2차원 배열을 만들어 두는 것과 숫자 '1'을 검사하는 로직을 잘 작성하는것이 중요하다.

 

# https://acmicpc.net/problem/16113
'''
<아이디어>
0. 각 숫자들의 형태를 담은 2차원 배열을 미리 만들어 둔다.
1. 주어진 문자열을 5줄의 문자열로 만든다.(5의 배수)
2. 각 자리의 숫자가 1인지 아닌지 검사한다.
    2.1. '#'이 일자로 쭉 늘어지면서, 양옆이 모두 '.'이라면 1이다.
3. 1이 아니라면 미리 만들어둔 문자열과 비교하여 어떤 수인지 파악하여 출력한다.
'''
zero = [["#","#","#"],
        ["#",".","#"],
        ["#",".","#"],
        ["#",".","#"],
        ["#","#","#"]]

one = []

two = [["#","#","#"],
        [".",".","#"],
        ["#","#","#"],
        ["#",".","."],
        ["#","#","#"]]

three = [["#","#","#"],
        [".",".","#"],
        ["#","#","#"],
        [".",".","#"],
        ["#","#","#"]]

four = [["#",".","#"],
        ["#",".","#"],
        ["#","#","#"],
        [".",".","#"],
        [".",".","#"]]

five = [["#","#","#"],
        ["#",".","."],
        ["#","#","#"],
        [".",".","#"],
        ["#","#","#"]]

six = [["#","#","#"],
        ["#",".","."],
        ["#","#","#"],
        ["#",".","#"],
        ["#","#","#"]]

seven = [["#","#","#"],
        [".",".","#"],
        [".",".","#"],
        [".",".","#"],
        [".",".","#"]]

eigth = [["#","#","#"],
        ["#",".","#"],
        ["#","#","#"],
        ["#",".","#"],
        ["#","#","#"]]

nine = [["#","#","#"],
        ["#",".","#"],
        ["#","#","#"],
        [".",".","#"],
        ["#","#","#"]]

# 0. 미리 숫자들 만들어 두기, 1은 따로 검사할것이므로 만들 필요 없다.
numbers = [zero,one,two,three,four,five,six,seven,eigth,nine]
n = int(input())
data = list(input())
# 해석한 문자(5줄로 분리)
length = n//5 # 한 줄에 포함될 문자열의 개수
signal = [data[i:i+length]for i in range(0,n,length)]
visited = [False for _ in range(length)] # 맨 윗줄만 검사할것이므로 한줄만 있어도됨

def isOne(i):
    # 세로로 모두 "#"이고, 양옆의 좌표가 .또는 갈수없는 곳이라면 1임
    for j in range(5):
        if signal[j][i] == "#":
            # 좌,우 확인
            if i-1>=0:
                if signal[j][i-1] != ".":
                    return False
            if i+1<length:
                if signal[j][i+1] != ".":
                    return False
    print(1,end='')
    # 방문처리
    visited[i] = True
    return True

def decryption(start):
    # 주어진 시작 좌표의 3*5크기의 배열과 미리 만들어둔 배열을 비교
    number_area = [signal[i][start:start+3] for i in range(5)]
    for i,num in enumerate(numbers):
        if num == number_area:
            print(i,end='')
            
    # 가로 3칸 방문처리
    visited[start:start+3] = [True,True,True]
    return

for i in range(length):
    # 아직 탐색하지 않은 숫자에 대해서만
    if not visited[i] and signal[0][i] == '#':
        # 1인지 검사
        if isOne(i):
            continue
        decryption(i) # 복호화하여 출력

 

 

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

 

16113번: 시그널

zxcvber는 외계인을 연구하는 과학자다. 그는 지난 10년간 우주에서 오는 시그널를 연구했지만, 아무런 성과가 없었다. 그러던 어느 날, 갑자기 우주에서 이상한 시그널이 오기 시작했다. zxcvber는

www.acmicpc.net

 

+ Recent posts