[프로그래머스] 단체사진 찍기 C++ 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/1835?language=cpp 

프로그래머스

 

전체 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
char arr[8]={'A','C','F','J','M','N','R','T'};
bool visit[8];
int res;
string str="";
    
void solve(int cnt, vector<string>& data)
{
    if(cnt==8)
    {
        int idx1, idx2;
        bool flag=true;
        for(int i=0;i<data.size();i++)
        {
            for(int j=0;j<8;j++)
            {
                if(str[j]==data[i][0])
                    idx1=j;
                if(str[j]==data[i][2])
                    idx2=j;
            }
            
            if(data[i][3]=='='&&abs(idx1-idx2)-1!=data[i][4]-'0')
            {flag=false; break;}
            else if(data[i][3]=='<'&&abs(idx1-idx2)-1>=data[i][4]-'0')
            {flag=false; break;}
            else if(data[i][3]=='>'&&abs(idx1-idx2)-1<=data[i][4]-'0')
            {flag=false; break;}
        }
        if(flag==true)
            res++;
        return;
    }
    
    
    for(int i=0;i<8;i++)
    {
        if(visit[i]==false)
        {
            visit[i]=true;
            str+=arr[i];
            solve(cnt+1, data);
            visit[i]=false;
            str.erase(str.begin()+cnt);
        }
    }

}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    int answer = 0;
    fill(visit,visit+8,false);
    res=0;
    solve(0, data);
    answer=res;
    return answer;
}

 

풀이 방식

브루트 포스(brute force) 방식으로 풀었습니다.

모든 방법으로 8명(A, C, F ... T)을 세운 뒤 각각의 세우는 방법이 data 조건에 맞다면 경우의 수를 +1 해준다.

---

풀이 해설

char arr[8]={'A','C','F','J','M','N','R','T'};
bool visit[8];
int res;
string str="";

str에는 줄을 세운뒤 상태가 들어갈 것이다.

예를 들어 주어진 arr의 순서 그대로 세웠다 하면 str = "ACFJMNRT"가 되는 것이다. 또 다른 예로 str="ACFJMNTR"이 있다.

 

visit는 줄을 선 상태인지 아직 줄은 안 섰는지 상태를 bool을 통해 저장할 것이다. true라면 선택되어 줄을 선 상태이다.

visit의 i 번째에는 누구의 상태를 넣을 것이냐면 arr의 i번째와 동일하게 상태를 저장할 것이다.

예를 들어 0번째는 A의 상태, 7번째는 T의 상태이다.

 

res는 경우의 수를 세어줄 것이다.

( 함수 내에서 초기화하자. 채점 시 한번 실행해서 여러 케이스를 테스트하므로 solution에서 초기값으로 초기화해야 함. )

 

fill(visit,visit+8,false);
res=0;
solve(0, data);
answer=res;
return answer;

solution 함수에서 전역 변수에 대해 초기화하는 과정이 필요하다.

프로그래머스에서는 채점 시 한번 실행하여 여러 케이스를 테스트하기에 초기값을 함수 내에 초기화하는 것이 중요한 것.

fill로 줄 선 상태를 visit를 false로, 경우의 수 res는 0으로..

solve 함수의 첫 인자는 줄 선 사람의 명 수를, 두 번째는 data를 포인터로 가지고 다닐 것이다.

포인터를 사용하지 않으려면 아래처럼 전역 변수를 이용해 하면 된다.

vector<string> data2;

int solution(int n, vector<string> data) {
    ...
    data2=data;
    solve(0);
    ...
}

 

먼저, 줄을 세우는 과정부터 설명하겠다.

for(int i=0;i<8;i++)
{
        if(visit[i]==false)
        {
            visit[i]=true;
            str+=arr[i];
            solve(cnt+1, data);
            visit[i]=false;
            str.erase(str.begin()+cnt);
        }
}

모든 방법을 통해 사람을 줄 세워야 하니

visit를 통해 모든 경우의 수로 사람을 줄 세웠다.

