[프로그래머스] 단체사진 찍기, 2017 카카오코드 본선, C++

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

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

꽤 오래 걸린 문제이다.

우선 어떻게 풀어야할지 감이 안왔다. 처음 문제를 봤을때 순열을 구하는 공식을 사용해서 만들어야하나 고민했다. 하지만 level 2에서 그런 문제가 나올리가 없다고 생각해서 다른 방법을 생각했다. 물론 공식을 사용해서 풀수만 있으면 훨씬 빠르게 끝낼수 있었겠지만 범위가 있어서 공식은 아니라고 판단헀다. 오랫동안 고민했는데 도저히 떠오르지 않아서 질문하기 제목을 살짝 훔쳐봤고 DFS문제인 것을 알게 되었다.

DFS 인 것을 파악한 이후엔 그래도 나름 술술 풀렸다. dfs를 사용해서 순열을 만들고, 만든 순열과 조건을 사용해서 필요한 답만 찾으면 됐다. 물론 이때도 문제가 몇개 있었는데 cstring, cstdlib 등 여러 헤더를 추가했는데도 atoi 에러가 떴다. 어차피 0~6 사이의 문자를 숫자로만 바꾸면 되는 거라 헤더 추가안하고 함수로 만들었다.

테스트케이스를 통과한걸 확인뒤엔 시간초과를 넘기기 어려웠다. 이것도 여러 방법으로 이리저리 풀어봤으나 내 실력으로는 역부족이었다. 그래서 다시 질문하기를 찾아봤고 1문제 안에 10문제를 한번에 풀어야한다는 이야기가 있었다. 내 알고리즘은 solution 함수가 실행되면 매번 DFS를 사용해서 순열을 찾는 알고리즘이었기 때문에 10문제를 한번에 풀어도 같은 순열을 10번 반복한다(8! * 10)는 이야기였다. 이를 해결하기 위해 vector를 생성해서 딱 한번만 순열을 찾고 그다음부턴 조건에 대입하는 방식으로 접근했고 해결할 수 있었다.

 

#include <string>
#include <vector>
#include <map>
#include <cmath>

using namespace std;
int cnt = 0;
string kakao_friends = "ACFJMNRT";
vector<string> perms;

// dfs
void dfs(int ind, string perm){
    if (ind == 0b11111111)
    {
        perms.push_back(perm);
        return;
    }
    for (int i=0; i<8; i++)
    {
        if (ind & (1<<i)) continue;
        dfs(ind | (1<<i), perm + kakao_friends[i]);
    }
}

int atoi(char c){
    return (int)c - (int)'0';
}

int check(string perm, vector<string> data){
    map<char, int> pos;
    for (int i=0; i<8; i++){
        pos.insert({perm[i], i});   
    }
    
    for (int i=0; i < data.size(); i++)
    {
        int a, b,c ;            
        a = pos[data[i][0]];
        b = pos[data[i][2]];
        c = atoi(data[i][4]) + 1;
        switch (data[i][3]){
            case '=':
            {
                if (abs(a - b) == c)
                    continue;
                return 0;
            }
            case '>':
            {
                if (abs(a - b) > c)
                    continue;
                return 0;
            }
            case '<':
            {
                if (abs(a - b) < c)
                    continue;
                return 0;
            }
                
        }
    }
    return 1;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    int answer = 0;
    if (!cnt) {
    	// 한번만 순열 찾기
        dfs(0, "");
        cnt++;
    }
    // 1. 8개원소를 사용해서 순열 생성(dfs)
    for (auto perm: perms){
        if (check(perm, data))
            answer++;
    }
    // 2. 순열을 만들고 난뒤 모든 조건 확인 -> 다 맞은 경우에만 answer++
    return answer;
}

오랜만에 C++문제를 풀어보고자 싱글벙글했는데, 이리치이고 저리치여서 상처만 남은 문제였다. 다행히 풀어서 망정이지 못풀었으면 아마 내일까지 스트레스 받았을 것이다. 

그리고 블로그에 안올리려했는데 짜증 이빠이라 스트레스 풀겸 올린다.