[2021 KAKAO Blind Recruitment] Q6. 카드 짝 맞추기 (C++, Python, Java)

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/72415

 

예상 난이도

S2 - G5

 

알고리즘 분류

BFS, 시뮬레이션, 브루트 포스, DP

 

풀이

뭔가 삼성 A형스러운 문제입니다. 일단 카드의 종류가 최대 6가지이므로 제거할 종류의 순서를 정할 때 6!이고 각 카드는 종류별로 2장씩이므로 둘 중에서 어느 것을 먼저 제거할지 정해야하는데 일단은 이 부분을 무시하겠습니다.

 

다음으로 매번 현재 커서의 위치에서 카드까지 도달하기 위한 최단거리를 구해야 하는데, 코드 좀 치시는 분들은 2차원 배열에서 가중치가 1인 상황에서의 최단거리다 하면 바로 눈이 돌아가야합니다. 

 

대놓고 BFS입니다.

 

 

카드를 2번, 3번, 1번 순으로 지우겠다고 정했을 때 2L→2R →3L →3R →1L →1R 순으로 방문할 수도 있고 2R→2L →3L →3R →1L →1R 순으로 방문할 수도 있고, 2L→2R →3R →3L →1L →1R 순으로 방문할 수도 있고, ... 총 2³가지의 가능한 순서가 존재합니다.

 

카드 종류는 총 6가지이니 이를 감안해 시간복잡도를 계산해보면 6! * 2⁶개의 가능한 순서가 있고 각 순서에 대해 BFS를 총 12번, 각 BFS는 대충 O(16)이니 대략 O(10⁷) 정도가 됩니다. 이렇게 짜면 C++, Java는 통과되는데 Python에서는 시간 초과가 발생합니다.

 

Python에서는 여기다가 DP까지 끼얹어야 합니다. 저 식을 그대로 따라치기가 너무 귀찮으니 알아서 위의 그림을 참고해주세요. 직전에 L에서 R로 갔는지, R에서 L로 갔는지를 가지고 DP를 돌려서 시간복잡도를 떨궈야합니다. C++, Java에서는 DP를 안해도 되지만 그냥 둘 다 DP까지 넣은 코드로 두었습니다.

 

코드(C++)

dist 함수에서 &를 이용해 매번 board를 복사하는 대신 reference로 이용했습니다. 6!의 순서를 정하는건 next_permutation을 사용했습니다.

 

코드(Python)

itertools.permutations를 활용했습니다.

 

코드(Java)

Java에는 permutation 관련 라이브러리가 없기 때문에 직접 구현을 해야 합니다. 저는 백트래킹을 이용해 구현했습니다.

 

관련 강의

0x09강 - BFS

0x0C강 - 백트래킹

0x0D강 - 시뮬레이션

0x10강 - 다이나믹 프로그래밍