[알고리즘C++] 단체사진 찍기

후이재·2020년 9월 9일
1

오늘의 문제

하.. 전역변수 초기화.. vector도 clear해줘야 하는구나...
https://programmers.co.kr/learn/courses/30/lessons/1835

단체사진 찍기

나의 풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<char> friends1 ={'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
string per = "ACFJMNRT";                  
vector<string> stringSet;                 
bool check[8] ={false};                

void permutation( int depth){ 
    
    if(depth == 8){
        stringSet.push_back(per); 
        return;
    }
    for(int i = 0; i < friends1.size(); i++){
        if(!check[i]){
            check[i] = true;
            per[depth] = friends1[i];          
            permutation( depth + 1);    
            check[i] = false;          
        }
    }
}

int solution(int n, vector<string> data) {
    stringSet.clear();
    friends1 ={'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    per = "DDDDDDDD";
    for(int i=0;i<8;i++) check[i] = false;
    
    int answer = 0;
    permutation(0);

    vector<string> c(n);
    vector<int> nn(n);
    vector<vector<string>> my(n, vector<string>(2));
    
    for(int i=0;i<n;i++){
        string l = data[i];
        my[i][0] = l.substr(0, 1);
        my[i][1] = l.substr(2, 1);
        
        c[i] = l.substr(3, 1);
        nn[i] = stoi(l.substr(4, 1));  
    }
    
    for(int i=0;i<stringSet.size();i++){
        string s = stringSet[i];        
        for(int j=0;j<n;j++){
            int start = s.find(my[j][0]);
            int end = s.find(my[j][1]);
            int num = nn[j];
            if(c[j] == "="){
                if(abs(start-end)-1 != num)
                  break;
            }else if(c[j] == "<"){
                if(abs(start-end)-1 >= num)
                  break;
            }else{
                if(abs(start-end)-1 <= num)
                  break;
            }
            if(j == n-1){
                answer++;}
        }
    }
    return answer;
}

모범 답안

#include <string>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

inline int normalize_alphabet(char c)
{
    assert(c >= 'A' && c <= 'Z');
    return c - 'A';
}

inline int normalize_digit(char c)
{
    assert(c >= '0' && c <= '9');
    return c - '0';
}

inline int abs(int n)
{
    return n < 0 ? -n : n;
}

inline void get_indexes(int (*index)[26], const char* str)
{   
    for (int i = 0; str[i] != '\0'; i++)
    {
        (*index)[normalize_alphabet(str[i])] = i;
    }   
}

int solution(int n, vector<string> data)
{
    char str[] = "ACFJMNRT";
    int index[26] = { 0, };
    get_indexes(&index, str);

    int perm[] = {0,1,2,3,4,5,6,7};

    int answer = 0;
    do
    {
        bool flag = true;

        for (string& cond : data)
        {
            const int name1 = normalize_alphabet(cond[0]);
            const int name2 = normalize_alphabet(cond[2]);
            const int num = normalize_digit(cond[4]);
            const char op = cond[3];

            const int dist = abs(perm[index[name1]] - perm[index[name2]]) - 1;

            if (op == '>' && !(dist > num)) flag = false;
            if (op == '=' && !(dist == num)) flag = false;
            if (op == '<' && !(dist < num)) flag = false;

            if (flag == false)
            {
                break;
            }
        }
        if (flag)
        {
            answer++;
        }
    } while (next_permutation(perm, perm + 8));

    return answer;
}

배울 점

  • 와 inline함수 이렇게 쓰는구나
  • 전역변수 초기화 하라 하는 문제는 반드시. 모든. 변수를. clear.해야 한다...
  • testCase는 다 맞는데 제출시 계속 틀려서 하.. 개 삽질했다
profile
공부를 위한 벨로그

0개의 댓글