LV2 [KAKAO] 단체 사진 찍기

---

문제

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

프로그래머스

풀이

어떻게 풀면 좋을까 생각하다 완탐 (순열) 밖에 없는거 같아서 그렇게 풀었다.

 

우선 8명이 설 수 있는 모든 경우를 모두 구한다. 파이썬은 itertools 로 순열을 굉장히 쉽게 구할 수 있는 반면, 자바는 없다고 하더라. 그래서 perm이라는 순열을 만드는 함수를 만들었고 특정 순열이 한개 만들어지면 (8명이 모두 자리를 잡고 서있다면) 조건에 부합하는지 검사하도록 했다.

 

해당 배치가 조건에 맞지 않는다면 바로 return하면 되고, 모든 조건에 부합한다면 답을 하나 늘려주면 된다.

 

난 문제에서 "간격" 개념이 초반에 조금 헷갈렸는데 

간격 => 프렌즈의 수

M~C > 2

M과 C 사이에는 최소 3명이 있어야한다.

M A B D C 가능


M~C < 2

M과 C 사이에는 2명보다 적어야 한다.

M A C 가능

이런식으로 적으니 코드 작성하기가 수월했다.

 

코드

import java.util.*;

class Solution {

    public boolean [] visited = new boolean[8];
    public String [] friends = new String[]{"A", "C", "F", "J", "M", "N", "R", "T"};
    public int answer = 0;

    public void isPossible(String[] conditions, String res){
        for(String condition : conditions){
            boolean flag = false;
            int distance = Math.abs(res.indexOf(condition.charAt(0)) - res.indexOf(condition.charAt(2)));
            String operator = condition.substring(3,4);
            int num = Integer.parseInt(condition.substring(4));
            switch(operator){

                case "=" :
                    if(distance == num+1) flag = true;
                    break;

                case "<" :
                    if(distance <= num ) flag = true;
                    break;

                case ">" : 
                    if(distance >= num+2) flag = true;
                    break;
            }
            if(!flag) {
                return;
            }
        }
        answer += 1;
    }

    public void perm(int cnt, String res, String[] data){
        if(cnt == 8){
            isPossible(data, res);
            return;
        }

        for(int i=0; i<8; i++){
            if(visited[i]) continue;
            visited[i] = true;
            perm(cnt+1, res + friends[i], data);
            visited[i] = false;
        }
    }

    public int solution(int n, String[] data) {
        perm(0, "", data);
        return answer;
    }
}

 

후기

 

예전에 이 문제를 봤을때 감도 못잡았던 거 같은데.. 지금은 금방 풀었다. 하다보니 조금 늘긴하나보다, 뿌듯하다 나름.