알고리즘 문제풀이/SWEA
[SWEA] 1242번 암호코드 스캔 자바(java) 풀이
- -
sw expert academy 1242 암호코드 스캔 자바(java) 풀이
- 난이도 : D5
- sw expert academy 1242 암호코드 스캔
문제 정리
- 암호는 총 8개의 숫자로 이루어져있다.
- 앞 7자리는 상품 고유의 번호를, 마지막 자리는 검증코드를 나타낸다.
- 검증코드 계산은 다음과 같이 한다.
- (홀수 자리의 합 * 3 ) + 짝수 자리의 합 + 검증 코드는 10의 배수가 되어야 한다.
- 암호코드 숫자 하나의 길이는 최소7이며 7의 배수로 늘어날 수 있다. (각 숫자는 흰색과 파란색의 넓이 비로 표현된다)
- 원래 9인 "0001011"의 비는 3:1:1:2이다. 2배로 늘어나게 되면 "00000011001111"이 된다. 비율은 같으므로 이도 9를 표현한다.
- 암호코드에 포함된 숫자들의 합을 출력한다.
문제 풀이
처음에는 문제 이해부터 힘들었습니다...
배열에 하나의 암호코드가 아니라 여러개의 암호코드가 들어있을 수 있습니다.
그때 들어있는 모든 암호코드를 숫자로 변환하여 합을 구해야합니다.
같은 암호코드가 여러줄에 걸쳐서 쓰여있는데 이 경우 모든 줄의 암호코드를 숫자로 바꿔서 더하는 것이 아니라
같은 줄 중 하나의 암호코드만 숫자로 변환하여 더해주면 됩니다!!
암호문을 2진수로 변환해서 풀어야 합니다.
숫자 암호들은 0으로 시작해서 '0101'의 패턴을 가지고 1로 끝납니다
- 오른쪽에서 부터 탐색하여 1이 처음 나오고 그 위에 숫자가 0이라면 바코드의 우상단임을 알 수 있습니다. 이 경우만 암호코드의 값을 게산하면 같은 암호코드를 계산할 일이 없습니다.
배수는 어떻게 판단할 것인가?
- 2 4 6 2가 나왔다고 하자. 그러면 가장 작은 수의 배수가 됨을 알 수 있습니다. (모두 1을 포함함)
- 가장 작은 수가 2이므로 2로 나누어줘서 1232가 됨을 알 수 있습니다.
- 오른쪽의 3수가 모두 다르므로 오른쪽의 3개의 수만 봐도 됩니다.
- code를 다음과 같이 판별 할 수 있습니다.
integer형으로 바꾸어서 bit shift 연산을 통해 번역하지 않고 하나씩 읽어가며 할 수 있습니다.0은 3:2:1:1이다. 이중 오른쪽 3개의 수는 2:1:1이다. 이를 s[2][1][1] = 0로 표현합니다. 1는 s[2][2][1] = 1로 표현합니다. 나머지 수들도 마찬가지입니다.
이전 줄과 같은 줄은 입력받은 경우 스킵
이는 구현하지 않아도 통과할 수 있습니다.
입력을 보면 똑같은 줄이 많이 주어집니다. 이러한 경우 이전 줄과 같으면 탐색을 하지 않고 skip하게 되면 더 빠른 시간안에 답을 도출할 수 있습니다.
skip 하는 부분을 추가함으로써 200ms 가까이 빠르게 답을 낼 수 있었습니다.암호코드에 포함된 숫자 계산
암호코드는 오른쪽의 3개의 수만 보면 됩니다. 이를 x,y,z 변수를 이용하여 찾습니다.
코드는 0/1/0/1이 번갈아서 나옵니다.
뒤에서 부터 탐색하므로 뒤의 1의 개수를 z, 뒤의 0의 개수를 y에, 앞쪽의 1의 개수를 x에 담습니다.
이렇게 1/0/1의 각각 개수를 찾고 최소 값을 찾아서 그 값으로 나누어 주게 되면 어떤 숫자를 나타내는지 num배열을 통해 알 수 있습니다.
swea 암호코드 스캔 자바 코드
코드를 아래에 첨부하며 주석도 달아두었으니 참고하시기 바랍니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
class Solution {
static char[][] map;
static int width, height;
static int[][][] num;
static int ans;
static int hcode[][] = {
{ 0, 0, 0, 0 }, //0
{ 0, 0, 0, 1 }, //1
{ 0, 0, 1, 0 }, //2
{ 0, 0, 1, 1 }, //3
{ 0, 1, 0, 0 }, //4
{ 0, 1, 0, 1 }, //5
{ 0, 1, 1, 0 }, //6
{ 0, 1, 1, 1 }, //7
{ 1, 0, 0, 0 }, //8
{ 1, 0, 0, 1 }, //9
{ 1, 0, 1, 0 }, //A
{ 1, 0, 1, 1 }, //B
{ 1, 1, 0, 0 }, //C
{ 1, 1, 0, 1 }, //D
{ 1, 1, 1, 0 }, //E
{ 1, 1, 1, 1 } //F
};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testNum = Integer.parseInt(br.readLine());
for(int test=1; test<=testNum; test++){
String[] temp = br.readLine().split(" ");
height = Integer.parseInt(temp[0]);
width = Integer.parseInt(temp[1]);
num = new int[4][3][4];
map = new char[height][width*4];
initCode();
int codeLen = 7;
int[] code = new int[8];
ans = 0;
// 암호
String before = "";
for(int i=0; i<height; i++){
String input = br.readLine();
// 첫 줄 or 이전 줄과 똑같을 경우 탐색 X
if(input.equals(before) || i == 0) {
before = input;
continue;
}
// map 만들기
String[] temp2 = input.split("");
makeMap(before.split(""), i-1);
makeMap(temp2, i);
// 암호코드 탐색
for(int j=width*4-1; j>0; j--){
// 바코드의 우상단인 경우
if(map[i][j] != '\0' && map[i-1][j] == '\0'){
int x,y,z;
x=y=z=0;
// x, y, z
// 1/0/1
// 1의 개수
while(map[i][j] != '\0'){
z++;
j--;
}
// 0의 개수
while(map[i][j] == '\0'){
y++;
j--;
}
// 1의 개수
while(map[i][j] != '\0'){
x++;
j--;
}
// 0의 개수
while(map[i][j] == '\0'){
j--;
// 맨 왼쪽은 쭉 null 문자만 나오므로 인덱스가 0에 도달하게 되면 탈출
if(j < 0)
break;
}
j++;
// 제일 작은 값 찾아서 나누기
int min = x;
if(min > y)
min = y;
if(min > z)
min = z;
x /= min;
y /= min;
z /= min;
// 찾은 숫자 쓰기
code[codeLen--] = num[x-1][y-1][z-1];
// 7개를 모두 찾음
if(codeLen == -1){
// 검증 코드 구하기
int odd = 0;
int even = 0;
for(int t=0; t<code.length; t++){
if(t % 2 == 0)
even += code[t];
else
odd += code[t];
}
int verificationCode = even*3 + odd;
if(verificationCode % 10 == 0)
ans += odd + even;
codeLen = 7;
}
}
}
before = input;
}
System.out.println("#" + test + " " + ans);
}
br.close();
}
public static void initCode(){
for(int i=0; i<4; i++)
for(int j=0; j<3; j++)
for(int k=0; k<4; k++)
num[i][j][k] = -1;
num[1][0][0] = 0;
num[1][1][0] = 1;
num[0][1][1] = 2;
num[3][0][0] = 3;
num[0][2][1] = 4;
num[1][2][0] = 5;
num[0][0][3] = 6;
num[2][0][1] = 7;
num[1][0][2] = 8;
num[0][0][1] = 9;
}
public static int hexToDec(char ch){
int num = 0;
switch(ch){
case 'A':
num = 10;
break;
case 'B':
num = 11;
break;
case 'C':
num = 12;
break;
case 'D':
num = 13;
break;
case 'E':
num = 14;
break;
case 'F':
num = 15;
break;
default:
num = Character.getNumericValue(ch);
}
return num;
}
public static void makeMap(String[] temp2, int w) {
for(int q=0; q<width; q++){
int t = hexToDec(temp2[q].charAt(0));
for(int k=0; k<4; k++)
map[w][q*4 + k] = (char)hcode[t][k];
}
}
}
Contents
소중한 공감 감사합니다