어제 풀다가 갑자기 일이 생겨서 마무리를 못 지은 문제가 있어 오늘 마무리를 지어보았다 ~
프로그래머스에서 푼 레벨2의 2017 카카오코드 본선 문제 단체사진 찍기 이다 ! 최근 어느 기업인가의 코테에서 비슷한 유형의 문제가 나왔었는데, 그 때는 요 문제를 떠올리며 풀었고, 오늘은 그 문제를 떠올리며 풀었다 ㅋ ㅋ ㅋ ㅋ
문제 설명
가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다. 사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다. 각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.
입력 형식
입력은 조건의 개수를 나타내는 정수 n과 n개의 원소로 구성된 문자열 배열 data로 주어진다. data의 원소는 각 프렌즈가 원하는 조건이 N~F=0과 같은 형태의 문자열로 구성되어 있다. 제한조건은 아래와 같다.
- 1 <= n <= 100
- data의 원소는 다섯 글자로 구성된 문자열이다. 각 원소의 조건은 다음과 같다.
- 첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다. {A, C, F, J, M, N, R, T} 각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다. 첫 번째 글자는 조건을 제시한 프렌즈, 세 번째 글자는 상대방이다. 첫 번째 글자와 세 번째 글자는 항상 다르다.
- 두 번째 글자는 항상 ~이다.
- 네 번째 글자는 다음 3개 중 하나이다. {=, <, >} 각각 같음, 미만, 초과를 의미한다.
- 다섯 번째 글자는 0 이상 6 이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.
출력 형식
모든 조건을 만족하는 경우의 수를 리턴한다.
입출력 예
| n | data | answer |
|---|---|---|
| 2 | ["N~F=0", "R~T>2"] | 3648 |
| 2 | ["M~C<2", "C~M>1"] | 0 |
풀이 방법
풀이 방법은 간단하다 ! 왜냐하면 나는 완전 탐색으로 풀었기 때문이댜 ~
우선 8명의 캐릭터를 한 줄로 세우는 모든 경우의 수를 구한다. 이건 순열을 통해서 구할 수 있다. 나는 각 경우에서 각 캐릭터의 알파벳을 통해서 서있는 위치를 O(1)로 가져올 수 있도록 map에 <캐릭터 알파벳, 위치> 형태로 저장을 해주었다. 이후에 조건을 판별하기 위해서 각 경우의 수에 있어서 캐릭터의 위치를 빠르게 가져오는 것이 좋을 것 같았기 때문이다.
줄을 세울 수 있는 모든 경우의 수를 구했다면, 이제 각 경우의 수가 주어진 조건을 모두 만족하는지를 판단해야한다. 그러기 위해서 input으로 들어온 조건 데이터를 파싱하여 의미있는 요소를 뽑아내주었다. 두 캐릭터의 알파벳과 기호(>,<,=) 그리고 원하는 거리 이렇게 요소를 뽑아주었다. 그리고 두 캐릭터의 위치를 map에서 받아서 둘 사이의 간격을 구해주었다! ( 여기서 그냥 차를 구하면 안된다 바로 옆에 붙어있으면 문제에서는 0을 의미하는데 실제 계산은 1이니까 ! 대충 풀다가 이거 때문에 한 번 틀렸다 ㅋ ㅋ ㅋ ) 실제 거리와 원하는 거리 그리고 기호를 이용하여 조건을 만족하는지 판단하고 모든 조건을 만족하면 answer++을 해주고, 하나라도 틀리면 해주지 않는다.
아무리 봐도 로직에 문제가 없는데 제출하면 오답이 떠서 질문을 봤더니 전역 혹은 정적 변수들 정의를 solution 안에서 다시 해주어야 한다는 것이다 ;; 참나 ;; 다른 문제들은 한 번도 그런 적 없는데.. 그래서 정의 코드를 추가해주었더니 통과했다 ! 혹시 애를 먹고 계신 분이 계시다면 요 내용을 참고해보는 것도 좋을듯 싶다 ~
코드
import java.util.*;
class Solution {
public static char[] mems;
public static ArrayList<Map<Character, Integer>> target;
public static void permutation(boolean[] visited, char[] output, int size, int depth){
if(depth == size){
Map<Character, Integer> temp = new HashMap<>();
for(int i=0; i<depth; i++){
temp.put(output[i], i);
}
target.add(temp);
return;
}
for(int i=0; i<mems.length; i++){
if(!visited[i]){
output[depth] = mems[i];
visited[i] = true;
permutation(visited, output, size, depth+1);
visited[i] = false;
}
}
}
public static boolean isPossible(char op, int gap, int num){
if(op == '=') return gap == num;
else if(op == '<') return gap < num;
else return gap > num;
}
public int solution(int n, String[] data) {
int answer = 0;
target = new ArrayList<>();
mems = new char[]{'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
int size = mems.length;
permutation(new boolean[size], new char[size], size, 0);
char mem1, mem2, operand;
int gap, num;
boolean flag;
for(Map<Character, Integer> elem : target){
flag = true;
for(String info : data){
mem1 = info.charAt(0);
mem2 = info.charAt(2);
operand = info.charAt(3);
num = info.charAt(4)-'0';
gap = Math.abs(elem.get(mem1)-elem.get(mem2))-1;
if(!isPossible(operand, gap, num)){
flag = false;
break;
}
}
if(flag) answer++;
}
return answer;
}
}