★[201027] 단체사진 찍기 - 2017 카카오코드(level2)

0. 문제 유형 : 완전 탐색(순열을 통해 모든 case 확인)

1. 문제 이해

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

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

주어진 조건에 따라 배치할 수 있는 경우의 수를 리턴하기

(1) 제한 조건

- n : 입력 조건의 개수 (1 <= n <= 100)

- 배치 대상 : {A, C, F, J, M, N, R, T} (총 8개)

 

(2) data : 만족해야될 조건

- 1, 3번째 글자 : 배치 대상1, 배치 대상2

- 2번째 글자 : ~

- 4번째 글자 : {=, <, >} 중 하나

- 5번째 글자 : 0이상 6이하의 정수 문자형

  ▷ 배치 대상1과 배치 대상2 사이의 간격이 (5번째 글자) 와 같거나/크거나/작다.

 

 

2. 전략

(1) 순열을 통해 모든 경우의 수 고려

- data 배열에 맞게 경우를 생각하기는 어렵다. 순열을 통해 각 경우의 수를 생성

- 순열 함수 perm 구현

public void perm(String[] array, int n, int k, int depth, String[] data)
- array : 순열의 대상이 되는 배열 → {A, C, F, J, M, N, R, T}
- n, k : nPk
- depth : 배치 대상이 되는 자릿수 _ 1번째 자리부터 순서대로 정해줄 것
- data : (2)의 data 조건 함수를 호출하기 위한 parameter
depth가 k가 되기 전까지 swap(따로 함수 구현)을 통해 각 자릿수를 정해주고, k가 되었을 때 String 형태로 1가지 case를 완성할 수 있다.

 

(2) 순열의 각 case별로 조건(data)에 맞는지 확인- data 확인 함수 checkData 구현

public boolean checkData(String s, String[] data)
<parameter>
- s : (1)을 통해 생성된 순열의 1가지 case
- data : 확인해야될 조건 배열
<local variable>
- result : true/false _ return할 값
- cond : 확인할 조건 String ( ex> "N~F=0" )
- first, second : cond의 1번째, 3번째 글자(substring 이용)
- index1, index2 : s에서 first, second가 위치한 index( indexOf 이용)
- gap : index1과 index2의 차이 (Math.abs 이용)
- operator : cond의 4번째 글자 ( =, <, > )
- num : cond의 5번째 글자 (int로 사용해야 되므로 Integer.parseInt를 통해 형변환)
<algorithm>
- data 배열의 각 string에 대하여 조건에 맞는지 확인(반복문)
- 모든 조건에 대하여 =, >, <에 따라 확인 후 맞으면 true, 하나라도 틀리면 false return

 

 

3. 참고사항

(1) 전역변수 초기화

- answer : perm 함수를 호출하여 나온 최종 결과를 담을 전역 변수

- 전역변수를 solution 함수 내에서도 0으로 초기화해주지 않으면 최종 결과에서 오류가 난다.

★ 전역변수의 초기화를 함수 내에서 진행해줘야 한다!!

 

(2) 순열 코드

- swap 대신 visited 배열도 쓸 수 있음

- 순열/조합 정리해둔 알고리즘 글

esw-csmoon.tistory.com/entry/%EC%88%9C%EC%97%B4%EC%A1%B0%ED%95%A9-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89?category=1125729

순열/조합 (완전탐색)

 

 

4. 코드

class Solution {
    static int answer = 0;
    public int solution(int n, String[] data) {
        answer = 0;
        String[] array = new String[]{"A", "C", "F", "J", "M", "N", "R", "T"};
        perm(array, 8, 8, 0, data);
        return answer;
    }
    
    public void perm(String[] array, int n, int k, int depth, String[] data){
        if(depth == k) {
            String s = "";
            for(int i = 0; i < k; i++){
                s += array[i];
            }
            if(checkData(s, data) == true){
                answer++;
            }
        }
        else{
            for(int i = depth; i < n; i++){
                swap(array, depth, i);
                perm(array, n, k, depth+1, data);
                swap(array, depth, i);
            }
        }
    }
    public void swap(String[] array, int a, int b){
        String temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
    public boolean checkData(String s, String[] data){
        int size = data.length;
        boolean result = true;
        for(int i = 0; i < size; i++){
            String cond = data[i];
            String first = cond.substring(0, 1); String second = cond.substring(2, 3);
            int index1 = s.indexOf(first); int index2 = s.indexOf(second);
            int gap = Math.abs(index1-index2)-1;
            String operator = cond.substring(3, 4);
            int num = Integer.parseInt(cond.substring(4, 5));
            if(operator.equals("=") && gap == num) continue;
            else if(operator.equals(">") && gap > num) continue;
            else if(operator.equals("<") && gap < num)   continue;
            else{
                result = false;
                break;
            }
        }
        return result;
    }
}