[programmers] Lv.2 단체사진 찍기(c++)

"일단 해보고 생각하자"를 또 뼈저리게 느꼈던 문제..

하나하나 돌면 시간 초과가 날거라고 막연히 생각했는데, 그럼 도대체 어떻게 해야할 지 몰라서 검색해보니 하나하나 돌았다고 한다...? 그냥 바로 해봤으면 좋았을걸..

그럼 next_permutation을 사용하면 끝이죠.

#include <string>
#include <vector>
#include <algorithm> // next_permutation

using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    vector<char> kakao_friends = { 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' };
    int cnt=0;
    do {
        bool flag = true;
        for (auto d : data) {
            char f1 = d[0], f2 = d[2];
            char condition = d[3];
            int dist = d[4] - '0' + 1;

            int f1_idx = find(kakao_friends.begin(), kakao_friends.end(), f1) - kakao_friends.begin();
            int f2_idx = find(kakao_friends.begin(), kakao_friends.end(), f2) - kakao_friends.begin();
            
            switch (condition) {
            case '=':
                if (abs(f1_idx - f2_idx) != dist) flag = false;
                break;
            case '<':
                if (abs(f1_idx - f2_idx) >= dist) flag = false;
                break;
            case '>':
                if (abs(f1_idx - f2_idx) <= dist) flag = false;
                break;
            default:
                break;
            }
            if (!flag) break;
        }
        if (flag) cnt++;
    } while (next_permutation(kakao_friends.begin(), kakao_friends.end()));

    return cnt;
}

---

문제

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

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

728x90

---

[접근1]

kakao_friends 벡터에 초기 순서를 넣어준다.

이것을 do while문과 algorithm library에 있는 next_permutation함수를 사용하여 하나하나 돌아준다.

만족하는 순서를 count 하기 위해서 cnt 변수를 0으로 초기화해준다.

    vector<char> kakao_friends = { 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' };
    int cnt=0;
    do {
	...
    } while (next_permutation(kakao_friends.begin(), kakao_friends.end()));

---

[접근2]

for문 switch문을 연달아 쓰기 때문에 break가 원하는대로 듣지 않을거라 추측, flag를 따로 만들어 조건을 만족하지 않을때 빠져나오고 조건을 만족하면 cnt값을 증가시키도록 구현하였다.

for문으로 data를 하나씩 돌면서 조건을 만족하는지 확인한다.

f1, f2에는 각 friends들의 이름을, condition엔 조건을 나타낼 연산자?를 dist엔 얼마나 떨어지길 원하는지 숫자를 넣어줬다. index의 차로 비교할것이기 때문에 1을 더해줬다.

각 f1, f2의 index위치를 구하여 _idx에 넣어주고

switch문을 사용해 각 조건에 만족하는지 확인한다. 만족하지 않을때, flag를 false로 만든다.

만약 flag가 false면, data를 돌던 for문을 나가고, for문이 끝나고 flag가 true이면 cnt값을 1 증가시켜준다.

// do while문 안

bool flag = true;
for (auto d : data) {
    char f1 = d[0], f2 = d[2];
    char condition = d[3];
    int dist = d[4] - '0' + 1;

    int f1_idx = find(kakao_friends.begin(), kakao_friends.end(), f1) - kakao_friends.begin();
    int f2_idx = find(kakao_friends.begin(), kakao_friends.end(), f2) - kakao_friends.begin();

    switch (condition) {
    case '=':
        if (abs(f1_idx - f2_idx) != dist) flag = false;
        break;
    case '<':
        if (abs(f1_idx - f2_idx) >= dist) flag = false;
        break;
    case '>':
        if (abs(f1_idx - f2_idx) <= dist) flag = false;
        break;
    default:
        break;
    }
    if (!flag) break;
}
if (flag) cnt++;