2018 카카오 코딩테스트 - 비밀지도

문제 출처 : https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

카카오 신입 공채 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을 만족한다.

 

출력 형식

---

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

 

입출력 예제

---

매개변수값

n	5
arr1	[9, 20, 28, 18, 11]
arr2	[30, 1, 21, 17, 28]
출력	["#####","# # #", "### #", "# ##", "#####"]

매개변수값

n	6
arr1	[46, 33, 33 ,22, 31, 50]
arr2	[27 ,56, 19, 14, 14, 10]
출력	["######", "### #", "## ##", " #### ", " #####", "### # "]

 

 

생각해보기

---

문제를 보았을때 

1. 입력받은 배열의 정수를 이진수로 변환한다.
2. 변환된 이진수간 OR연산을 한다.
3. 결과를 출력한다.

이과정을 거쳐서 해결하면 되겠다고 생각했습니다.

 

이것이 첫번째로 구상한 내용입니다.

직관적으로 원래의 계획을 그대로 옮긴것입니다. 

중복되는 연산이 너무 많은것 같아 연산을 줄여보려 했습니다.

 

그래서 나온것이 이결과 입니다. 

이진수로 변환한 것을 따로 배열에 저장하지않고 바로바로 OR연산을 해주어 결과를 도출해줍니다.

https://boycoding.tistory.com/163

C++ 03.07 - 비트 단위 연산자 (Bitwise operators)

비트 단위연산에 대해 알아보니 9와 30을 이진수로 변환하지않고, 바로 OR연산해주어도 비트단위로 OR를 해주어 원하는 결과를 얻을수 있게 해주었습니다.

이를 통해, 2*n번이던 이진수 변환과정을 한번으로 줄여주었습니다. 

 

이진수 변환을 하지않고 비트연산만으로 해결하려 해보았는데, 이진수 변환보다 더많은 과정이 필요하여 이진수 변환을 한번은 사용하는 형태로 했습니다.

 

 

이제 이를 코드로 옮겨야 합니다.

 

 

코딩

---

문제 입력형식에 arr1, arr2는 길이 n인 정수 배열로 주어진다고 했으므로, 메인에서 n과 arr1, arr2를 입력받고

문제를 해결하는 함수의 매개변수로 n과 arr1, arr2를 주는 방식으로 코딩해보겠습니다.

입력을 받을때 arr1과 arr2는 n크기만큼 선언되어야하므로, 동적할당을 해주어야 합니다.

https://boycoding.tistory.com/205

C++ 07.13 - 동적으로 배열 할당하기 (Dynamically allocating arrays)

동적할당을 사용하였으면, 메모리를 해제해주는것을 잊지않고 해주어야합니다.

동적할당을 사용하여 arr1, arr2를 받아주고 n도 받아줍니다.

계획했던대로, arr1과 arr2에서 숫자를 가져와 OR연산해줍니다.

OR연산의 결과를 2진수로 변환하여야합니다.

저는 이런식으로 코딩하였습니다. 

if(k % 2) { ... }

else { ... }

로 하여도 됩니다. 

https://stackoverflow.com/questions/5189072/c-bool-question

c++ bool question

c++에서는 0을 false로 처리하고, !false를 true로 처리합니다. 즉 0이 아닌 아무 숫자나 와도 true로 처리하게 됩니다.

하지만 조건문은 확실히 해두는게 좋아서, 굳이 안에 확실하게 적어두었습니다.

reverse를 사용하였습니다. 뒤집어 주지않으면, 생각했던 결과와 정반대 결과가 나오므로 잊지않고 꼭해주어야 합니다.

 

 

호기심

---

배열입력은 cin으로 한번에 받을수는 없는걸까?

 - 입력예제에 있는 방식대로 입력하여 cin으로 받아지는지 해보았는데 안된다.

 

코드

---

https://github.com/psg2021/KAKAOtest/blob/master/2018_1st/2018_1st/secretmap.cpp

psg2021/KAKAOtest

 

후기

---

다른 블로그글을 보면 핵심만 짧게 적혀있어서 이렇게 주절주절써놓은 블로그는 왜없을까하고 써봤는데, 생각을 다 풀어쓴다는것이 보통힘든일이 아니란걸 알게되었다.

그리고 다른 블로그글은 예쁘게 잘정리되어있는데 내껀 왜 이모양인지..

블로그 쓰는것이 어색하지만 글을 쓴다는게 정말 재미있는 일인것 같다.

첫 글 끝!