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

Link | 1835번 문제 : 단체사진 찍기

📌 Analyze

줄 지을 수 있는 모든 경우의 수는 8명이기 때문에 8! = 40,320 번이다.

n은 최대 100이기 때문에 각 줄에 대해서 n번 반복하여 검증을 한다고 하면 4,032,000 번이다.

적은 경우의 수이기 때문에 각각의 줄에 대해 검증을 하면 된다.

📌 Solution

DFS를 통해 Stack에 줄을 세우면서 줄을 다 서면 검증을 한다.

탐색 방법은 다음과 같다.

public void lining() {
    if (line.size() == 8 && check()) count++;
    else for (int f = 0; f < 8; f++) {
        if (!line.contains(friends[f])) {
            line.push(friends[f]);
            lining();
            line.pop();
        }
    }
}

탐색을 하였을 때 stack의 크기가 8이면 검증을 한다.

8이 아니면 아직 줄을 다 선 것이 아니므로 아직 서지 않은 친구를 세운다.

검증은 다음과 같이 한다.

public boolean check() {
    for (String datum : data) {
        int diff = Math.abs(line.indexOf(datum.charAt(2)) - line.indexOf(datum.charAt(0))) - 1;
        char op = datum.charAt(3);
        int num = Character.getNumericValue(datum.charAt(4));
        if (op == '=' && diff != num || op == '>' && diff <= num || op == '<' && diff >= num) 
            return false;
    }
    return true;
}

검증을 하다가 오류를 발견하면 false를 반환한다.

모든 검증이 완료되면 true를 반환한다.

true를 반환하면 count 증가를 통해 줄 세운는 방법의 수를 센다.

📌 Code

GitHub Repository

import java.util.Stack;

class Solution {

    public final Stack<Character> line = new Stack<>();
    public final char[] friends = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    public String[] data;
    public int count = 0;

    public int solution(int n, String[] data) {
        this.data = data;
        lining();
        return count;
    }

    public void lining() {
        if (line.size() == 8 && check()) count++;
        else for (int f = 0; f < 8; f++) {
            if (!line.contains(friends[f])) {
                line.push(friends[f]);
                lining();
                line.pop();
            }
        }
    }

    public boolean check() {
        int diff, op, num;
        for (String datum : data) {
            diff = Math.abs(line.indexOf(datum.charAt(2)) - line.indexOf(datum.charAt(0))) - 1;
            op = datum.charAt(3);
            num = Character.getNumericValue(datum.charAt(4));
            if (op == '=' && diff != num || op == '>' && diff <= num || op == '<' && diff >= num)
                return false;
        }
        return true;
    }
}