[ 프로그래머스 2017 카카오코드 본선] 단체사진 찍기 (java)

[ 프로그래머스 2017 카카오코드 본선 ] 단체사진 찍기 (자바)

순열 + 여러 조건들 고려하는 문제로

81명 제출자 중 78명이 통과

 

 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/1835

코딩테스트 연습 - 단체사진 찍기 | 프로그래머스

 

출처: 카카오 코드 패스티벌 본선, https://tech.kakao.com/2017/09/13/code-festival-round-2/

카카오 코드 페스티벌 본선 이야기

 

 

 

핵심 

1. 순열 만들기 
   8개 캐릭터 모두 앉을 수 있는 자리 고려하기. 8! 
   8! 까지 마구잡이로 만들어도 시간 초과 나지 않아 재귀 함수로 처리했다. 
   
   

2. 매 순열마다 조건이 맞는지 체크하기
   재귀 마지막에 만들어진 순열에 대해 모든 조건이 맞는지 체크했다.
   조건을 체크할 때, 하나라도 조건에 맞지 않으면 해당 재귀를 바로 종료.
   모든 data(조건)를 통과하면 count++ 
   
   

3. 캐릭터에 번호 매칭하기 이 부분이 다른 문제들과 달랐던 부분 모든 케릭터가 앉을 수 있는 모든 순열을 만들어야 한다. 그래서 각 캐릭터마다 앉을 수 있는 위치(0~7)를 설정했다.
   그런데, 캐릭터 문자에 매번 새로운 번호를 매칭하며 순열을 만들게 되면 hashMap을 계속 불러야 돼서 비효율적. 그래서, 8개 캐릭터에 0 ~ 7 번호를 부여하고, 그 번호를 이용해서 순열을 만른다. 

캐릭터	A	C	F	J	M	N	R	T
캐릭 번호	0	1	2	3	4	5	6	7
자리- 순열	0~7	0~7	0~7	0~7	0~7	0~7	0~7	0~7

 

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

 

 

코드

import java.util.*;
class Solution {
  public int solution(int n, String[] data) {
 
        // 캐릭터마다 새로운 번호를 매칭 
        hm = new HashMap<Character, Integer>();
        hm.put('A', 0);
        hm.put('C', 1);
        hm.put('F', 2);
        hm.put('J', 3);
        hm.put('M', 4);
        hm.put('N', 5);
        hm.put('R', 6);
        hm.put('T', 7);
        
        permute = new int[8];
        selected = new boolean[8];
        count = 0;
        
        // dfs ( pos, data ): pos번째 캐릭터 위치를 정하고, pos+1 번째 구하고.. 끝까지! 순열 구한다
        // 그리고 조건data를 통과하는지 확인 
        dfs(0,  data);
 
        return count;
    }
 
    static HashMap<Character, Integer> hm;
    static int[] permute ;
    static boolean[] selected ;
    static int count;
    
    // permute에서 pos번째 케릭터의 위치를 고른다.  
    static void dfs(int pos, String[] data) {
        
        if(pos == 8) { // 하나의 permute이 완성 
            char compare;
            int c1, c2, digit;
            for(int i = 0 ; i < data.length ; i++) {
                c1 = permute[hm.get(data[i].charAt(0))];
                c2 = permute[hm.get(data[i].charAt(2))];
                compare = data[i].charAt(3);
                digit = data[i].charAt(4)-'0';
                if(compare == '>') {
                    if(Math.abs(c1-c2) -1 <= digit) 
                        return;
                }else if(compare == '<') {
                    if(Math.abs(c1-c2) -1  >= digit)
                        return;
                }else {
                    if(Math.abs(c1-c2) - 1 != digit)
                        return;
                }
            }
            count++;
            return;
        }
        
        // pos번째 캐릭터가 위치 가능한 모든 i 
        for(int i = 0 ; i < 8 ; i++) { 
            if(!selected[i]) {
                selected[i] = true;
                permute[pos] = i;
                dfs(pos+1, data);
                selected[i] = false;
            }
        }
    }
}