프로그래머스(C++) / level 2 : 단체사진 찍기

level 2 : 단체사진 찍기

https://programmers.co.kr/learn/courses/30/lessons/1835?language=cpp 

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

 

 

🎨 문제

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

 

---

 

 

🎨 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    int answer = 0;
    
    vector<char> character(8);
    character[0] = 'A'; character[1] = 'C'; character[2] = 'F'; character[3] = 'J'; 
    character[4] = 'M'; character[5] = 'N'; character[6] = 'R'; character[7] = 'T'; 
    sort(character.begin(), character.end());
    
    unordered_map<char, int> um;
    do{
        for(int i=0; i<8; i++){
            um[character[i]] = i;
        }
        
        bool check = true;
        for(int i=0; i<data.size(); i++){
            int interval = abs(um[data[i][0]] - um[data[i][2]]) -1; //간격
            if(data[i][3] == '='){
                if(interval != data[i][4] - '0'){
                    check = false;
                    break;
                }
            }
            else if (data[i][3] == '<'){
                if(interval >= data[i][4]-'0'){
                    check = false;
                    break;
                }
            }
            else if (data[i][3] == '>'){
                if(interval <= data[i][4]-'0'){
                    check = false;
                    break;
                }
            }
        }
        if(check == true){
            answer++;
        }
        
    }while(next_permutation(character.begin(), character.end()));
    
    return answer;
}

 

next_permutation

next_permutation으로 순열을 구할 수 있다. next_permutation을 사용하지 않는다면 DFS로 순열을 직접 구현해야 하지만 next_permutation을 사용하면 쉽게 순열을 구할 수 있다.

vector가 무조건 오름차순으로 되어있어야 모든 조합을 구할 수 있고, 작은 수부터 큰 수로 차례대로 출력된다.

 

unordered_map

해쉬 함수인 unordered_map을 사용하여 각 캐릭터가 어느 위치에 있는지 빠르게 구할 수 있다.