프로그래머스 - 단체사진 찍기(c++)

문제출처 : https://programmers.co.kr/learn/courses/30/lessons/1835

문제난이도

Level 2

문제접근법

1. 배치될 인원수는 한정적이다.
2. 주어진 문자열 위치는 정해져있다.
3. 조건에 따른 경우의 수를 찾는다.

위와 같은 이유로 next_permutation을 써서 푸는 문제였다. 처음에는 어떤 식으로 풀어야할지 감이 잡히지 않아, Lv2에 이 문제가 있는게 의아했는데 다른 사람 답안을 참고하니 쉬웠다.
라이브러리를 사용해서 단순하게 문제를 풀 수 있어서였다.

사용한 언어
C++
추가 사용 라이브러리
algorithm

통과 코드

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

using namespace std;


bool isRight(char c, int diff, int num){
    if(c == '='){
        return diff == num;
    }else if(c == '>'){
        return diff > num;
    }else if(c == '<'){
        return diff < num;
    }
}

int solution(int n, vector<string> data) {
    int answer = 0;
    string friends = "ACFJMNRT";
    
    do{
        bool flag = true;
        for(string text : data){
            char ff = text[0];
            char sf = text[2];
            char comp = text[3];
            int num = text[4] - '0';
            int diff = friends.find(ff) - friends.find(sf);
			int dis = abs(diff) - 1;
            
            if(isRight(comp, dis, num)) continue;
            flag = false;
            break;
        }
        if(flag) answer++;
    }while(next_permutation(friends.begin(), friends.end()));
    
    return answer;
}

피드백

시도 1.
처음엔 vector에 담아서 algrorithm 속 find와 distance 함수를 사용했다.

  vector<char> friends = { 'a', 'c', 'f', 'j', 'm','n','r','t' };
	vector<char>::iterator it;

	do {
		int cnt = 0;
		for (string text : data) {
			char ff = text[0];
			it = find(friends.begin(), friends.end(), ff);
			int findex = distance(friends.begin(), it);
			char sf = text[2];
			it = find(friends.begin(), friends.end(), sf);
			int sindex = distance(friends.begin(), it);
			char comp = text[3];
			char num = text[4];

			int diff = abs(findex - sindex) - 1;

			if (isright(comp, diff, num - '0')) cnt++;
		}
		if (cnt == data.size()) answer++;
	} while (next_permutation(friends.begin(), friends.end()));

그러나 이 코드는 라이브러리 함수 속도 때문에 시간초과가 났고 다른 사람 코드를 참고해서 string을 사용했다.

시도 2.

string friends = "ACFJMNRT";

	do {
		int cnt = 0;
		for (string text : data) {
			char ff = text[0];
			char sf = text[2];
			char comp = text[3];
			int num = text[4] - '0';
			int diff = friends.find(ff) - friends.find(sf);
			int dis = abs(diff) - 1;

			if (isRight(comp, dis, num)) cnt++;
		}
		if (cnt == n) answer++;
	} while (next_permutation(friends.begin(), friends.end()));

이 코드는 통과했지만 일일이 수를 세서 answer를 증가시킨다는 점에서 6초나 걸린다.

시도 3.

flag를 두고 for문 속에 break를 두었다.

그랬더니

0.4초로 확 줄었다.
앞으로 코테에서도 bool flag와 break를 사용해서 시간을 줄일 수 있다는 걸 염두해둬야겠다.