프로그래머스 Lv.2) 단체사진 찍기

단체사진 찍기

코딩테스트 연습 - 단체사진 찍기

풀이

우여곡절이 많았던 문제다. 시간초과가 뜰까봐 문제를 보자마자 생각난 완전탐색을 미뤄두고 여러가지 시도를 했다. 하지만, 이마저도 다 시간초과가 떠서 어떻게 풀라는 건지 막막했다. 문제를 푼 지 오랜시간이 지나고 도저히 모르겠어서 검색을 했다. 맨 위에 나온 블로그를 켜자마자 첫 줄에 완전탐색으로 풀었다는 글을 보자마자 블로그를 껐다. 그리고 한숨을 쉬었다.. 완탐이 되는 문제라니.. 수학적 공식을 활용하려고 발버둥 쳤던 내 자신을 반성했다.. 아무튼 완탐이 된다고 해서 나름의 로직을 만들어 풀어봤다.

 

1. 순열을 이용해 단체사진을 찍는 위치를 만든다.

2. 완성된 순열을 조건에 부합하는지 검사하는 메소드에 넘겨 부합하면 카운트를 증가시켜줬다.

 

클래스를 따로 만들기 귀찮아서 특이하게 HashMap을 통해 순열을 구해봤다. List를 통해 만들면 값을 다시한번 탐색해야하기 때문에 List는 포기했고, Array를 통해 구현해도 마찬가지라 포기했다. 이 문제에서 중요한 것은 어떤 카카오프렌즈(문자)가 몇번째 인덱스(숫자)에 있는지다. 그래서 HashMap을 통해 관리해주어 조건을 검사했다.

 

코드

import java.util.HashMap;

public class GroupPhoto_1835 {
    final static char[] friends = {'A','C','F','J','M','N','R','T'};
    final static int PEOPLE_NUM = 8;
    static int answer;

    public static void main(String[] args) {
        int n =2;
        String[] data = {"N~F=0", "R~T>2"};
        System.out.println(solution(n,data));
    }

    private static int solution(int n, String[] data) {
        answer = 0;
        makeAllCase(0,new int[PEOPLE_NUM], data, new HashMap<Character,Integer>());

        return answer;
    }
    private static void makeAllCase(int idx, int[] visit, String[] data, HashMap<Character,Integer> orderMap) {
        if(idx == PEOPLE_NUM) {  // 작업 완료
            if(isOkay(orderMap, data)) {
                answer++;
            }
            return;
        }
        for(int i=0; i<PEOPLE_NUM; i++) {
            if(visit[i] ==0) {
                visit[i] =1;
                orderMap.put(friends[i], idx);
                makeAllCase(idx+1, visit, data, orderMap);
                visit[i] =0;
                orderMap.remove(friends[i]);
            }
        }
    }
    private static boolean isOkay(HashMap<Character,Integer> orderMap, String[] data) {
        boolean result = true;
        for(String str : data) {
            char person1 = str.charAt(0);
            char person2 = str.charAt(2);
            char sign = str.charAt(3);
            int dist = str.charAt(4)-47;    // 숫자 0 ~> -48 => 조건에 부합하려면 +1 따라서, -47

            int targetDist = Math.abs(orderMap.get(person1) - orderMap.get(person2));
            if(sign == '=') {
                if(targetDist != dist) {
                    result = false;
                    break;
                }
            } else if(sign == '>') {
                if(targetDist <= dist) {
                    result = false;
                    break;
                }
            } else {
                if(targetDist >= dist) {
                    result = false;
                    break;
                }
            }
        }
        return result;
    }
}