i번째 visit가 false라면 아직 줄을 서지 않은 상태로

str에 arr[i]를 추가해 arr[i]가 줄 선 상태로 만든다.( i번째가 누구냐? arr의 i번째 사람의 이름이다. )

줄 선 상태로 만들고 visit[i]를 true로 표시한다.

그리고 1명을 더 줄 세웠으니 solve를 통해 cnt+1을 넘기고 재귀적으로 풀어나간다.

이 함수를 빠져나올 때는 다시 줄을 안 선 상태로 visit[i]=false로, str에서 이 사람을 지워버려 준다.

이때, cnt번째 줄을 섰으므로 str에도 str번째 존재할 것이므로 아래와 같이 구현해 str에서 지워줬다.

str.erase(str.begin()+cnt);

 

 

if(cnt==8)
    {
        int idx1, idx2;
        bool flag=true;
        for(int i=0;i<data.size();i++)
        {
            for(int j=0;j<8;j++)
            {
                if(str[j]==data[i][0])
                    idx1=j;
                if(str[j]==data[i][2])
                    idx2=j;
            }
            
            if(data[i][3]=='='&&abs(idx1-idx2)-1!=data[i][4]-'0')
            {flag=false; break;}
            else if(data[i][3]=='<'&&abs(idx1-idx2)-1>=data[i][4]-'0')
            {flag=false; break;}
            else if(data[i][3]=='>'&&abs(idx1-idx2)-1<=data[i][4]-'0')
            {flag=false; break;}
        }
        if(flag==true)
            res++;
        return;
}

위에서 차례대로 아래로 설명하겠다.

cnt에는 줄 선 사람의 명 수를 카운트한다고 했다. cnt가 8이라면 8명이 세워진 상태로 이제 조건에 맞는지

검사하면 된다.

 

data의 내용은 "N~F=0"으로 존재한다.

그래서 idx1에는 data[i]번째의 [0]을 통해 사람 이름을 찾아, str상의 인덱스의 위치를 저장한다.

( idx2=data[i][1] )

 

예로든 data[i][0]은 "N" data[i][2]는 "F"가 있을 것이다.

str의 상태가 "ACFJMNRT"이라면 N의 인덱스(idx1)는 5, F의 인덱스(idx2)는 2이다.

이것을 왜 구하느냐?? 이 인덱스를 이용해 두 사람이 줄 섰을 때 사이에 몇 명이 껴있는지 알 수 있다!

그래서 아래 코드는 두 사람의 위치를 찾는 과정이다.

 

이제 두 사람의 위치를 찾았으니 조건과 일치하는지 봐야 한다.

"두 사람의 인덱스 차이-1" 만큼 사이에 껴있는 사람의 수가 된다.

이것을 이용해 '='일때, '<'일때, '>'일때 맞춰 조건에 부합하는지 검사하면 된다.

나는 조건에 맞지 않다면 flag를 false로 바꾸어 break하게 했다.

flag를 false로 바꾸는 것은 조건에 맞지 않음이 발생했음을 의미하고, 더 이상 조건 data를 검사하는 것은

무의미하기에 break 했다.

 

if(flag==true)
	res++;
return;

data의 모든 i번째 조건들을 다 검사한 후, flag가 true라면 단 하나도 flag=false에 걸리지 않은 것이니

모두 조건에 충족한다고 볼 수 있으므로 경우의수(res)를 더해준다.

 

테스트 케이스는 맞는데 채점 시 시간초과 또는 틀리다면 한번 확인을 해보자.

1. 전역 변수를 모두 solution 함수 내에서 초기화하는 과정이 필요하다.

2. data의 조건을 검사할 때 break를 통해 더 이상 의미 없는 검사를 하지 말자.

3. 아래처럼 vector를 참조자로 call by reference를 하자.

void solve(int cnt, vector<string>& data)

 

아래처럼 call by value를 했더니 시간 초과가 뜨더라.

void solve(int cnt, vector<string> data)