문제 설명

가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다.

그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다.

네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불에 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어지기를 원했다.

사진을 찍고 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다.

각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.

입력 형식

입력은 조건의 개수를 나타내는 정수 n과 n개의 원소로 구성된 문자열 배열 data로 주어진다. data의 원소는 각 프렌즈가 원하는 조건이 N~F=0과 같은 형태의 문자열로 구성되어 있다. 제한조건은 아래와 같다.

1 <= n <= 100
data의 원소는 다섯 글자로 구성된 문자열이다. 각 원소의 조건은 다음과 같다.

첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다. {A, C, F, J, M, N, R, T} 각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다. 첫 번째 글자는 조건을 제시한 프렌즈, 세 번째 글자는 상대방이다. 첫 번째 글자와 세 번째 글자는 항상 다르다.

두 번째 글자는 항상 ~이다.
네 번째 글자는 다음 3개 중 하나이다. {=, <, >} 각각 같음, 미만, 초과를 의미한다.

다섯 번째 글자는 0 이상 6 이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.

예제 입출력

Solution

2017 카카오코드 본선 1번 문제로써 최대 8! (약 40000)번의 계산 횟수를 갖는 완전 탐색 문제이다. 다시말해 개의 for문으로 구현을 해도 문제가 없다.

문제 해결의 접근법은 우선 모든 경우의 수를 구한 뒤 각 경우가 주어진 조건을 만족하는지 여부를 체크하는 완전 탐색이다.

구현에는 재귀 호출을 이용하였고, 각 호출은 8개의 자리 중 호출 번째 위치에 프렌즈를 선택하여 위치시키는 경우이다.

ex) 2번째 재귀 호출에서는 2번째 위치에 남은 7명의 프렌즈 중 하나를 선택하여 위치시킨다.

각 재귀 호출에서는 현재 정렬된 프렌즈의 리스트, 남아있는 프렌즈의 리스트 를 이용한다. 남아있는 프렌즈의 리스트에서 각 프렌즈들을 현재 호출번째 자리에 위치시키는 모든 경우의 수를 찾기 위해 남아있는 프렌즈 수 만큼 for 루프를 돈다.

최종적으로 현재 정렬된 프렌즈의 리스트 크기가 모든 프렌즈의 수(8)이 되었을 때 하나의 경우의 수가 완성되었음을 의미하므로 주어진 조건을 체크하여 만족한다면 Count + 1을 해준다.

Code

solution에서 언급한 바와 같이 재귀 호출을 이용하여 각 호출시 마다 남아있는 프렌즈의 리스트(friends)에서 하나를 뽑아 현재 정렬된 프렌즈 리스트(permut)에 삽입하고 다음 재귀로 넘겨주었다.

주의해서 볼 점은 재귀호출 이후 permut에 삽입했던 friends의 값을 삭제하고 다시 friends의 tail에 삽입한다는 점이다.

for 루프는 각 루프때 마다 서로 다른 friends의 요소를 permut에 삽입을 해주어야 한다.

위와 같이 재귀호출이 끝나면 또 다른 friends를 permut에 위치시키는 경우를 구하기 위함이다.

단순히 경우의 수를 생각한다면 위 코드를 이해하기가 크게 어렵지 않을 것이다.

몇줄 평

재귀를 활용한 문제해결이 조금씩 더 익숙해져 가는것 같아 뿌듯

각 분기되는 경우가 for 루프로 구현됨

구현시 friends 리스트에서 permut에 넣고 재귀 호출 이후 friends에서 제거하고 permut에 맨 끝에 삽입하는 “스택처럼 활용” 하는걸 생각하는데 시간이 오래 소요됨.

참고 및 출처