[카카오] 단체사진찍기 (java)

문제링크

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

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 브루트포스 순열

카카오 프렌즈 캐릭터 8명이 원하는 순서대로 사진을 찍을 수 있는 횟수를 구하는 문제이다. 캐릭터가 순서대로 서는 경우의수는 8!이며 최대로 들어올 수 있는 조건이 100개이다. 따라서 최악의 경우 $O(8!*100)$의 시간이 걸리게 된다. 따라서, 브루트포스로 문제를 해결할 수 있다.

 

순열로 문제를 해결해주었다. 이름에 대한 정보를 미리 배열에 저장해두고 Map을 사용해서 이름과 그 캐릭터의 위치를 정수로 넣어주었다. 그리고, 조건들을 확인하여 넣을 수 있는지 체크하고 넣을 수 있다면 넣어주면 된다.

구현코드

package pgm_1835;

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int solution(int n, String[] data) {
        int answer = 0;

        char[] names = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
        int[] permutation = {1,2,3,4,5,6,7,8};
        Map<Character,Integer> position = new HashMap<>();
        do {
            switchPosition(names, permutation, position);
            if(checkCondition(n, data, position))
                answer++;
        }while (nextPermutation(permutation,8));

        return answer;
    }

    private boolean checkCondition(int n, String[] data, Map<Character, Integer> position) {
        int i;
        for(i = 0; i < n; i++){
            Integer positionA = position.get(data[i].charAt(0));
            Integer positionB = position.get(data[i].charAt(2));
            int dis = Math.abs(positionA - positionB);
            if(data[i].charAt(3) == '=' && dis-1 != data[i].charAt(4)-'0'){
                break;
            }
            else if(data[i].charAt(3) == '<' && dis-1 > data[i].charAt(4)-'0'-1){
                break;
            }
            else if(data[i].charAt(3) == '>' && dis-1 < data[i].charAt(4)-'0'+1){
                break;
            }
        }
        if(i != n){
            return false;
        }
        return true;
    }

    private void switchPosition(char[] names, int[] permutation, Map<Character, Integer> position) {
        for(int i = 0; i < names.length; i++){
            position.put(names[i], permutation[i]);
        }
    }

    private boolean nextPermutation(int[] numbers, int n){
        int prevIndex;
        int nextIndex = n-1;
        int changeIndex = -1;

        for(int i = n-2; i >= 0; i--){
            prevIndex = nextIndex;
            nextIndex = i;

            if(numbers[nextIndex] < numbers[prevIndex]){
                changeIndex = nextIndex;
                break;
            }
        }

        if(changeIndex == -1)
            return false;

        for(int i = n-1; i > changeIndex; i--){
            if(numbers[i] > numbers[changeIndex]){
                int temp = numbers[i];
                numbers[i] = numbers[changeIndex];
                numbers[changeIndex] = temp;
                break;
            }
        }
        while(++changeIndex < --n){
            int temp = numbers[n];
            numbers[n] = numbers[changeIndex];
            numbers[changeIndex] = temp;
        }
        return true;
    }
}

 

시간복잡도

조건의 개수가 n 캐릭터가 c개 있다면 시간 복잡도는 $O( n*C!)$이 된다.

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)