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

 

문제 개요

 

가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다. 사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다. 각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해 보자.

 

입력 형식

입력은 조건의 개수를 나타내는 정수 n과 n개의 원소로 구성된 문자열 배열 data로 주어진다. data의 원소는 각 프렌즈가 원하는 조건이 N~F=0과 같은 형태의 문자열로 구성되어 있다. 제한조건은 아래와 같다.

• 1 <= n <= 100
• data의 원소는 다섯 글자로 구성된 문자열이다. 각 원소의 조건은 다음과 같다.
  • 첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다. {A, C, F, J, M, N, R, T} 각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다. 첫 번째 글자는 조건을 제시한 프렌즈, 세 번째 글자는 상대방이다. 첫 번째 글자와 세 번째 글자는 항상 다르다.
  • 두 번째 글자는 항상 ~이다.
  • 네 번째 글자는 다음 3개 중 하나이다. {=, <, >} 각각 같음, 미만, 초과를 의미한다.
  • 다섯 번째 글자는 0 이상 6 이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.

출력 형식

모든 조건을 만족하는 경우의 수를 리턴한다.

<예시 입출력>

int n	String[] data	출력
2	["N~F=0", "R~T>2"]	3648
2	["M~C<2", "C~M>1"]	0

 

---

 

풀이

이 문제는 좀 오래 걸린다는 생각은 들어도 그래프 탐색 알고리즘인 DFS로 풀어야 한다. (나도 제출해보고서야 알게 되었다)

나는 DFS를 풀 때 재귀를 주로 사용하는 편인데, 재귀를 돌릴 때 매개변수는 문제나 상황에 따라 매번 바뀐다.

 

일단 각 정점, 즉 줄을 서는 사람이 이미 서있는지 아니면 줄을 서기 위해 대기 중인지를 의미하는 boolean[] 형태의 visited를 넘겨주었고, 추가적으로 입력받은 String[] data와 문제에서 지정해준 일렬로 설 사람들 8명을 String[] 타입으로 만들어 함께 넘겼다.

마지막으로 현재 줄을 어떻게 서고 있는지를 의미하는 String 변수인 line을 넘겨 총 4개의 매개변수를 넘기는 형식의 dfs() 메서드를 만들어 문제를 풀었다.

 

public void dfs(String[] names, String[] data, boolean[] visited, String line)

 

풀이 순서 다음과 같다.

1. 파라미터로 넘겨줄 변수들을 생성한다.
2. 문제에서 제공한 메소드인 solution()에서는 dfs()만 실행하고 해당 메소드에서 모든 경우의 수를 구해서 int형 변수인 answer에 넣어준다.
   • 일단은 dfs로 모두 탐색하기 때문에 총 경우의 수는 8!(팩토리얼) == 40320 이다.
   • 모든 경우의 수를 일단 돌면서 모든 인원이 일렬로 섰을 때마다 문제에서 입력받은 조건들을 판별해서 조건을 만족하면 카운팅 하고, 만족하지 않는다면 카운팅 하지 않도록 처리한다.
3. dfs() 메소드가 모두 종료되면 answer를 리턴해준다.

 

---

 

코드

class Solution {    
    int answer = 0;
    public int solution(int n, String[] data) {
        answer = 0;
        String[] names = {"A", "C", "F", "J", "M", "N", "R", "T"};
        dfs(names, data, new boolean[8], "");
        return answer;
    }

    public void dfs(String[] names, String[] data, boolean[] visited, String line) {
        if (line.length() == 7) {
            if (check(line, data)) {
                answer++;
            }
            return;
        }
        for (int i=0 ; i<names.length ; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            dfs(names, data, visited, line + names[i]);
            visited[i] = false;
        }
    }

    public boolean check(String line, String[] data) {
        for (String d : data) {
            String[] items = d.split("");
            int start = line.indexOf(items[0]);
            int end = line.indexOf(items[2]);
            int length = Integer.parseInt(items[4]);
            if (items[3].equals("<")) {
                if (length+1 <= Math.abs(start - end))
                    return false;
            } else if (items[3].equals(">")) {
                if (length+1 >= Math.abs(start - end))
                    return false;
            } else {
                if (length+1 != Math.abs(start - end))
                    return false;
            }
        }
        return true;
    }
}

 

---

 

제출 결과

 

뭐.. 일단은 맞췄따.

 

---

 

마치며

 

뭔가 아까웠다..

스킬체크 레벨 2에 도전하고 있었는데 첫 번째 문제를 5분 만에 해결해서 와 이번엔 올라가겠네 ㅎㅎ 이러고 있었더니, 두 번째에 이 문제가 내 앞길을 가로막아 버렸다.

지금에서야 제출이라도 해볼걸 하는 생각이 든다. 왜냐면 실제로 문제를 해결하고서 제출하니까 정확도 체크 1개 항목만 있고, 효율성은 전혀 보지 않았기 때문이다.

이런 후회를 하는 이유는, 처음에 문제를 보고 잠깐 당황했으나, '그래프 탐색 알고리즘을 사용한다면 가능은 하겠네..'라는 생각을 했었기 때문이다. 하지만 예제 입출력을 보고 '와 3천 번이 넘는 횟수를 그래프를 통해 탐색하면 시간초과가 나오겠구나'라는 생각에 감도 못 잡고 실패했다.

그래도 뭔가 혼자서 풀어보면서 dfs에 대해 조금 더 익숙해진 기분이 들어서 그런 점은 좋은 것 같다.

혹시 글 본문에 오류가 있거나 문제가 있으면 댓글로 꼭 알려주세요!