[Coding Test] 암호코드 스캔 (SWEA: 1242)

암호코드 스캔 (SWEA: 1242)

암호코드 스캔 문제는 이곳에서 볼 수 있습니다.

엄청난 구현 문제입니다.

• 암호 코드 저장 배열 전역 변수 설정
• 16진수로 인코딩 된 문자열을 4bit의 0과 1로 나타내는 방법
• 스케일을 구해내는 함수
• 중복된 검사를 피하는 방법

등을 4시간 안에 구현해야 합니다. 저는 3일이 꼬박 걸렸습니다. 그것도 몇 문제는 답이 틀리지 않아 해설 영상을 봐야했네요.

중요하게 봐야 할 점은 다음과 같습니다.

• int Hash[5000] 에 값을 저장해 O(1)의 검색 시간 보장
• 문제에서 모든 코드의 오른쪽은 1로 시작하는 점
• 비율에 관계없이 코드 하나에서 이전 값과 달라지는 경계점의 갯수는 동일함

이 힌트들을 생각하며 구현에 힘쓰면 Pass를 받을 수 있을 것입니다. 몇 개의 정답 코드들을 참조해보았는데, 정말 대단한 굇수들이 많다는 감탄만 하다가 돌아왔네요.

소스코드

#include<iostream>
#include<cstring>

using namespace std;

char arr[2000][2000];
char hexaHash[16][5] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
int HashTable[5000];
int N, M;

int getScale(int, int);
int decode(int, int, int);

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	//freopen("sample_input.txt", "r", stdin);
	cin >> T;
	
	char ch;
	memset(HashTable, -1, 5000);
	HashTable[3211] = 0; HashTable[2221] = 1; HashTable[2122] = 2; HashTable[1411] = 3; HashTable[1132] = 4;
	HashTable[1231] = 5; HashTable[1114] = 6; HashTable[1312] = 7; HashTable[1213] = 8; HashTable[3112] = 9;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N >> M;

		// input
		for (int row = 0; row < N; row++){
			for (int col = 0; col < M; col++){
				cin >> ch;
				if (ch < 'A') {
					for (int idx = 0; idx < 4; idx++) {
						arr[row][col * 4 + idx] = hexaHash[ch - '0'][idx];
					}
				}
				else {
					for(int idx = 0; idx < 4; idx++){
						arr[row][col * 4 + idx] = hexaHash[ch - 'A' + 10][idx];
					}
				}
			}
		}

		int answer = 0;

		// find start point
		for (int row = 0; row < N; row++){
			for (int col = 4*M - 1; col >= 55; col--) {
				if (arr[row][col] == '1') {
					// get scale				
					int scale = getScale(row, col);

					// decode code
					int startPoint = col + 1 - 56 * scale;
					int code[8], possible = 1;
					for (int i = 0; i < 8; i++) {
						code[i] = decode(row, startPoint + i * 7 * scale, scale);
						if (code[i] < 0) { possible = 0; break; }
					}

					// check possible
					if (possible == 1) {

						// 아래 마스킹
						for (int maskRow = row + 1; maskRow < N; maskRow++) {
							for (int maskCol = startPoint; maskCol <= col; maskCol++) {
								if (arr[row][maskCol] == arr[maskRow][maskCol]) {
									arr[maskRow][maskCol] = '0';
								}
								else { maskRow = N; break; }
							}
						}

						// 올바른 값인지 검사
						if (((code[0] + code[2] + code[4] + code[6]) * 3 + (code[1] + code[3] + code[5]) + code[7]) % 10 == 0) {
							for (int i = 0; i < 8; i++) answer += code[i];
						}

						// 다음 포인트 서치
						col = startPoint - 1;
					}
				}
			}
		}

		cout << "#" << test_case << ' ' << answer << endl;
	}

	return 0;
}

int getScale(int row, int col) {
	int cnt = 0;
	for (int i = col; i > 0; i--) {
		if (arr[row][i] != arr[row][i - 1]) cnt++;
		if (cnt == 4) return (col - i + 1) / 7;
	}

	return 1;
}

int decode(int row, int col, int scale) {
	// scale step 으로 읽으면서 비율 계산
	int cnt = 1;
	int key = 0;

	for (int i = 0; i < 7 * scale; i++) {
		if (col + i < 4 * M - 1 && arr[row][col + i] == arr[row][col + i + 1]) {
			cnt++;
		}
		else {
			cnt /= scale;
			key = key * 10 + cnt;
			cnt = 1;
		}
	}

	return HashTable[key];
}