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

난이도: Level 2

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/1835

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

 

8명의 사람이 줄을 설 때,

주어진 조건을 만족하는 경우의 수를 세는 문제입니다.

 

아무 조건이 없을 때, 8명의 사람이 줄을 설 수 있는 경우의 수는

8! = 40320 이 됩니다.

따라서 모든 경우의 수를 탐색해 보기에 크게 문제가 되지 않습니다.

 

조건의 수는 최소 1개에서 최대 100개가 주어집니다.

두 사람 A와 B 사이의 간격을 구하게 되는데, 이 간격은 |(A의 위치 - B의 위치)| - 1 가 됩니다.

A = 0, B = 3에 위치하고 있다면, 두 사람 사이의 간격은 2가 되는 것이죠.

 

이후 간격이 일치하거나, 더 작거나, 더 큰 경우 세 가지로 구분하여, 각각 함수를 작성하였습니다.

줄 서는 방법이 주어진 모든 조건을 만족한다면, 경우의 수를 하나 추가합니다.

 

줄 서는 경우는 8명 중 중복을 허용하지 않습니다.

따라서 재귀 함수를 이용한 DFS를 구현하였고, 이미 줄을 선 사람을 파악하기 위하여 set 자료구조를 사용하였습니다.

이미 set 내에 insert된 사람이라면 추가하지 않고 넘어가는 것이죠.

줄 선 사람의 수가 8명이 되면, 조건을 통해 확인하는 방법으로 구현하였습니다.

 

줄을 설 사람을 나타내는 배열 friends와 조건을 나타내는 배열 data는 함수를 전달하며 레퍼런스를 호출하는 방식으로 사용하였습니다.

 

코드 링크: GitHub

GitHub - kchung1995/code_test_personal: 혼자 코딩 테스트 공부를 하며 사용하는 저장소

// 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/1835
#include <string>
#include <vector>
#include <set>
#include <cmath>

using namespace std;

int answer;

bool equalsTo (int a, int b, int dist) {
    if ((abs(a-b) - 1) == dist) return true;
    else return false;
}

bool lessThan (int a, int b, int dist) {
    if ((abs(a-b) - 1) < dist) return true;
    else return false;
}

bool furtherThan (int a, int b, int dist) {
    if ((abs(a-b) - 1) > dist) return true;
    else return false;
}

void satisfyCondition(string input, vector<string> &data) {
    bool satisfiesAll = true;

    for (auto &condition : data) {
        int a, b;
        int dist = (condition[4] - '0');
        for (int i = 0; i < input.size(); i++) {
            if (condition[0] == input[i]) a = i;
            if (condition[2] == input[i]) b = i;
        }

        if (condition[3] == '=') {
            if (equalsTo(a, b, dist) == false) {
                satisfiesAll = false;
            }
        }
        else if (condition[3] == '<') {
            if (lessThan(a, b, dist) == false) {
                satisfiesAll = false;
            }
        }
        else if (condition[3] == '>') {
            if (furtherThan(a, b, dist) == false) {
                satisfiesAll = false;
            }
        }
    }

    if (satisfiesAll) answer++;
    return;
}

void lineup(string input, set<int> occupied, vector<char> &friends, vector<string> &data) {

    if (input.size() == friends.size()) {
        satisfyCondition(input, data);
        return;
    }

    else {
        for (int i = 0; i < friends.size(); i++) {
            if (occupied.find(i) == occupied.end()) {
                string nextInput = input + friends[i];
                occupied.insert(i);
                lineup(nextInput, occupied, friends, data);
                occupied.erase(i);
            }
        }
    }
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {

    answer = 0;
    vector<char> friends = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    set<int> occupiedInit;
    lineup("", occupiedInit, friends, data);

    return answer;
}​

 

 

주의점:

이 문제의 경우에는, friends 벡터를 전역으로 설정할 경우 runtime error가 발생합니다.

처음에 주석에 이렇게 적혀있는데요.

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.

 

아마 다른 프로그래머스 문제에는 없던 내용이 적혀 있는 것으로 보아, 해당 문제의 제약조건 상 전역변수로 선언하기엔 크기가 너무 큰가 봅니다.

배열은 전역보다는 처럼 메인 함수 내에 선언하시고 사용하는 것을 권장드립니다.