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

프로그래머스 1835. 단체사진 찍기 문제를 풀면서 얻어갈 수 있는 것들이 무엇이 있는지 살펴보고 뜯어 먹어보자. 이 문제는 완전 탐색으로 모든 케이스를 확인하면 시간 내에 정답을 구할 수 있는 문제이다. 재귀 함수와 완전 탐색에 대한 이해가 필수적이다. 풀이는 자바(Java)로 구현했다. 이 게시글의 내용과 코드를 제대로 이해한다면 다른 언어로도 금방 문제를 해결할 수 있다.

얻어 갈 수 있는 것

필자가 완전 탐색 문제를 처음 접했을 때, 모든 케이스를 확인하면 되겠다는 생각은 들었지만 코드로 구현하려면 어떻게 해야 하는 지 몰라 막막했던 기억이 있다. 이런 유형의 문제는 재귀 함수와 완전 탐색을 이해하고 있으면 쉽게 해결할 수 있는 문제다. 개인적으로 재귀 함수를 이해하고 문제 해결에 활용할 수 있게 되기 까지 오랜 시간이 걸렸다. 여러분이 이 글을 통해 재귀 함수와 완전 탐색에 대한 이해도를 조금이나마 높일 수 있길 바란다.

재귀 함수에 대한 이해

재귀 함수는 내부적으로 자기 자신을 호출하는 함수이다. 종료 조건이 반드시 필요하다는 특징을 가지고 있고, 재귀 호출을 너무 많이 하게 되면 스택 메모리에 너무 많은 메모리를 할당하여 스택 오버플로가 발생할 수 있다는 점을 주의해야 한다.

public void func(int count) {
  if (count == 5) {
    return;
  }
  System.out.println("1");
  func(count + 1);
  System.out.println("2");
}

재귀 함수는 위 func 함수처럼 생겼다. func(0) 으로 호출하면 출력 결과가 어떻게 될 지 예상해보라.

1
1
1
1
1
2
2
2
2
2

결과는 위처럼 1을 5번 출력하고 2를 5번 출력하게 된다. 재귀 함수는 자기 자신을 내부적으로 호출하는 함수다. 따라서 종료 조건이 없으면 죽을 때까지 자기 자신을 호출하게 된다. 위 예시에서는 count == 5 가 종료 조건이다. 반드시 원하는 조건에 재귀 호출을 멈출 수 있도록 종료 조건을 잘 설정해주는 것을 잊지 말자. 함수는 return 되거나 함수를 끝까지 실행했을 때 종료된다. 위 예시 코드는 내부적으로 count + 1을 인자로 넘겨주므로 이 함수의 최초 호출이 func(0)이라면 1을 5번 출력하기 전에는 함수가 종료되지 않는다.

재귀함수에 대해 더 자세한 설명이 필요하다면 여기(👈click!!)에 관련 글이 있다.

완전 탐색(Brute Force)에 대한 이해

완전 탐색은 모든 경우의 수를 탐색하는 것이다. A B C D 네 개의 알파벳을 줄 세우는 방법을 예로 들면 아래와 같이 나타낼 수 있다. 줄의 맨 앞에 A가 있는 경우만 그림으로 나타내 보았다.

위 그림은 A로 시작하는 케이스이지만 B, C, D로 시작하는 경우에 대해서도 위와 비슷하게 나타낼 수 있다. 그래서 총 24가지의 경우의 수가 나온다. 재귀 함수를 사용해 위와 같은 경우를 모두 탐색하면서 종료 조건에 도달했을 때 특정 작업을 수행한 뒤 재귀 호출을 종료할 수 있다. 두 가지 중요한 포인트가 있는데, 그 중 하나는 4개의 알파벳을 줄 세우는 경우에는 재귀 함수의 종료 조건을 줄의 길이가 4가 되었을 때로 설정해야 한다는 점이다. 그리고 나머지 하나는 이미 줄을 세운 알파벳은 또 줄을 세울 수 없으므로 이를 체크하면서 탐색해야 한다는 점이다.

프로그래머스 1835 문제 링크 및 핵심 아이디어

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

• 줄 서는 모든 경우의 수에 대해 주어진 줄 서기 조건에 해당하는 케이스가 몇 개인지 반환하는 메서드를 구현하는 문제이다.
• 재귀 함수를 활용해 모든 경우의 수를 탐색하며 종료 조건에 도달했을 때 주어진 줄 서기 조건을 만족하는 케이스를 카운트 한다.
• 줄 세우는 방법
  • ArrayList<Character> Collection을 생성하고 카카오 프렌즈들을 put, reomve 하는 방식을 고려한다. 그러면 리스트의 길이가 k가 되었을 때 줄 서기 조건을 만족하는 케이스를 카운트 할 수 있다.
• 이미 줄 세운 프렌즈를 체크하는 방법
  • boolean 배열을 만들어 줄 선 친구를 표시하여 뒤에 줄 세울 대상에서 제외한다.

풀이

import java.util.*;
class Solution {
    private char[] people = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    private boolean[] check = {false, false, false, false, false, false, false, false};
    private List<Character> orderList = new ArrayList<>();
    private String[] data;
    private int N;
    private int answer = 0;
    
    public int solution(int n, String[] data) {
        this.data = data;
        this.N = n;
        permutation(0);
        return answer;
    }
    
    private int find(Character ch) {
        return orderList.indexOf(ch);
    }
    private boolean isAnswer() {
        for (int i=0; i<N; i++) {
                int diff = Math.abs(find(data[i].charAt(0))-find(data[i].charAt(2)))-1;
                int expected = data[i].charAt(4)-'0';
                char op = data[i].charAt(3);
                if ((op == '=') && (diff != expected)) {
                    return false;
                }
                else if ((op == '<') && (diff >= expected)) {
                    return false;
                }
                else if((op == '>') && (diff <= expected)) {
                    return false;
                }
            }
        return true;
    }
    
    private void permutation(int index) {
        if(orderList.size() == 8) {
            if(isAnswer()){
                answer += 1;
            }
            return;
        }
        
        for(int i=0; i<8 ;i++) {
            if(check[i]) continue;
            check[i] = true;
            orderList.add(people[i]);
            permutation(i);
            orderList.remove(orderList.size()-1);
            check[i] = false;
        }
        
    }
}