[기업 코딩 테스트] 유효한 시리얼 찾기
얼마전 온라인으로 모 기업에서 코딩테스트를 봤습니다.
재밌는 문제가 나와서 붙잡고 풀어보았는데, 문제가 있었습니다.
우선 문제를 설명 드리겠습니다.
어떤 제품의 제품키는 다음과 같은 규칙을 갖는다.
--------------------------------------------------------------------------------------------------------------
<규칙 설명>
제품키는 다음과 같이 5문자씩 5묶음으로 총 25문자이다. ( 한 묶음에 다섯 문자 )
□□□□■ - □□□□■ - □□□□■ - □□□□■ - □□□□■
제품키의 각 문자는 숫자와 알파벳 대문자, 즉 0~9, A~Z 로만 이루어져있다.
각 묶음의 검은 부분은 제품키를 검증하기 위한 검증문자로서 다른 문자들의 관계로 나타난다.
검증문자 앞에 있는 다섯 개의 문자 (첫번째 검증문자의 경우 앞에 네 개의 문자 밖에 없는데 가장 앞에 0 이 있다고 가정한다. 나머지 검증문자들의 경우 이전 검증문자까지 포함하여 다섯 개의 문자) 에 대한 식으로 나타낼 수 있다.
검증문자 = ( ① * 2 + ② * 3 + ③ * 5 + ④ * 7 + ⑤ * 11 ) % 36
( 문자 0~9 는 숫자 0~9 로 변환하고, 문자 A~Z 는 숫자 10~35 로 변환하여 위 식에 적용 )
--------------------------------------------------------------------------------------------------------------
이와 같은 제품키들이 주어진 파일에 숨겨져 있다.
위의 규칙을 만족하는 제품키들을 모두 찾아 출력하자.
주어진 파일의 문자열은 한 줄이다.
제품키의 5묶음을 구분하기 위한 ‘-‘ 같은 문자 없이, 묶음끼리 붙어있을 수 있다.
주어진 문자열에는 제품키를 구성하는 문자( 0~9, A~Z )가 아닌 문자도 포함되어있다. 이러한 문자들은 제품키의 묶음 사이에만 있을 수 있고, 2개 이상 있을 수 있다. 한 묶음 안에는 이런 문자가 있을 수 없다.
제품키끼리는 겹쳐져 있지 않다.
abcdef-ghijk 경우 bcdef 와 ghjik 만 제품키에 포함 될 수 있습니다.( 검증문자는 차후 문제)
abcdefghijk 경우 abcde가 검증문자에 맞지 않는 경우 bcdef를 가지고 시작 하되 마지막 제품키에서 검증문자가 맞지 않는다면 다시 cdefg를 가지고 시작 해야 합니다.
입력 예시Q2G1C4."E5H{K9LTVK0EIM\&*VI038AII1L@'QMVZ5O8@GEGPZIXYZZF4O4'>:7JT8J!/-HNAZBMX67C=:AXTI98/22105VEC7RDDA6O<08VS1SJLZT^!7HIRB*4D6H53[1(J6,U42*0ZSPMEL3WOI%Q2SPJ>?H61BV:"\NV0H66C1BLWCFRGY.ZM83G~KS7SDUNJD3KZL13EJA6S6DN0CYBB0NH?'SSZSJ+MVXF7&DUPES+-:XT3ZMJXNMD;*923KG#^,4XIBO6GY9F&PXPNEFOKQF==}XD154)1IVY8]O0VGD!}}25P8WQ8WC6]#{7RTVS\.'BVQAW/!HD72ZZIAQ9EGVQ7DESXONBUAW46W;(%E7UWJ*[VD2QS%.{7XJ1Q#@#GDOUGW@T04D^YMEJ80J70RT=URINE_5YQ2L@#KZTVT"QX4JZBYWXH6^D9W63WOBUXG%17OBZ$7HJ9C;**NEK21+BD3W6}M1HRJUZK(0W?YQOPR~( 62ZTY_|#PI7NV[+.WU1MH_01CF1OZID9KK34FGHTQKITIYKN6QHQN2VHVJJAD9[R5QHGIH>MSN7C'^[BYO7414KQP%VD2Q4).NDKKZT5UBN|8W9I:).4KKCO_|750OY.,MMBCL<PD8BZ||@YT4RVDQVH{DK6AID5J7PM7H]ITTD3]+X94BB):}VKSLU??ZCDDSRX3JDJ03M.5HSV3RSTZ5AKA}RTH9WLSVIY)-"NYYZVWT0ILJWT3W2+8J1AOI3VM0$&*RBZXOZ7CWCH5AYG{JPC64(<2I40OLZ3P6#60RILX93SRCRB|K1CUKK6WWD8F59VYX>&$DMU41[>(X0I7HE90PR' WOXI4NHL9{FS3T3[>I0JAFAHVBF(~6ZR1SUB'P1Q2BBTUBOPSO$OBSVS#^87NB1|@83BD9'_Z3ZWG>2*=LDF5KET2WYVP_CUSEA,CK0YQV91W9(750CHWWVGDN출력 예시JXNMD-923KG-4XIBO-6GY9F-PXPNEFOKQF-XD154-1IVY8-O0VGD-25P8WQ8WC6-7RTVS-BVQAW-HD72Z-ZIAQ9K34FG-HTQKI-TIYKN-6QHQN-2VHVJWT3W2-8J1AO-I3VM0-RBZXO-Z7CWCH5AYG-JPC64-2I40O-LZ3P6-60RIL
이런 문제였는데요, 저는 문자열들을 먼저 조건에 맞게끔 정제(영대문자,숫자로만 이루어지며, 연속된 문자열이 5자 이상)후, 규칙을 체크하고 5연속 규칙에 맞으면 시리얼로 판단, 출력하도록 했습니다.
결과는 이렇습니다.
맨 첫줄에 "BBONH-SSZSJ-MVXF7-DUPES-XT3ZM"이 보이시나요?
이것은 입력 문자열에 이렇게 포함되어 있었습니다.
"BB0NH?'SSZSJ+MVXF7&DUPES+-:XT3ZM"
제가 판단한 규칙에 맞고, 그 판단으로 로직을 만들었으니 당연히 맞게 나왔습니다.
각각 5글자 이상으로 중간에 끊어지지 않고, 검증문자 조건도 적합하고..
그런데 예시에는 안나와서 그런지, 정답이 틀린걸로 나왔습니다.
다른분들을 찾아보니 정답처리되신분이 한분 계셔서, 너무 궁금한 마음에 문의 메일을 보냈습니다.
답변이 오면 정리 해서 결과를 알려드리겠습니다.
그리고 아래는 제가 작성한 코드입니다.
#pragma region 문제 설명, 풀이 설명
/*
시리얼 찾기.
어떤 제품의 제품키는 다음과 같은 규칙을 갖는다.
--------------------------------------------------------------------------------------------------------------
<규칙 설명>
제품키는 다음과 같이 5문자씩 5묶음으로 총 25문자이다. ( 한 묶음에 다섯 문자 )
□□□□■ - □□□□■ - □□□□■ - □□□□■ - □□□□■
제품키의 각 문자는 숫자와 알파벳 대문자, 즉 0~9, A~Z 로만 이루어져있다.
각 묶음의 검은 부분은 제품키를 검증하기 위한 검증문자로서 다른 문자들의 관계로 나타난다.
검증문자 앞에 있는 다섯 개의 문자 (첫번째 검증문자의 경우 앞에 네 개의 문자 밖에 없는데 가장 앞에 0 이 있다고 가정한다. 나머지 검증문자들의 경우 이전 검증문자까지 포함하여 다섯 개의 문자) 에 대한 식으로 나타낼 수 있다.
검증문자 = ( ① * 2 + ② * 3 + ③ * 5 + ④ * 7 + ⑤ * 11 ) % 36
( 문자 0~9 는 숫자 0~9 로 변환하고, 문자 A~Z 는 숫자 10~35 로 변환하여 위 식에 적용 )
--------------------------------------------------------------------------------------------------------------
이와 같은 제품키들이 주어진 파일에 숨겨져 있다.
위의 규칙을 만족하는 제품키들을 모두 찾아 출력하자.
주어진 파일의 문자열은 한 줄이다.
제품키의 5묶음을 구분하기 위한 ‘-‘ 같은 문자 없이, 묶음끼리 붙어있을 수 있다.
주어진 문자열에는 제품키를 구성하는 문자( 0~9, A~Z )가 아닌 문자도 포함되어있다. 이러한 문자들은 제품키의 묶음 사이에만 있을 수 있고, 2개 이상 있을 수 있다. 한 묶음 안에는 이런 문자가 있을 수 없다.
제품키끼리는 겹쳐져 있지 않다.
abcdef-ghijk 경우 bcdef 와 ghjik 만 제품키에 포함 될 수 있습니다.( 검증문자는 차후 문제)
abcdefghijk 경우 abcde가 검증문자에 맞지 않는 경우 bcdef를 가지고 시작 하되 마지막 제품키에서 검증문자가 맞지 않는다면 다시 cdefg를 가지고 시작 해야 합니다.
입력 예시
Q2G1C4."E5H{K9LTVK0EIM\&*VI038AII1L@'QMVZ5O8@GEGPZIXYZZF4O4'>:7JT8J!/-HNAZBMX67C=:AXTI98/22105VEC7RDDA6O<08VS1SJLZT^!7HIRB*4D6H53[1(J6,U42*0ZSPMEL3WOI%Q2SPJ>?H61BV:"\NV0H66C1BLWCFRGY.ZM83G~KS7SDUNJD3KZL13EJA6S6DN0CYBB0NH?'SSZSJ+MVXF7&DUPES+-:XT3ZMJXNMD;*923KG#^,4XIBO6GY9F&PXPNEFOKQF==}XD154)1IVY8]O0VGD!}}25P8WQ8WC6]#{7RTVS\.'BVQAW/!HD72ZZIAQ9EGVQ7DESXONBUAW46W;(%E7UWJ*[VD2QS%.{7XJ1Q#@#GDOUGW@T04D^YMEJ80J70RT=URINE_5YQ2L@#KZTVT"QX4JZBYWXH6^D9W63WOBUXG%17OBZ$7HJ9C;**NEK21+BD3W6}M1HRJUZK(0W?YQOPR~( 62ZTY_|#PI7NV[+.WU1MH_01CF1OZID9KK34FGHTQKITIYKN6QHQN2VHVJJAD9[R5QHGIH>MSN7C'^[BYO7414KQP%VD2Q4).NDKKZT5UBN|8W9I:).4KKCO_|750OY.,MMBCL&$DMU41[>(X0I7HE90PR' WOXI4NHL9{FS3T3[>I0JAFAHVBF(~6ZR1SUB'P1Q2BBTUBOPSO$OBSVS#^87NB1|@83BD9'_Z3ZWG>2*=LDF5KET2WYVP_CUSEA,CK0YQV91W9(750CHWWVGDN
출력 예시
JXNMD-923KG-4XIBO-6GY9F-PXPNE
FOKQF-XD154-1IVY8-O0VGD-25P8W
Q8WC6-7RTVS-BVQAW-HD72Z-ZIAQ9
K34FG-HTQKI-TIYKN-6QHQN-2VHVJ
WT3W2-8J1AO-I3VM0-RBZXO-Z7CWC
H5AYG-JPC64-2I40O-LZ3P6-60RIL
문제 풀이 방식
먼저 문자를 입력받는다(여기에서는 입력하기 귀찮아서 string으로 대체)
그 후 먼저 범위 내의 문자로 정제한다(시리얼은 5자리씩 5묶음으로 이루어져 있으므로, 5자리 아래는 제외, 영대문자, 숫자 외의 문자도 제외)
그리고 문자열의 처음부터 끝까지 1칸씩 반복하되, 검증된 시리얼을 찾으면 25칸을 건너뛰고 다시 찾는다.
반복행위는 다음과 같다.
위의 조건대로 검증을 한다.
검증이 된다면? -> 그다음 문자들을 검증을 한다 x 4번 반복.
시리얼이 검증이 된다면, 시리얼을 출력한다.
*/
#pragma endregion
#include <stdio.h>
#include <stdlib.h>
#define MAX 10000 //입력받을 문자열의 최대 길이
#define NOTVALIDCHARACTER 127 //의미없는 검증 외의 문자
typedef enum {FALSE,TRUE} Boolean; //Boolean 타입 정의
char checkTable[256]; //검증용 테이블 전역변수
#pragma region 함수 전방 선언
void InitTable(); //검증용 테이블 생성
int GetLength(char* str); //문자열의 길이 구하기
void FindSerial(char* str); //시리얼 찾기
char* CreateValidString(char* str); //입력받은 문자열에서 범위 제외 된 문자 제거
Boolean CheckCharacter(char ch); //범위내의 문자인지 검사
Boolean SerialValidateCheck(char * str, char target, Boolean isFirst); //규칙 검증
Boolean ValidateCheckString(char *str, int *index, int minLength, char* key); //규칙 검증(범위 외의 문자인지 판별)
char* substring(char *input, int index, int length); //문자열 자르기
char* DeleteString(char *input, int index, int length); //범위내의 문자열 없애기
int FindCharacter(char* input, int index, char key); //문자 찾기
#pragma endregion
int main() {
//문자열(입력받았다고 친다)
char* string="Q2G1C4.\"E5H{K9LTVK0EIM\&*VI038AII1L@'QMVZ5O8@GEGPZIXYZZF4O4'>:7JT8J!/-HNAZBMX67C=:AXTI98/22105VEC7RDDA6O<08VS1SJLZT^!7HIRB*4D6H53[1(J6,U42*0ZSPMEL3WOI%Q2SPJ>?H61BV:\"\NV0H66C1BLWCFRGY.ZM83G~KS7SDUNJD3KZL13EJA6S6DN0CYBB0NH?'SSZSJ+MVXF7&DUPES+-:XT3ZMJXNMD;*923KG#^,4XIBO6GY9F&PXPNEFOKQF==}XD154)1IVY8]O0VGD!}}25P8WQ8WC6]#{7RTVS\.'BVQAW/!HD72ZZIAQ9EGVQ7DESXONBUAW46W;(%E7UWJ*[VD2QS%.{7XJ1Q#@#GDOUGW@T04D^YMEJ80J70RT=URINE_5YQ2L@#KZTVT\"QX4JZBYWXH6^D9W63WOBUXG%17OBZ$7HJ9C;**NEK21+BD3W6}M1HRJUZK(0W?YQOPR~( 62ZTY_|#PI7NV[+.WU1MH_01CF1OZID9KK34FGHTQKITIYKN6QHQN2VHVJJAD9[R5QHGIH>MSN7C'^[BYO7414KQP%VD2Q4).NDKKZT5UBN|8W9I:).4KKCO_|750OY.,MMBCL<pd8bz||@yt4rvdqvh{dk6aid5j7pm7h]ittd3]+x94bb):}vkslu??zcddsrx3jdj03m.5hsv3rstz5aka}rth9wlsviy)-\"nyyzvwt0iljwt3w2+8j1aoi3vm0$&*rbzxoz7cwch5ayg{jpc64(<2i40olz3p6#60rilx93srcrb|k1cukk6wwd8f59vyx>&$DMU41[>(X0I7HE90PR' WOXI4NHL9{FS3T3[>I0JAFAHVBF(~6ZR1SUB'P1Q2BBTUBOPSO$OBSVS#^87NB1|@83BD9'_Z3ZWG>2*=LDF5KET2WYVP_CUSEA,CK0YQV91W9(750CHWWVGDN";
InitTable(); //테이블 입력
char* validString = CreateValidString(string); //문자열 정제
FindSerial(validString); //시리얼 탐색 및 출력
return 0; //종료
}
#pragma region 검증 테이블 생성
/*
* 검증용 테이블 생성
* 규칙에 맞는 테이블(0~9는 0~9, A~Z는 10~35까지 등록하고 그 외는 다 의미없는, 마지막 숫자인 127로 지정한다
* 입력 : 없음
* 출력 : checkTable(전역 변수 테이블)
*/
void InitTable() {
int i = 0;
int num = 0;
while (i < 256) {
checkTable[i] = NOTVALIDCHARACTER;
i++;
}
i = '0';
num = 0;
while (i <= '9') {
checkTable[i++] = num++;
}
i = 'A';
num = 10;
while (i <= 'Z') {
checkTable[i++] = num++;
}
}
#pragma endregion
#pragma region 문자열 정제 함수
/*
* 정제 문자열 만들기
* 문자열을 입력받아, 규칙에 맞지 않는 문자열을 제거한다.
* (규칙 : 알파벳 대문자 혹은 숫자인지 여부, 알파벳이 연속적으로 5글자 이상인지 여부)
* 입력 : 정제되지 않은 문자열
* 출력 : 정제된 문자열
*/
char* CreateValidString(char* str) {
int length = GetLength(str);
char* checkString = (char*)malloc(sizeof(char) * length);
int i = 0;
int j = 0;
while (i < length) {
if (checkTable[str[i]] == NOTVALIDCHARACTER) {
i++;
continue;
}
char* tmpString = (char*)malloc(sizeof(char)*length);
if (ValidateCheckString(str, &i, 5, tmpString) == TRUE) {
int k = 0;
while (tmpString[k] != NULL) {
checkString[j++] = tmpString[k++];
}
}
free(tmpString);
tmpString = NULL;
}
checkString[j++] = NULL;
return checkString;
}
/*
* 문자열 검증
* 문자열을 입력받아, 시작지점부터 검증범위 내의 문자열들이 나올동안 문자열을 만들어서 출력한다
* 입력 : 전체 문자열, 문자열 위치, 최소 길이
* 출력 : 유효여부, 만들어진 문자열
*/
Boolean ValidateCheckString(char *str, int *index, int minLength, char* key) {
int length = GetLength(str);
int j = 0;
int count = 0;
while ((*index) < length) {
if (checkTable[str[(*index)]] != NOTVALIDCHARACTER) {
key[j++] = str[(*index)];
count++;
(*index)++;
}
else break;
}
key[j] = NULL;
if (count >= minLength) return TRUE;
else {
return FALSE;
}
}
#pragma endregion
#pragma region 시리얼 탐색 함수
/*
* 시리얼 탐색
* 유효성 검사를 끝낸 문자열을 입력받아서, 총 25자의 규칙에 맞는 시리얼인지 확인 후, 규칙에 맞다면 출력한다
* 입력 : 검사를 끝낸 문자열(str)
* 출력 : 없음(대신, 화면에 출력)
*/
void FindSerial(char* str) {
int index = 0;
int length = GetLength(str);
while (index + 25 < length) {
if (SerialValidateCheck(str + index, str[index + 4], TRUE)) {
int tmpIndex = index + 4;
if (SerialValidateCheck(str + tmpIndex, str[tmpIndex + 5], FALSE)) {
tmpIndex += 5;
if (SerialValidateCheck(str + tmpIndex, str[tmpIndex + 5], FALSE)) {
tmpIndex += 5;
if (SerialValidateCheck(str + tmpIndex, str[tmpIndex + 5], FALSE)) {
tmpIndex += 5;
if (SerialValidateCheck(str + tmpIndex, str[tmpIndex + 5], FALSE)) {
char* test = substring(str, index, 25);
printf("%s-%s-%s-%s-%s\n", substring(str, index, 5), substring(str, index + 5, 5), substring(str, index + 10, 5), substring(str, index + 15, 5), substring(str, index + 20, 5));
index = tmpIndex + 5;
}
}
}
}
}
index++;
}
}
/*
* 시리얼 유효성 체크
* 시리얼 토막을 입력받아서, 규칙에 맞는지 확인한다
* 입력 : 시리얼, 검증 문자, 첫 묶음인가에 대한 플래그
* 출력 : 검증 유무
*/
Boolean SerialValidateCheck(char * str, char target, Boolean isFirst)
{
int char1, char2, char3, char4, char5;
if (isFirst) {
char1 = 0;
char2 = checkTable[str[0]] * 3;
char3 = checkTable[str[1]] * 5;
char4 = checkTable[str[2]] * 7;
char5 = checkTable[str[3]] * 11;
}
else {
char1 = checkTable[str[0]] * 2;
char2 = checkTable[str[1]] * 3;
char3 = checkTable[str[2]] * 5;
char4 = checkTable[str[3]] * 7;
char5 = checkTable[str[4]] * 11;
}
int value = (char1 + char2 + char3 + char4 + char5) % 36;
if (value == checkTable[target]) return TRUE;
else return FALSE;
}
#pragma endregion
#pragma region 문자열 제어 함수들
/*
* 문자 체크
* 입력받은 문자가 검증 범위 내의 문자인지 판별한다
* 입력 : 검증 할 문자
* 출력 : 검증 결과
*/
Boolean CheckCharacter(char ch) {
for (int i = 0; i < 256; i++) {
if (checkTable[ch] != NOTVALIDCHARACTER) return TRUE;
}
return FALSE;
}
/*
* 문자열 자르기
* 문자열의 원하는 값을 잘라온다
* 입력 : 전체 문자열, 시작 위치, 길이
* 출력 : 잘린 문자열
*/
char* substring(char *input, int index, int length) {
int size = length + 2;
int i;
char *substring = (char*)malloc(size * sizeof(char));
i = 0;
while (i < length) {
substring[i] = input[index + i];
i++;
}
substring[i] = NULL;
return substring;
}
/*
* 문자열 부분 삭제
* 문자열에서 원하는 길이만큼 부분을 자른다
* 입력 : 전체 문자열, 시작위치, 길이
* 출력 : 해당 범위가 삭제 된 전체 문자열
*/
char* DeleteString(char* input, int index, int length) {
int i = 0;
int j = 0;
int maxLength = GetLength(input);
char *deletestring;
deletestring = (char*)malloc(maxLength * sizeof(char));
while (i < maxLength) {
if (i < index || i >(index + length)) deletestring[j++] = input[i];
i++;
}
deletestring[j++] = NULL;
return deletestring;
}
/*
* 문자 찾기
* 문자열에서 문자를 찾는다
* 입력 : 문자열, 위치, 찾을 문자
* 출력 : 위치
*/
int FindCharacter(char* input, int index, char key) {
int i = index;
int length = GetLength(input);
while (i < length) {
if (input[i] == key) return i;
i++;
}
return -1;
}
/*
* 문자열 길이 확인
* 문자열의 길이를 확인한다
* 입력 : 문자열
* 출력 : 문자열 길이
*/
int GetLength(char* str) {
int i = 0;
while (str[i] != NULL) i++;
return i;
}
#pragma endregion
반응형