[SWEA] #1240 - 단순 2진 암호코드

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15FZuqAL4CFAYD 

SW Expert Academy

 

💡 문제

---

[설명]

어떤 국가에서는 자국 내 방송국에서 스파이가 활동하는 사실을 알아냈다. 스파이는 영상물에 암호 코드를 삽입하여 송출하고 있었다. 암호 코드는 국가 내 중요 시설을 의미하는 숫자임을 알아냈다. 암호 코드의 규칙은 아래와 같다

1. 총 8개의 숫자로 이루어져 있다.

2. 앞 7자리는 상품 고유의 번호를 나타내며, 마지막 자리는 검증 코드를 나타낸다.

검증 코드는 아래와 같은 방법으로 계산한다.

“(홀수 자리의 합 x 3) + 짝수 자리의 합 + 검증 코드” 가 10의 배수가 되어야 한다.

상품 고유의 번호가 8801234일 경우,

    “( ( 8 + 0 + 2 + 4 ) x 3 ) + ( 8 + 1 + 3 ) + 검증 코드”

    = “42 + 12 + 검증 코드”

    = “54 + 검증 코드” 가 10의 배수가 되어야 하므로, 검증 코드는 6이 되어야 한다.

즉, 88012346 이 정상적인 암호 코드고, 그 외의 검증 코드가 포함된 경우 비정상적인 암호 코드다.

A 업체에서는 이 암호 코드들을 빠르고 정확하게 인식할 수 있는 스캐너를 개발하려고 한다. 스캐너의 성능은 아래와 같은 방법으로 측정된다.

1. 세로 50. 가로 100 이하의 크기를 가진 직사각형 배열에 암호 코드 정보가 포함되어 전달된다. 이때, 하나의 배열에는 1개의 암호 코드가 존재한다. (단, 모든 암호 코드가 정상적인 암호 코드임을 보장할 수 없다. 비정상적인 암호 코드가 포함될 수 있다.)

2. 배열은 1, 0으로 이루어져 있으며 그 안에 포함되어 있는 암호 코드 정보를 확인한다.

3. 포함된 암호 코드들의 검증 코드를 확인하여 정상적인 암호 코드인지 확인한다.

4. 정상적인 암호 코드들을 판별한 뒤 이 암호 코드들에 적혀있는 숫자들의 합을 출력한다.

5. 이때, 총 소요시간이 적을수록 성능이 좋은 것으로 간주된다. 

1과 0의 비율에 따라 의미하는 숫자가 다르다.

 

💡 아이디어

---

문제만 읽었을 땐 상당히 복잡한 문제라고 느껴진다. 하지만, 이해를 하고 나면 그렇게 어려운 문제는 아니다.

문제에 대해서 간단히 설명하자면 2차원 배열에 이진 코드가 암호로 숨어져 있다.

이 이진 코드는 총 56자리이며 7자리씩 나누어 8개의 숫자를 얻은 후

“(홀수 자리의 합 x 3) + 짝수 자리의 합 + 검증 코드” 가 10의 배수가 되는지 확인하면 된다.

우선 0 ~ 9까지의 패턴을 보면 마지막엔 항상 1이 존재하는 것을 알 수 있다.

그렇기 때문에 행의 끝에서부터 탐색하면서 1이 존재한다면 그 자리를 포함해 56자리를 하나의 문자열로 분리한다.

그 후 56자리의 문자열에서 다시 7자리씩 분리해 패턴과 비교하며 알맞은 숫자를 찾아 배열에 넣어준다.

그렇게 되면 총 8개의 숫자가 배열에 저장되게 되는데 이를 이용해 계산을 하면 답을 얻을 수 있다.

테스트 케이스를 보면 같은 코드가 여러 번 나오기도 하고, 0으로만 채워져 있는 행도 있다.

불필요한 시간을 줄이기 위해 행이 전부 0이거나 이전에 계산한 이진 코드라면 다음 행으로 넘어가도록 한다.

 

💡 소스코드

---

package SWEA;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class SWEA_P1240_단순_2진_암호코드 {
	static String[] CODE = { "0001101", "0011001", "0010011", "0111101", "0100011", "0110001", "0101111", "0111011",
			"0110111", "0001011" };//0~9값을 가지는 코드

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("./SWEA_INPUT/SWEA_P1240_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int TC = 1; TC <= T; TC++) {
			StringTokenizer sz = new StringTokenizer(br.readLine());
			int row = Integer.parseInt(sz.nextToken());
			int col = Integer.parseInt(sz.nextToken());

			String msg = null;
			String NON_CODE = null;

			for (int i = 1; i <= col; i++)
				NON_CODE += String.valueOf(0);//전부 0으로 채워진 CODE

			for (int i = 1; i <= row; i++) {
				String str = br.readLine();

				if (str.contains(NON_CODE))//전부 0으로 채워진 line이라면 continue
					continue;

				else {//그게 아니라면
					for (int j = col - 1; j >= 0; j--) {
						if (str.charAt(j) - '0' == 1) {
							msg = str.substring(j - 55, j);//코드 부분만 분리
							break;
						}
					}
				}
			}

			System.out.println("#" + TC + " " + solve(msg + "1"));//출력
		}

		br.close();
	}

	public static int solve(String str) {
		int[] num = new int[8];
		int idx = 0;

		for (int i = 0; i < str.length(); i += 7) {
			String s = str.substring(i, i + 7);
			for (int j = 0; j < 10; j++) {
				if (s.equals(CODE[j])) {//코드와 매치되는 패턴이 있다면
					num[idx++] = j;//num배열에 추가
					break;
				}
			}
		}

		int check = (num[0] + num[2] + num[4] + num[6]) * 3 + num[1] + num[3] + num[5] + num[7];//올바른 코드인지 확인

		if (check % 10 != 0)
			return 0;

		int result = 0;

		for (int j = 0; j < idx; j++)
			result += num[j];//올바른 코드라면 result에 더해주고

		return result;//return
	}
}

 

💡 결과

---

문제를 조금 더 친절하게 줬다면 굉장히 쉬운 문제일 텐데.....

패턴의 끝이 1이라는 중요한 점을 파악하기까지 시간이 꽤 오래 걸린 문제이다.