[취업] Kakao 코딩 테스트 문제 [1]

카카오 코딩테스트를 풀어보자!


한번 풀어보는 것에 대해 많은 도움이 될 것 같아 포스팅 해보려합니다.


저는 단순 풀어보는데에 의의를 두고 있기에, 더 좋은 방법이 있다면 공유 부탁드려요




문제를 사이트에서 직접 풀어보지 않아. 처음부터 끝까지 구현하긴 했는데...


Solution에 대한 함수만 짜면 된다는 얘기를 들은 거 같아, 혹시 아신다면 공유 부탁드릴게요




우선 문제에 대한 설명입니다. ( http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/ )





문제 1에 대해서 풀어보겠습니다...!

문제를 푼 환경은 Linux(Centos) C++로 풀었습니다.




1. 비밀 지도(난이도: 하)

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다.
다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.


1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 “공백”(“ “) 또는 “벽”(“#”) 두 종류로 이루어져 있다.


2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 “지도 1”과 “지도 2”라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다.
지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.


3. “지도 1”과 “지도 2”는 각각 정수 배열로 암호화되어 있다.


4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

입력 형식
= 입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.
- 1 ≦ n ≦ 16
- arr1, arr2는 길이 n인 정수 배열로 주어진다.
- 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2^n - 1을 만족한다.


출력 형식
= 원래의 비밀지도를 해독하여 "#", 공백으로 구성된 문자열 배열로 출력하라.

분석 해보면 이 문제는

arr1의 9 , 20, 28, 18, 11

arr2의 30, 1, 21, 17, 28 의

10진수 값을 2진수로 바꾼 후,

bit or 연산이 필요한 문제입니다.


그것을 단순히 '#'와 ' ' 로 풀면 되게 됩니다.



문제의 순서를 따져보면...



1. arr1과 arr2를 2진수화 한다. ( = 2진수로 직접 변환하거나 stl의 bitset이 있는데, 이것을 이용하면 될 듯합니다 )


2. arr1과 arr2의 값을 or한다


3. arr1과 arr2의 or값에 값이 있다면 '#' 없다면 ' ' 를 출력한다. 입니다.



저는 일단, 문제 풀 당시 bitset을 몰라서, 일일이 다 구현하긴했는데...


if else로 풀어서 질이 떨어집니다.



이후 수정할 수 있도록 노력해야겠네요...

#include 
#include 
#include 
#define LOG printf
using namespace std;

int case1N = 5;
int case1_secretValue[]  = {9, 20, 28, 18, 11};
int case1_secretValue2[] = {30, 1, 21, 17, 28};

int case2N = 6;
int case2_secretValue[]  = {46, 33, 33, 22, 31, 50};
int case2_secretValue2[] = {27, 56, 19, 14, 14, 10};




void binaryChange(int val, string& printVal, int size)
{
 /******************
  * 나머지가 
  * 1 이면 #
  * 0 이면 공백 
  ******************/
 int limit = 0;
 string strVal;
 do
 {
  int remaind = val % 2;
  (remaind == 0) ? strVal.append(" ") : strVal.append("#");
  val = val / 2;
  limit++;
 } 
 while ( limit < size );
 reverse(strVal.begin(), strVal.end());
 strVal.append("\n");
 printVal.append(strVal);
}

void merge_map(const char* str1, const char* str2, string& value, int size)
{
 char *pStr1 = (char*)str1;
 char *pStr2 = (char*)str2;
 int idx = 0;
 while ( size > idx )
 {
  /**********************
   * 간결하게 짜보자...
                 * bitset을 이용하자
   **********************/
  if ( *pStr1 == '#' || *pStr2 == '#' )
  { 
   value.append("#");
  }
  else if ( *pStr1 == '\n' )
  {
   value.append("\n");
  }
  else 
  {
   value.append(" ");
  }
  pStr1++; 
  pStr2++;
  idx++;
 }
}


int main(void)
{
 int idx = 0;
 string returnMap1;
 string returnMap2;
 for( idx = 0; idx < case1N; idx++)
 {
  binaryChange(case1_secretValue[idx], returnMap1, case1N);
  binaryChange(case1_secretValue2[idx], returnMap2, case1N);
 } 
 string output;
 merge_map(returnMap1.c_str(), returnMap2.c_str(), output, returnMap1.size());
 LOG("result\n%s", output.c_str());

 returnMap1.clear();
 returnMap2.clear();
 for ( idx = 0; idx < case2N; idx++ )
 {
  binaryChange(case2_secretValue[idx], returnMap1, case2N);
  binaryChange(case2_secretValue2[idx], returnMap2, case2N);
 }
 output.clear();
 merge_map(returnMap1.c_str(), returnMap2.c_str(), output, returnMap1.size());
 LOG("result\n%s", output.c_str());

 return 0;
}

추가로 읽으면 좋을 것