단체사진 찍기

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

프로그래머스

Level 2

 

주어진 조건에 만족하는 자리배치의 모든 경우의 총합을 구하는 문제

 

 

흔히 중학교 수학과정에서 배우는 한 줄 세우기 순열로 자리 배치의 경우의 수를 구한 뒤

조건에서 제시하는 특정 거리만큼 + 부등호 조건에 만족하는 지 확인해야한다. 

 

개인적으로는 최악의 경우 조건이 모든 경우의 수 즉 8! 를 구해야하기 때문에 

8! 모든 경우의 수를 구해 놓고 그 상태에서 조건을 돌려도 최대 4032000 (8! * 100(최대 조건의 갯수)) 이기 때문에

효율성에서 크게 문제가 되지 않을 거라고 생각했다.

뭐 8명이 넘어가면 문제가 될 수 도?...

 

그래서 나의 풀이는 다음과 같다.

1. 모든 자리배치를 구하는 함수를 구현한다.

2. 8명의 자리배치가 완료될 경우 모든 조건을 확인한다.

3. 단 하나의 조건이라도 만족하지 못하면 결과값에 포함시키지 않는다.

 

import java.util.*;

public class Solution { //단체사진 찍기
    static int answer;
    public int solution(int n, String[] data) {
        answer = 0;
        String currentLine = "";
        char[] friends = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
        ArrayList<Character> line = new ArrayList<Character>();
        for(char friend : friends) line.add(friend); //배열에 사용될 알파벳들을 리스트에 복사
        factorial(currentLine, line, data);
        return answer;
    }

    public void factorial(String currentLine, ArrayList<Character> line, String[] data){
        if(line.isEmpty()){ //자리 배치가 완료된 상황
            answer = isValid(data, currentLine) ? answer+1 : answer; //현재 자리배치가 모든 조건을 만족하는지 검사 후 결과값 최신화
        }else { //자리 배치가 완료되지 않았을 경우
            for(char alphabet : line){ //자리 배치 진행 n! 한 줄 세우기
                ArrayList<Character> nextLine = new ArrayList<>(line);
                nextLine.remove(Character.valueOf(alphabet));
                String nextCurrentLine = currentLine+alphabet;
                factorial(nextCurrentLine, nextLine, data);
            }
        }
    }

    public boolean isValid(String[] data, String line) {
        for(String condition : data){ //모든 조건 검사
            int lineGap = Math.abs(line.indexOf(condition.charAt(0)) - line.indexOf(condition.charAt(2)))-1; //현재 두 사람의 자리배치 차이
            int paramGap = condition.charAt(4) - '0'; //조건에서 요구하는 두 사람의 자리배치 차이
            char sign = condition.charAt(3); //부등호 추출

            //조건을 하나라도 만족하지 못하면 거짓
            if(sign == '='){
                if(!(lineGap == paramGap)) return false;
            }else if(sign == '>'){
                if(!(lineGap > paramGap)) return false;
            }else if(sign == '<'){
                if(!(lineGap < paramGap)) return false;
            }
        }
        return true; //모든 조건을 만족하면 참
    }
}