[JAVA] SWEA 1242번 암호코드 스캔

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15JEKKAM8CFAYD&categoryId=AV15JEKKAM8CFAYD&categoryType=CODE

SW Expert Academy

 

이전에 포스트한 단순 2진 암호코드의 심화문제이다.

 

하지만 훨씬 더럽.... 어려워 푸는데 시간이 꽤 걸렸다.

 

단순 2진 암호코드와의 차이점이라면,

 

16진수의 입력을 2진수로 바꾸어 값을 구해야 하는 점,

 

라인마다 입력이 달라 여러 라인을 받아 모두 확인해야 한다는 점,

 

그리고 이전 문제는 어렵지 않아 값을 비율로 구하지 않았었는데, 각 수의 0과 1의 비율로 코드를 해독해야 한다는 점

 

등이 있을 것이다.

 

풀이

• 같은 라인을 받을 필요는 없기에 동일 라인을 필터, 0으로만 이루어진 라인을 필터링하였다.
• 동일 입력, 동일 라인에 여러개의 암호코드가 존재하기 때문에, 암호코드를 개별로 저장할 배열을 선언하였다.
• 16진수 -> 2진수는 각각에 매칭되는 배열을 만들어 변환하였다.
• 암호코드는 0으로 시작해 1로 끝나기 때문에, 오른쪽 끝에 있는 0들은 필요가 없다. 모두 삭제한다.
• 오른쪽부터 탐색하며, 암호코드를 비율에 맞게 찾아야한다.
• 모든 암호코드는 0->1->0->1 순으로 진행된다.
• 오른쪽부터 확인하기 때문에, 1->0->1->0 순으로 진행되며, 선행되는 값이 무조건 있어야 다음 값이 채워지도록 해야한다.
• 예를들어보자. 0111011을 오른쪽부터 확인한다. '1'이 2개, '0'이 1개, '1'이 3개, '0'이 1개이다.
• 일렬로 나열하면 1312가 된다. 
• 미리 선언해놓은 codes 배열을 보면 1312는 7번째 인덱스의 값이고, sum 배열의 8번째 인덱스에 7을 저장하면 된다.
• 00111111001111를 예로 들면 '1'이 4개, '0'이 2개, '1'이 6개, '0'이 2개이다.
• 일렬로 나열하면 2624이고, 이 경우 14비트를 사용했기 때문에, 기존 7비트의 2배수임을 알 수 있고, 
• 각 값을 2로 나누어 암호코드를 구하면 된다.
• 2로 나누면 1312 임을 알 수 있고, 암호코드 7을 도출할 수 있다.
• 이후, 모든 값을 더하면 문제를 해결할 수 있다.
• 동일한 암호코드 더미를 중복하여 더할 가능성이 있기 때문에, 검증과정에서 이를 필터링해주는 것도 잊으면 안된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 암호코드스캔 {
	static ArrayList<String> hexPasswords;
	static String passwords[];
	static int sum[][];
	static ArrayList<String> sumResult;
	// 16진수
	static char hex[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
	// 16진수에 매칭되는 2진수
	static String hexToBin[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", 
			"1001", "1010", "1011", "1100", "1101", "1110", "1111"};
	// 0-9 값의 비율
	static String codes[] = {"3211", "2221", "2122", "1411", "1132", "1231", "1114", "1312", "1213", "3112"};
	static int result;
	
	// 암호코드 판별
	public static void Verification(int[] sum) {
		int n1 = 0, n2 = 0;
		
		for (int i = 1; i < sum.length; i++) {
			if (i % 2 == 1) n1 += sum[i];
			else if (i % 2 == 0) n2 += sum[i];
		}
		
		// 정상적인 암호코드라면 sumResult에 저장하고, 중복 필터
		if (((n1 * 3) + n2) % 10 == 0)
			if (!sumResult.contains(Arrays.toString(sum).replaceAll("[^0-9]", "")))
				sumResult.add(Arrays.toString(sum).replaceAll("[^0-9]", ""));
	}
	
	public static int Encode() {
		int cur = 0;
		
		// 오른쪽 끝에 채워져있는 0 제거
		for (int k = 0; k < passwords.length; k++) {
			for (int i = passwords[k].length() - 1; i > 0; i--) {
				if (passwords[k].charAt(i) != '0') {
					passwords[k] = passwords[k].substring(0, i + 1);
					break;
				}
			}
		}
		
		for (int k = 0; k < passwords.length; k++) {
			int r1 = 0, r2 = 0, r3 = 0, r4 = 0;
			int idx = 8;
			
			for (int i = passwords[k].length() - 1; i > 0; i--) {
				// 오른쪽부터 값 하나 추출
				char temp = passwords[k].charAt(i);
				
				// 값의 비율 측정
				if (temp == '1' && r3 == 0) r4++;
				else if (temp == '0' && r2 == 0) { 
					if (r4 != 0) r3++;
					else passwords[k] = passwords[k].substring(0, i);
				}
				else if (temp == '1' && r1 == 0) r2++;
				else {
					int mul = Math.min(Math.min(r2, r3), r4);
					
					// 7의 배수로 r1 도출
					r1 = (mul * 7) - (r2 + r3 + r4);
					int rateSum = r1 + r2 + r3 + r4;
					
					// codes에 저장된 비율로 맞춤
					r1 /= mul; 
					r2 /= mul; 
					r3 /= mul; 
					r4 /= mul;
					
					String code = "";
					code += r1; 
					code += r2; 
					code += r3; 
					code += r4;
					
					// 코드와 매칭되는 인덱스(값) 저장
					sum[cur][idx--] = Arrays.asList(codes).indexOf(code);
					
					if (idx == 0) {
						cur++;
						idx = 8;
					}
					
					r1 = 0; r2 = 0; r3 = 0; r4 = 0;
					
					// 암호 찾은 구간까지 passwords 짜름
					if (passwords[k].length() - rateSum > 0) 
						passwords[k] = passwords[k].substring(0, passwords[k].length() - rateSum);
					else break;
					
					i = passwords[k].length();
				}
			}
		}
		
		for (int i = 0; i < sum.length; i++) 
			Verification(sum[i]);
		
		// sumResult에 들어있는 값 하나씩 모두 더함
		for (String sumStr: sumResult)
			for (int i = 0; i < 9; i++) 
				result += sumStr.charAt(i) - '0';
		
		return result;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			
			hexPasswords = new ArrayList<>();
			sumResult = new ArrayList<>();
			result = 0;
			
			for (int i = 0; i < N; i++) {
				String str = br.readLine();
				
				// 동일 라인 필터
				if (hexPasswords.contains(str)) continue;
				
				// 0으로만 이루어진 라인 필터
				for (int k = 0; k < M; k++) {
					if (str.charAt(k) != '0') {
						hexPasswords.add(str);
						break;
					}
				}
			}
			
			sum = new int[10000][9];
			passwords = new String[hexPasswords.size()];
			
			for (int i = 0; i < passwords.length; i++) passwords[i] = "";
			
			// 16진수 -> 2진수
			for (int k = 0; k < hexPasswords.size(); k++) {
				for (int i = 0; i < hexPasswords.get(k).length(); i++) {
					for (int j = 0; j < hex.length; j++) {
						if (hexPasswords.get(k).charAt(i) == hex[j]) {
							passwords[k] += hexToBin[j];
						}
					}
				}
			}
			
			System.out.println("#" + test_case + " " + Encode());
		}
	}
}