본문 바로가기
코딩테스트/프로그래머스

프로그래머스] C++ 2017 카카오 - 단체사진 찍기(Level 2)

by Hwan2 2021. 7. 20.
728x90
반응형

 

 

 

 

해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다.

아래 링크를 통해 풀 수 있습니다.

 

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

 

 

1. 조건

  • 첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다. {A, C, F, J, M, N, R, T} 각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다.
  • data는 1 ~ 100개까지 들어 있다.
  • data의 각 요소들은 다음과 같은 형태를 갖는다.
    - 첫번째와 세번째는 알파벳(A, C, F, J, M, N, R, T 중 1개)
    - 네번째 글자는 ( <, >, = ) 중 하나이다.
    - 다섯번째 글짜는 숫자로 각 인원이 원하는 거리를 뜻한다.
  • data의 조건을 만족하면서 줄을 설 수 있는 모든 경우의 수를 구하여라.

 

2. 풀이

해당 문제는 각 문제를 쪼개서 푼다면 쉽게 풀 수 있는 문제입니다.

우선 {A, C, F, J, M, N, R, T}가 나올 수 있는 경우의수는 40320가지 이다.

이는 8! 로 풀 수 있으며, 순열을 이용해 간단히 섞을 수 있습니다.

 

저희는 40320의 경우의 수 중에 data에 있는 모든 조건을 만족하는 경우만 추려주면 됩니다.

 

각 data의 각 원소의 문자열은 길이가 고정이므로 특정 위치에서 원하는 문자를 뽑아서 처리해줄 수 있습니다.

string s = data[0]; 로 하나의 원소를 뺏다고 가정 했을 때,

s[0] 과 s[2]는 알파벳이 뽑히고, 

s[3] 은 같은 선상에 있을지, 숫자 이상으로 떨어져 있을지, 붙어있을지 결정하는 기호가 있습니다.( <, >, = )

s[4]는 간격의 숫자가 있고요.

 

s[0] 과 s[2]의 간격은 섞인 배열을 기준으로 절대값으로 빼주면 간격이 나오게 됩니다.

 

이를 if문을 통해 처리해준다면 간단하게 풀 수 있습니다.

 

3. 코드

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

using namespace std;

int find_char(vector<char>& v, char c){
    for(int i = 0; i < v.size(); i++)
        if(c == v[i]) return i;
    
    return -1;
}

bool func1(int a, int b, int num){
    return abs(a - b) == num ? true : false;
}

bool func2(int a, int b, int num){
    return abs(a - b) < num ? true : false;
}

bool func3(int a, int b, int num){
    return abs(a - b) > num ? true : false;
}

int solution(int n, vector<string> data) {
    vector<char> v = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    int answer = 0;
    
    do {
        bool flag = true;
        
        for(auto& s : data) {
            int a = find_char(v, s[0]);
            int b = find_char(v, s[2]);
            int num = (s[4] - '0') + 1;

            if(s[3] == '=') flag = func1(a, b, num);
            else if(s[3] == '<') flag = func2(a, b, num);
            else flag = func3(a, b, num);
            
            if(!flag) break;
        }

        if(flag) answer++;

    } while (next_permutation(v.begin(), v.end()));

    return answer;
}

 

 

 

 

반응형

댓글


스킨편집 -> html 편집에서