[Level 2] 단체사진 찍기 (Java)

[Level 2] 단체사진 찍기 (Java)

---

프로그래머스의 Level2 문제인 단체사진 찍기를 풀었다. 나같은 경우 해당 문제를 아래와 같이 풀었었다.

1. 알파벳 8자리에서 나올 수 있는 모든 경우의 수를 모두 구한다. (8! = 40320)
2. 구한 경우의 수들을 조건에 맞는지 확인 후 조건에 만족할 경우 +1 해준다.

import java.util.*;

public class 단체사진_찍기 {
    public static void main(String[] args) {
        int n = 0;
        // String[] data = {
        //     "N~F=0", 
        //     "R~T>2"
        // };

        String[] data = {
            "M~C<2", 
            "C~M>1"
        };

        System.out.println(solution(n, data));
    }

    
    static char[] friendsAlphabet = new char[] { 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' };
    public static int solution(int n, String[] data){
        int answer = 0;
        createAllFriendsRow(0);
        for (String cs : createFriendsRowList) {
            if (checkCondition(cs, data)){
                answer++;
            }
        }
        return answer;
    }

    static boolean[] visited = new boolean[8];
    static List<String> createFriendsRowList = new ArrayList<String>();
    static char[] createFriendsRowArray = new char[8];
    public static void createAllFriendsRow(int index){
        if (index == visited.length){
            createFriendsRowList.add(String.valueOf(createFriendsRowArray));
        }
        else{
            for(int i=0; i<visited.length; i++){
                if (!visited[i]){
                    visited[i] = true;
                    createFriendsRowArray[index] = friendsAlphabet[i];
                    createAllFriendsRow(index + 1);
                    visited[i] = false;
                }
            }
        }
    }

    public static boolean checkCondition(String friendsArray, String[] data){
        String[] splits;
        String startFriend, endFriend;
        String condition;
        int conditionCount = 0;
        int gap;
        int indexGap = 0;
        int endIndex, startIndex;

        for (String c : data) {
            splits = c.split("");

            startFriend = splits[0];
            endFriend = splits[2];
            condition = splits[3];
            gap = Integer.parseInt(splits[4]);

            startIndex = friendsArray.indexOf(startFriend);
            endIndex = friendsArray.indexOf(endFriend);
            indexGap = Math.abs(endIndex - startIndex) - 1;

            switch (condition) {
                case "=":
                    if (indexGap != gap){
                        return false;
                    }
                    conditionCount++;
                    break;
                
                case ">":
                    if (indexGap <= gap){
                        return false;
                    }
                    conditionCount++;
                    break;

                case "<":
                    if (indexGap >= gap){
                        return false;
                    }
                    conditionCount++;
                    break;
            }
        }

        if (conditionCount == data.length){
            return true;
        }
        else{
            return false;
        }
    }
}

그 결과...

8.6초라는 어마어마한 성능을 가지고 있었다;

8! 만큼 2번 (프렌즈의 모든 경우의 수 구할 때, 조건에 맞는지 구할 때)을 돌아서 성능이 저렇게 나온건지 해서 아래와 같이 수정했었다.

1. 모든 경우의 수를 구함과 동시에 조건에 맞는지 확인한다.
2. 조건에 맞다면 +1 해준다.

위와 같이 작성해봐도 동일하게 8초 이상이 출력되었다. 그래서 다시 확인한 결과 checkCondition 함수에서 split 메소드로 문자열을 자르는 부분이 있었는데, 이 부분을 split 대신 charAt 메소드를 사용하여 구현해 보았다.

class Solution {
    char[] friendsAlphabet = new char[] { 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' };
    public int solution(int n, String[] data){
        int answer = 0;
        createAllFriendsRow(0, data);
        answer = correctCount;
        return answer;
    }

    boolean[] visited = new boolean[8];
    char[] createFriendsRowArray = new char[8];
    int correctCount = 0;
    public void createAllFriendsRow(int index, String[] data){
        if (index == visited.length){
            if (checkCondition(String.valueOf(createFriendsRowArray), data)){
                correctCount++;
            }
        }
        else{
            for(int i=0; i<visited.length; i++){
                if (!visited[i]){
                    visited[i] = true;
                    createFriendsRowArray[index] = friendsAlphabet[i];
                    createAllFriendsRow(index + 1, data);
                    visited[i] = false;
                }
            }
        }
    }

    public boolean checkCondition(String friendsArray, String[] data){
        char startFriend, endFriend;
        char condition;
        int conditionCount = 0;
        int gap;
        int indexGap = 0;
        int endIndex, startIndex;

        for (String c : data) {
            startFriend = c.charAt(0);
            endFriend = c.charAt(2);
            condition = c.charAt(3);
            gap = c.charAt(4) - '0';

            startIndex = friendsArray.indexOf(startFriend);
            endIndex = friendsArray.indexOf(endFriend);
            indexGap = Math.abs(endIndex - startIndex) - 1;

            switch (condition) {
                case '=':
                    if (indexGap != gap){
                        return false;
                    }
                    conditionCount++;
                    break;
                
                case '>':
                    if (indexGap <= gap){
                        return false;
                    }
                    conditionCount++;
                    break;

                case '<':
                    if (indexGap >= gap){
                        return false;
                    }
                    conditionCount++;
                    break;
            }
        }

        if (conditionCount == data.length){
            return true;
        }
        else{
            return false;
        }
    }
}

위와 같이 작성 한 후 다시 제출했더니 아래와 같은 결과가 나왔다.

 

속도와 메모리가 9배 이상 차이가 남을 확인할 수 있었다. 

 

결론.

  - split 대신 charAt을 사용할 수 있는 경우 charAt을 사용하는 것이 성능상에 유리하다.