[Swift] 2021 KAKAO BLIND RECRUITMENT 카드 짝 맞추기

 

Problem

 

코딩테스트 연습 - 카드 짝 맞추기

---

Solution

 

모든 카드를 뒤집는 최소 조작횟수를 찾아야 하는 문제입니다.

 

(BFS를 구현하는 법과 순열구하는 법을 알아야 구현하기 수월하실겁니다.)

 

1. 카드를 뒤집는 순서를 정하기(순열 구하는 방법 알기)

 

만약 1,2,3 카드가  있다면 1 - 2 - 3, 1 - 3 - 2, 2 - 1 - 3... 등으로 뒤집을 수 있습니다.

 

순열을 구하는 방법은 재귀 함수를 사용해 해당 하나씩 숫자를 지워나가면서 depth에 저장해줍니다.

 

하지만 카드는 각 각 2장씩 있으므로 똑같은 숫자 카드라도 먼저 뒤집을 카드 순서도 정해줘야 합니다.

 

(startCardGame을 참조해주세요!)

 

2. BFS로 모든 이동에 대한 조작 횟수 구하기

 

왼쪽,오른쪽,아래쪽,위쪽으로 이동하는 것과 ctrl을 누르고 왼쪽,오른쪽,아래쪽,위쪽로 이동하는 경우가 있으므로 총 8가지로

 

이동했을 때 조작 횟수를 구해야 합니다.

 

이 때 BFS로 이동에 대한 값을 queue에 넣어두고 queue의 가장 첫번째 값을 삭제해 나가면서 구할 수 있습니다.

 

또한  4x4 Bool을 담을 배열을 만들어서 해당 위치를 방문했는지 안했는지 확인해줍니다.

 

(moveCurrentToGoal과 moveBFS를 참고해주세요!)

 

3. 모든 경우의 수에서 가장 작은 값 찾기

 

정답(answer) 변수를 정수에서 가장 큰 값인 Int.max로 놓습니다.

 

카드를 뒤집을 때마다 depth에 숫자들을 담아놓고 모든 숫자들이 뒤집어졌을때 즉, depth에 카드갯수/2만큼의 숫자가 채워졌을때

 

answer와 count를 비교해 더 작다면 answer를 count로 바꿔줍니다.

 

이렇게 모든 순열에 대한 조작횟수를 구하고 더 작은 값으로 answer를 바꿔줍니다.

 

마지막으로 answer에 어차피 카드들은 뒤집어질 때마다 +1이므로 카드의 갯수만큼을 더해주고 return 해줍니다.

 

(solution을 참고해주세요!)

---

Source Code

 

---

P.S

 

처음에 모든 카드를 뒤집는 경우의 수는 그냥 모든 카드를 탐색하고 뒤집은 카드를 지우고 또 남은 카드들을

 

똑같이 반복해주면 되지 않나? 라고 생각했는데 안됐다..

 

근데 실제로 쌓이는 숫자들을 보면 순열과 똑같이 쌓이긴하는데.. 왜 안될까?

 

BFS로 구현하기 전에는 현재 x,y와 목적지의 x,y를 차이를 비교해서 x먼저 맞추고 y를 맞출때와 y 먼저 맞추고 x를 맞출때를

 

구하면 되겠지했는데 아래와 같이 4에서 4로 이동하는 경우는 y를 한칸만 움직이고 x에서 ctrl로 움직이고

 

다시 y를 움직여야 되므로 모든 이동에 대한 조작 횟수를 구해줘야 했다.

 

 

 

이거 한 문제 푸는데 거의 일주일걸린거 같다....

 

고집도 많이 부리고 나만의 방식으로 풀거야라고 생각해서 오래 걸린거 같다...

 

다음부터는 내려놓고 배우는 마음으로 코드를 작성해야겠다.

---

Reference

 

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설