[JAVA] 프로그래머스 LEVEL2 단체 사진 찍기

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

프로그래머스

코딩테스트 연습 > 2017 카카오코드 본선 > 단체사진 찍기

 

난이도: LEVEL2

알고리즘 유형: 구현

 

풀이 설명 

1. 먼저 init() 메소드를 통해서 HashMap에 프렌즈들의 이름을 key 부여받는 번호를 숫자(value)로 저장해 주었다.

 

init() 메소드 

static HashMap<Character, Integer> map = new HashMap<>();

public static void init(){
    map.put('A', 0);
    map.put('C', 1);
    map.put('F', 2);
    map.put('J', 3);
    map.put('M', 4);
    map.put('N', 5);
    map.put('R', 6);
    map.put('T', 7);
}

 

2. init2() 메소드를 사용해서 Test 객체를 Test 배열에 저장하였다. 

 

Test 클래스 

이 Test 클래스는 data 배열에 들어있는 각각의 String을 분석해서 저장할 클래스이다. 

target1 , target2 프렌즈를 저장  
int num 간격을 저장하는 숫자이다. 네오와 프렌드의 간격이 0이라면 네오index - 프렌드index 차이는 1

그래서 1을 늘려서 저장했다. 

 check는 문자를 저장했다. >, <, =  3개 중에 하나 

저장의 편의를 위해 모든 인스턴스 변수를 받는 생성자를 만들었다.

 

제일 중요한 check 메소드이다. 

check 메소드는 2개의 인자를 받는다. 현재(내가 백트래킹 한 경우의 수 중에 하나) target1 index와 target2 index를 받는다.
distance: index의 간격을 구한다. Math.abs(target1_index - target2_index);

그리고 미리 저장해둔 check 문자를 통해서 각각의 경우에 맞게 boolean 타입을 반환한다. 

static class Test{
    int target1;
    int target2;
    int num; // +1 해서 기록 
    char check;
    public boolean check (int target1_index, int target2_index){
        int distance = Math.abs(target1_index - target2_index);
        if(check == '=' && distance == num) return true;
        else if(check == '>' && distance > num) return true;
        else if(check == '<' && distance < num) return true;
        return false;
    }
    // 생성자 
    public Test (int target1, int target2, int num, char check){
        this.target1 = target1;
        this.target2 = target2;
        this.num = num;
        this.check = check;
    }
}

init2() 메소드 

init2() 메소드는 Test 클래스에 형식에 맞게 charAt() 메소드를 통해서 구하고 

Test 생성자를 통해 객체를 만들고 condition 배열에 저장을 했다. 

static Test [] condition;

public static void init2(String [] data, int n){
    condition = new Test [n];
    int cnt = 0;
    for(String cur : data){
        char tar1 = cur.charAt(0);
        char tar2 = cur.charAt(2);
        char check = cur.charAt(3); // =  >  < 
        int num = cur.charAt(4) - '0' + 1;
        System.out.println(map.get(tar1) +  " " + map.get(tar2) + " " + check + " " + num);
        Test test = new Test(map.get(tar1), map.get(tar2), num, check);
        condition[cnt++] = test;
    }
}

 

3. 백트래킹을 사용해서 프렌즈들의 모든 경우의 수를 구한다. 

static boolean [] visited = new boolean [8];
static int [] memo = new int [8];

public static void backTracking(int depth){
    if(depth == 8){
        check();
        return;
    }
    for(int i = 0; i < 8; i++){
        if(visited[i]) continue;
        visited[i] = true;
        memo[depth] = i;
        backTracking(depth + 1);
        visited[i] = false;
    }
}

 

4. check 메소드를 통해서 각 경우의 수에서 해당 경우의 수가 모든 Test를 통과하는지 체크한다. 

다 통과하면 answer++

index 배열 같은 경우 각 프렌즈들은 고유의 번호가 있는데 프렌즈들의 현재 위치를 저장하기 위해서 만들었다.

매번 memo 배열을 돌면서 체크하면 *8의 시간복잡도가 추가적으로 들기 때문에 사용했다. 

public static void check(){
    int [] index = new int [8];
    for(int i = 0; i < 8; i++){
        index[memo[i]] = i;
    }
    for(Test test : condition){
        int tar1 = test.target1;
        int tar2 = test.target2;
        boolean flag = test.check(index[tar1], index[tar2]);
        if(!flag) return;
    }
    answer++;
}

 

C++ 초기 코드 

C++ 초기 코드를 보면 주석으로 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성하라는 주석이 있다. 

자바에는 없다.

이런 내용이 없으니까 계속 틀렸었다.

static 변수인 answer를 solution 메소드 안에서 초기화를 하니까 정답으로 통과되었다. 

왜 이런 메커니즘인지 이해하기가 좀 어렵다. 

 

정답 코드 

import java.util.*;
class Solution {
    static class Test{
        int target1;
        int target2;
        int num; // +1 해서 기록 
        char check;
        public boolean check (int target1_index, int target2_index){
            int distance = Math.abs(target1_index - target2_index);
            if(check == '=' && distance == num) return true;
            else if(check == '>' && distance > num) return true;
            else if(check == '<' && distance < num) return true;
            return false;
        }
        // 생성자 
        public Test (int target1, int target2, int num, char check){
            this.target1 = target1;
            this.target2 = target2;
            this.num = num;
            this.check = check;
        }
    }
    static HashMap<Character, Integer> map = new HashMap<>();
    static int answer = 0;
    static boolean [] visited = new boolean [8];
    static int [] memo = new int [8];
    static Test [] condition;
    public int solution(int n, String[] data) {
        answer = 0; 
        init();
        init2(data, n);
        backTracking(0);
        return answer;
    }
    public static void check(){
        int [] index = new int [8];
        for(int i = 0; i < 8; i++){
            index[memo[i]] = i;
        }
        for(Test test : condition){
            int tar1 = test.target1;
            int tar2 = test.target2;
            boolean flag = test.check(index[tar1], index[tar2]);
            if(!flag) return;
        }
        answer++;
    }
    public static void backTracking(int depth){
        if(depth == 8){
            check();
            return;
        }
        for(int i = 0; i < 8; i++){
            if(visited[i]) continue;
            visited[i] = true;
            memo[depth] = i;
            backTracking(depth + 1);
            visited[i] = false;
        }
    }
    public static void init2(String [] data, int n){
        condition = new Test [n];
        int cnt = 0;
        for(String cur : data){
            char tar1 = cur.charAt(0);
            char tar2 = cur.charAt(2);
            char check = cur.charAt(3); 
            int num = cur.charAt(4) - '0' + 1;
            Test test = new Test(map.get(tar1), map.get(tar2), num, check);
            condition[cnt++] = test;
        }
    }
    public static void init(){
        map.put('A', 0);
        map.put('C', 1);
        map.put('F', 2);
        map.put('J', 3);
        map.put('M', 4);
        map.put('N', 5);
        map.put('R', 6);
        map.put('T', 7);
    }
}