[프로그래머스] 단체 사진 찍기 - Java

문제 설명

 

 

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

 

접근 방법

해당 문제는 정해진 8명의 캐릭터에 대해 줄을 세우는데, 어떤 조건을 충족시키면서 줄을 세울 수 있는 경우의 수를 요구하고있다.

 

우선 단순히 8명을 줄을 세운다면 전체 경우의 수는 40320(8!)이다. 즉, 특정 조건을 충족시키는 경우의 수는 이 보다 작을 것이다. 일차적으로 백트래킹을 이용해 주어진 캐릭터 8명에 대해서 순열을 구하는 로직을 작성했다.

 

    private void lineUp(boolean[] visited, int depth) {
        if (depth == 8) {
            return;
        }

        for (int i = 0; i < 8; i++) {
            if (!visited[i]) {
                visited[i] = true;
                depth++;

                lineUp(visited, depth);

                depth--;
                visited[i] = false;
            }
        }
    }

 

depth가 8인 경우, 즉 8명에 대해 모두 정렬을 마친 경우 주어진 조건이 일치하는지를 검증하면 된다. 이때 나 같은 경우는 조건 검증을 위해 "조건"과 관련된 커스텀 객체를 만들어주었던게 도움이 되었다.

 

    static class Condition {

        String subject;
        String object;
        String operation;
        int gap;

        public Condition(String data) {
            this.subject = String.valueOf(data.charAt(0));
            this.object = String.valueOf(data.charAt(2));
            this.operation = String.valueOf(data.charAt(3));
            this.gap = data.charAt(4) - 47;
        }

        public boolean validate(List<String> position) {
            int subjectIndex = position.indexOf(subject);
            int objectIndex = position.indexOf(object);
            if (operation.equals(">")) {
                return Math.abs(subjectIndex - objectIndex) > gap;
            }
            else if (operation.equals("=")) {
                return Math.abs(subjectIndex - objectIndex) == gap;
            }
            else {
                return Math.abs(subjectIndex - objectIndex) < gap;
            }
        }
    }

 

위 객체를 보면 처음 생성될 때 조건 문자열을 파싱하여 상태 값으로 지니고 있는다. 이후 검증 메서드가 호출되면 앞서 주어진 조건이 일치하는지를 검증한 결과를 반환해준다.

 

앞서 단순히 8명에 대해서 정렬하는 로직에서 정렬을 모두 마친 경우에 해당 조건 검증 메서드를 호출하면서 true일 경우 count하여 결과값을 도출할 수 있었다.

 

 

전체 소스 코드

import java.util.ArrayList;
import java.util.List;

class Solution {

    String[] characters = {"A", "C", "F", "J", "M", "N", "R", "T"};
    List<Condition> conditions = new ArrayList<>();
    List<String> characterList = new ArrayList<>();

    int result = 0;

    static class Condition {

        String subject;
        String object;
        String operation;
        int gap;

        public Condition(String data) {
            this.subject = String.valueOf(data.charAt(0));
            this.object = String.valueOf(data.charAt(2));
            this.operation = String.valueOf(data.charAt(3));
            this.gap = data.charAt(4) - 47;
        }

        public boolean validate(List<String> position) {
            int subjectIndex = position.indexOf(subject);
            int objectIndex = position.indexOf(object);
            if (operation.equals(">")) {
                return Math.abs(subjectIndex - objectIndex) > gap;
            }
            else if (operation.equals("=")) {
                return Math.abs(subjectIndex - objectIndex) == gap;
            }
            else {
                return Math.abs(subjectIndex - objectIndex) < gap;
            }
        }
    }

    public int solution(int n, String[] data) {
        for (String d : data) {
            conditions.add(new Condition(d));
        }

        boolean[] visited = new boolean[8];

        lineUp(visited, 0);

        return result;
    }

    private void lineUp(boolean[] visited, int depth) {
        if (depth == 8) {
            boolean flag = true;
            for (Condition condition : conditions) {
                if (!condition.validate(characterList)) {
                    flag = false;
                    return;
                }
            }
            if (flag) result++;

            return;
        }

        for (int i = 0; i < 8; i++) {
            if (!visited[i]) {
                visited[i] = true;
                depth++;
                characterList.add(characters[i]);

                lineUp(visited, depth);

                characterList.remove(characters[i]);
                depth--;
                visited[i] = false;
            }
        }
    }
}

 

 

참고자료

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