알고리즘

[백준] 시그널 - Java

BGK97 2025. 2. 5. 15:40

문제 출처

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

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

81

노트

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

풀이 방법

  • 간단하게 그냥 숫자모형 배열을 만들고 이를 대응하면서 풀었다.
  • 각 줄의 길이는 전체 길이에서 5로 나눈 길이이다.(숫자가 5x3 크기임) 
    • 먼저 각 숫자에 해당하는 배열을 생성해준다 (10, 5, 3 크기)
	static int[][][] numberSet = { { // 0
			{ 1, 1, 1 }, { 1, 0, 1 }, { 1, 0, 1 }, { 1, 0, 1 }, { 1, 1, 1 } },
			{ // 1
					{ 0, 1, 0 }, { 0, 1, 0 }, { 0, 1, 0 }, { 0, 1, 0 }, { 0, 1, 0 } },
			{ // 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 } } };
  • 열 정렬해서 보면 숫자로 보인다.
  • 이후 이 받은 시그널을 바탕으로, #는1로, .는 0으로 저장한다.
  • 이후 비교해서 값을 저장하고 출력하면 끝

예외사항

  • 다른 숫자는 예외가 안되는데, 1이 문제다.

  • 예제 사진과 같이, 1의 경우 5x3을 특정할 수도 없기에 1에대한 예외처리를 해주어야한다.
// 숫자 1인지 확인 (5행이 모두 1인지 확인)
		    if ((i + 1 < N / 5 && signal[0][i] == 1 && signal[1][i] == 1 && signal[2][i] == 1 && signal[3][i] == 1 && signal[4][i] == 1
		        && (i + 1 == N / 5 || signal[0][i + 1] == 0)) || (i == (N / 5) - 1 && signal[0][i] == 1)) {
		        sb.append(1);
		        continue;
		    }
  • 따라서 위 코드처럼 각 행이 1인지 확인해준다.
  • 마지막 열에 1이 등장하는 경우도 있기 때문에 이 점도 잘 생각해서 풀이해야한다.

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int[][][] numberSet = { { // 0
			{ 1, 1, 1 }, { 1, 0, 1 }, { 1, 0, 1 }, { 1, 0, 1 }, { 1, 1, 1 } },
			{ // 1
					{ 0, 1, 0 }, { 0, 1, 0 }, { 0, 1, 0 }, { 0, 1, 0 }, { 0, 1, 0 } },
			{ // 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 } } };

	static int[][] signal;
	static int N;
	static String code;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(br.readLine());
		code = br.readLine();
		signal = new int[5][N / 5];
		int idx = 0;

		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < N / 5; j++) {
				if (code.charAt(idx++) == '#') {
					signal[i][j] = 1;
				} else {
					signal[i][j] = 0;
				}
			}
		}

		// 배열 내에서 검사하기
		for (int i = 0; i < N / 5; i++) {
		    // 빈칸이면 스킵
		    if (signal[0][i] == 0) continue;

		    // 숫자 1인지 확인 (5행이 모두 1인지 확인)
		    if ((i + 1 < N / 5 && signal[0][i] == 1 && signal[1][i] == 1 && signal[2][i] == 1 && signal[3][i] == 1 && signal[4][i] == 1
		        && (i + 1 == N / 5 || signal[0][i + 1] == 0)) || (i == (N / 5) - 1 && signal[0][i] == 1)) {
		        sb.append(1);
		        continue;
		    }

		    // 숫자 비교
		    in: for (int num = 0; num < 10; num++) {
		        if (i + 2 >= N / 5) continue; // 숫자 판별 가능 여부 체크
		        for (int j = 0; j < 3; j++) { // 3열 검사
		            for (int k = 0; k < 5; k++) { // 5행 검사
		                if (numberSet[num][k][j] != signal[k][j + i]) {
		                    continue in; // 불일치하면 다음 숫자로 넘어감
		                }
		            }
		        }
		        sb.append(num);
		        i += 2; // 숫자 폭이 3이므로, 2만큼 이동
		        break;
		    }
		}

		
		System.out.println(sb.toString());
	}
}

결과

회고

  • 예외처리가 가장 힘다