SnowMan

문제 설명

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.

후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

• 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
  • 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
  • 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.

위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 "학번"을 가지고 있다. 따라서 "학번"은 릴레이션의 후보 키가 될 수 있다.
그다음 "이름"에 대해서는 같은 이름("apeach")을 사용하는 학생이 있기 때문에, "이름"은 후보 키가 될 수 없다. 그러나, 만약 ["이름", "전공"]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다.
물론 ["이름", "전공", "학년"]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다.
따라서, 위의 학생 인적사항의 후보키는 "학번", ["이름", "전공"] 두 개가 된다.

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

제한사항

• relation은 2차원 문자열 배열이다.
• relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
• relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

입출력

문제 풀이

1. 깊이우선탐색을 통해서 모든 튜플 조합을 만들어본다.

2. 해당 조합이 유일성, 최소성을 만족하는지 확인하고 개수를 증가시킨다.

---------------------------------------------------------------------------------

1. 조합 개수가 1 개부터 relation.size() 만큼 일때까지 index 조합을 구한다.

2. 조합을 구했으면 유일성과, 최소성을 만족하는지 확인하고 만족할 경우 ans++, result에 집어넣는다.

소스 코드

#include <vector>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
bool selected[8];
vector<vector<int>> result;
bool check_unique(vector<vector<string>> relation, vector<int> index)
{
    map<string, int> tmp;
    for(int i=0;i<relation.size();i++)
    {
        string str= "";
        for(int j=0;j<index.size();j++)
        {
            str += relation[i][index[j]];
        }
        tmp[str]++;
    }
    for(auto value : tmp)
    {
        if(value.second > 1)
            return false;
    }
    return true;
}
bool check_minimal(vector<vector<string>> relation, vector<int> index)
{
    vector<int> tmp;
    if(index.size() == 1)
        return true;
    for(int i=0;i<result.size();i++)
    {
        bool flag = false;
        for(int j=0;j<result[i].size();j++)
        {
            int value = result[i][j];
            if(find(index.begin(), index.end(), value) == index.end())
            {
                flag = true;
                break;
            }
        }
        if(!flag)
        {
            return false;
        }
    }
    return true;
}
void dfs(int idx, int depth, int cnt, vector<vector<string>> relation, int& ans)
{
    if(depth == cnt)
    {
        vector<int> tmp;
        for(int i=0;i<relation[0].size();i++)
        {
            if(selected[i])
                tmp.push_back(i);
        }
        if(check_unique(relation, tmp) && check_minimal(relation, tmp))
        {
            result.push_back(tmp);
            ans++;
        }
        return;
    }
    for(int i=idx;i<relation[0].size();i++)
    {
        if(selected[i]) continue;
        selected[i] = true;
        dfs(i, depth+1, cnt, relation, ans);
        selected[i] = false;
    }
}
int solution(vector<vector<string>> relation)
{
    int ans = 0;
    for(int i=1;i<=relation[0].size();i++)
        dfs(0, 0, i, relation, ans);
    return ans;
}

문제 설명

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

입출력

문제 풀이

기본적인 완전탐색 문제.

bfs를 이용하여 해결

소스 코드

#include<vector>
#include <queue>
struct pos{
    int y; int x;
};
int dy[] = {1, -1, 0, 0};
int dx[] = {0, 0, 1, -1};
int check[100][100];
using namespace std;
void bfs(int y, int x, vector<vector<int>> maps, int n, int m)
{
    queue<pos> q;
    q.push({y,x});
    check[y][x] = 1;
    while(!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >=0 && nx >=0 && ny < n && nx < m)
            {
                if(!check[ny][nx] && maps[ny][nx])
                {
                    q.push({ny,nx});
                    check[ny][nx] = check[y][x]+1;
                }
            }
        }   
    }
}
int solution(vector<vector<int> > maps)
{
    int answer = 0;
    int n = maps.size();
    int m = maps[0].size();
    bfs(0,0, maps, n,m);
    if(check[n-1][m-1] ==0)
        answer = -1;
    else
        answer = check[n-1][m-1];
    return answer;
}

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳

▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)

◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)

▶ - 커서를 오른쪽으로 이동

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다. - 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다. 따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

입출력

문제 풀이

이 문제는 커서를 왼쪽으로 움직일지 오른쪽으로 움직일지 그때그때 상황에 맞게 움직여야 하기때문에 그리디 문제입니다.

현재 위치에서 오른쪽?왼쪽을 정하는 방법은 target 문자열과 name을 비교하여 다른 문자열이 나오는 크기를 비교해주며

진행하였습니다.

소스 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int solution(string name) {
    int answer = 0;
    string target(name.size(), 'A');
    if(name == target) return answer;
    int cur_idx = 0;
    while(true)
    {
        answer +=min(name[cur_idx] - 'A', 'Z'-name[cur_idx] + 1);
        target[cur_idx] = name[cur_idx];
        
        if(target == name) break;
        
        int left_idx=cur_idx;
        int left_cnt =0;
        while(target[left_idx] == name[left_idx])
        {
            left_idx--;
            left_cnt ++;
            
            if(left_idx ==-1)
            {
                left_idx = name.size()-1;
            }
        }
        
        int right_idx = cur_idx;
        int right_cnt=0;
        while(target[right_idx] == name[right_idx])
        {
            right_idx++;
            right_cnt++;
            if(right_idx == name.size())
            {
                right_idx = 0;
            }
        }
        if(left_cnt < right_cnt)
        {
            cur_idx = left_idx;
            answer += left_cnt;
        }
        else
        {
            cur_idx = right_idx;
            answer += right_cnt;
        }
    }
    return answer;
}

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력

문제 풀이

1. 문자열이 주어졌을때 문자열을 조합해서 만들수 있는 모든 문자열을 만든다.

2. 만들어진 문자열이 소수인지 아닌지 확인한다.

소스 코드

#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
bool selected[7];
vector<char> v;
vector<char> v2;
vector<int> list;
int ans;
bool isPrime(int tmp)
{
    if(tmp == 1 || tmp == 0)
        return false;
    int num = (int)sqrt(tmp);
    for(int i=2;i<=num;i++)
    {
        if(tmp%i ==0)
            return false;
    }
    return true;
}
void dfs(int cnt, int depth)
{
    if(cnt == depth)
    {
        string tmp ="";
        for(auto a : v2)
            tmp += a;
        if(find(list.begin(), list.end(), stoi(tmp)) == list.end())
        {
            list.push_back(stoi(tmp));
            if(isPrime(stoi(tmp)))
                ans++;
        }
        return;
    }
    for(int i=0;i<v.size();i++)
    {
        if(selected[i])continue;
        selected[i] = true;
        v2.push_back(v[i]);
        dfs(cnt, depth+1);
        v2.pop_back();
        selected[i] =false;
    }
}
int solution(string s)
{
    ans = 0;
    for(int i=0;i<s.size();i++)
    {
        v.push_back(s[i]);
    }
    for(int i=1;i<s.size()+1;i++)
    {
        dfs(i,0);
    }
    return ans;
}

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력

문제 풀이

문자열을 정렬하는 문제이다.

sort() 함수를 이용해 비교함수를 따로 구현하였다.

문자열은 정렬은 기본적으로 아스키코드 값이 작을 수록, 길이가 짧을 수록 이라는 특징을 가지고 있다

이 문제에서는 두개의 string을 앞뒤로 붙였을때 큰 값이 먼저 와야하기 때문에

bool compare(string a, string b)

{

    return a+b > b+a;

}

다음과 같은 방법을 이용하였다.

소스 코드

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
bool compare(string a, string b)
{
    return a+b > b+a;
}
string solution(vector<int> numbers)
{
    string ans = "";
    vector<string> nums;
    for(int i=0;i<numbers.size();i++)
    {
        nums.push_back(to_string(numbers[i]));
    }
    sort(nums.begin(), nums.end(), compare);

    if(nums[0] == "0")
        return "0";
    for(int i=0;i<nums.size();i++)
    {
        ans += nums[i];
    }
   
    return ans;
}

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

입출력

문제 설명

1. vector<string> v의 정렬

<algorithm> 헤더의 sort(v.begin(), v.end())를 사용하여 정렬했을 경우

문자열이 사전순, 길이순으로 정렬된다.

따라서 문제에서 다른 번호의 접두어인 경우를 판별할때 바로 오른쪽의 string 과 비교해보면 구분할 수 있다.

소스 코드

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

bool solution(vector<string> phone_book)
{
    bool ans = true;
    sort(phone_book.begin(), phone_book.end());

    for(int i=0;i<phone_book.size()-1;i++)
    {
        if(phone_book[i] == phone_book[i+1].substr(0, phone_book[i].size()))
            return false;
    }
    return ans;
}

문제 설명

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다.
이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 같은 방식으로 결정하려고 합니다.
해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 미션은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다.
단, 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 합니다. 즉, + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,-처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다. 수식에 포함된 연산자가 2개라면 정의할 수 있는 연산자 우선순위 조합은 2! = 2가지이며, 연산자가 3개라면 3! = 6가지 조합이 가능합니다.
만약 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출하며 제출한 숫자가 가장 큰 참가자를 우승자로 선정하며, 우승자가 제출한 숫자를 우승상금으로 지급하게 됩니다.

예를 들어, 참가자 중 네오가 아래와 같은 수식을 전달받았다고 가정합니다.

"100-200*300-500+20"

일반적으로 수학 및 전산학에서 약속된 연산자 우선순위에 따르면 더하기와 빼기는 서로 동등하며 곱하기는 더하기, 빼기에 비해 우선순위가 높아 * > +,- 로 우선순위가 정의되어 있습니다.
대회 규칙에 따라 + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,- 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.
수식에 연산자가 3개 주어졌으므로 가능한 연산자 우선순위 조합은 3! = 6가지이며, 그 중 + > - > * 로 연산자 우선순위를 정한다면 결괏값은 22,000원이 됩니다.
반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60,420 이지만, 규칙에 따라 우승 시 상금은 절댓값인 60,420원이 됩니다.

참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• expression은 길이가 3 이상 100 이하인 문자열입니다.
• expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, -, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.
  • 즉, "402+-561*"처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.
• expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
  • 즉, "100-2145*458+12"처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
  • "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
• expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.
• 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 2^63 - 1 이하가 되도록 입력이 주어집니다.
• 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.

입출력

문제 풀이

이 문제는 연산자의 우선순위를 재설정하여 연산 결과의 최대값을 구하는 문제이다.

그러면 풀이과정으로

1. 연산자의 우선순위 재설정

-> dfs를 활용하여 모든 경우의 수에 대해 연산 진행

2. 연산 결과의 최대값 구하기

-> 연산 결과는 절대값으로 계산!

3. 연산 결과의 범위

-> 연산결과는 최대 2^63 -1 까지다. 이 말은 c++에서 long 의 범위를 의미하는것으로 보인다.

    난 여유있게 long long으로 계산함

4. 사전작업

-> expression을 숫자 백터와 연산자 백터에 따로 담아 두었다.

(연산자 백터는 항상 숫자 백터 크기보다 1개 작다는것을 주의하자)

-> 연산자 백터에서 중복된 연산자를 제외 한후 dfs를 돌려서 순열을 만들어 모든 우선순위를 구한다.

5. 계산하기

-> 연산자 순서대로 계산 후, 처음에 만들었던 숫자백터와 연산자 백터의 크기를 줄여가며 진행한다.

    숫자 백터의 크기가 1 일때 더이상 연산할것이 없으므로 answer 와 절대값 크기비교를 하며 

    모든 경우의 수를 구해본다.

소스 코드

#include <vector>
#include <string>
#include <algorithm>
using namespace std;
bool selected[3];
vector<char> oper3;
void cal(char operation, vector<char>& oper, vector<long long>& numbers, long long& sum)
{
    auto it = find(oper.begin(), oper.end(), operation);
    while(it != oper.end())
    {
        int idx = it - oper.begin();
        if(operation == '*')
        {
            numbers[idx] = numbers[idx] * numbers[idx+1];
        }
        else if(operation == '+')
        {
            numbers[idx] = numbers[idx] + numbers[idx+1];
        }
        else
        {
            numbers[idx] = numbers[idx] - numbers[idx+1];
        }
        numbers.erase(numbers.begin() + idx+1);
        oper.erase(oper.begin() + idx);
        it = find(it, oper.end(), operation);
    }
    if(numbers.size() == 1)
    {
        sum = abs(numbers[0]);
    }
    return;
}
void dfs(int depth, vector<char> oper, vector<char> oper2, vector<int> nums, long long& answer)
{
    if(depth == oper2.size())
    {
        long long sum = 0;
        vector<long long> numbers;
        for(auto a : nums)
            numbers.push_back(a);
        for(int i=0;i<oper3.size();i++)
        {
            cal(oper3[i], oper, numbers, sum);
        }
        answer = max(sum, answer);
        return;
    }
    for(int i=0;i<oper2.size();i++)
    {
        if(selected[i])continue;
        selected[i] = true;
        oper3.push_back(oper2[i]);
        dfs(depth+1, oper, oper2, nums, answer);
        oper3.pop_back();
        selected[i] = false;
    }
}
long long solution(string expression)
{
    long long answer = 0;
    vector<int> nums;
    vector<char> oper;
    string ttmp="";
    for(int i=0;i<expression.size();i++)
    {
        if(expression[i] >='0' && expression[i] <= '9')
        {
            ttmp+= expression[i];
        }
        else
        {
            oper.push_back(expression[i]);
            nums.push_back(stoi(ttmp));
            ttmp="";
        }
    }
    nums.push_back(stoi(ttmp));

    vector<char> oper2;
    for(int i=0;i<oper.size();i++)
    {
        if(find(oper2.begin(), oper2.end(), oper[i]) == oper2.end())
        {
            oper2.push_back(oper[i]);
        }
    }

    dfs(0, oper, oper2, nums, answer);
    return answer;
}

문제 설명

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.         

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• places의 행 길이(대기실 개수) = 5
  • places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
  • places 원소의 길이(대기실 가로 길이) = 5
  • P는 응시자가 앉아있는 자리를 의미합니다.
  • O는 빈 테이블을 의미합니다.
  • X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
• return 값 형식
  • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
  • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

입출력

방향 배열을 설정하여 해당 좌표가 범위를 벗어나지않고 'P'일때 기준으로

위와 같은경우와

다음과 책상을 기준으로 한칸 떨어져있을 경우를 확인하며 배열을 탐색해 보았다.

Version2

처음 이 문제를 풀때는 위와같이 경우의 수를 나누어 코딩을 하였다.

이번엔 자바를 이용해서 문제를 풀다가 다른 분의 코드를 보니 다음과같이 해결하였다.

(y,x) 가 'P' 일때를 보면 거리가 2인것 1인것이 보인다. 다아아몬드 모양인게 모양이 규칙성이 보인다.

-> dfs, bfs가 가능하다고 판단. 페이지 맨 아래 dfs,bfs를 사용한 코드가 있다.

소스 코드

#include <vector>
#include <string>
using namespace std;
int dx1[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int dy1[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy2[4] = { 0, -2, 0, 2 };
int dx2[4] = { -2,0,2,0 };
int dy3[4] = { 0, -1, 0, 1 };
int dx3[4] = { -1,0,1,0 };
int distance(int y1, int x1, int y2, int x2)
{
	return abs(y1 - y2) + abs(x1 - x2);
}
bool solve(vector<string> room)
{
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			if (room[i][j] == 'P')
			{
				for (int k = 0; k < 8; k++)
				{
					int ny = i + dy1[k];
					int nx = j + dx1[k];
					if (ny >= 0 && nx >= 0 && ny < 5 && nx < 5)
					{
						if (room[ny][nx] == 'P')
						{
							if (distance(i, j, ny, nx) == 2)
							{
								//왼위
								if (ny == i - 1 && nx == j - 1)
								{
									if (room[i][nx] != 'X' || room[ny][j] != 'X')
										return false;
								}
								//오위
								else if (ny == i - 1 && nx == j + 1)
								{
									if (room[i][nx] != 'X' || room[ny][j] != 'X')
										return false;
								}
								//왼아
								else if (ny == i + 1 && nx == j - 1)
								{
									if (room[i][nx] != 'X' || room[ny][j] != 'X')
										return false;
								}
								//오아
								else if (ny == i + 1 && nx == j + 1)
								{
									if (room[i][nx] != 'X' || room[ny][j] != 'X')
										return false;
								}
							}
							else
								return false;
						}
					}
				}
				for (int k = 0; k < 4; k++)
				{
					int ny = i + dy2[k]; int ty = i + dy3[k];
					int nx = j + dx2[k]; int tx = j + dx3[k];
					if (ny >= 0 && nx >= 0 && ny < 5 && nx < 5)
					{
						if (room[ny][nx] == 'P')
						{
							if (room[ty][tx] == 'O')
							{
								return false;
							}
						}
					}
				}
			}
		}
	}
	return true;
}
vector<int> solution(vector<vector<string>> places)
{
	vector<int> answer;
	for (int i = 0; i < 5; i++)
	{
		if (solve(places[i]))
		{
			answer.push_back(1);
		}
		else
			answer.push_back(0);
	}

	return answer;
}

///DFS
class Solution
{
    int[] ans;
    boolean[][] visited;
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    public int[] solution(String[][] places)
    {
        ans = new int[places.length];
        for(int i=0;i<places.length;i++)
        {
            ans[i] = 1;
        }
        for(int i=0;i<places.length;i++)
        {
            visited = new boolean[5][5];
            for(int j=0;j<5;j++)
            {
                for(int k=0;k<5;k++)
                {
                    if(places[i][j].charAt(k) == 'P')
                    {
                        visited[j][k] = true;
                        dfs(i,0,j,k,places[i]);
                        visited[j][k] = false;
                    }
                }
            }
        }

        return ans;
    }
    void dfs(int roomNumber, int depth, int y, int x, String[] room)
    {
        if(depth > 2)
            return;
        if(depth > 0 && depth <= 2 && room[y].charAt(x) == 'P')
        {
            ans[roomNumber] = 0;
            return;
        }
        for(int i=0;i<4;i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            //빈칸이거나 사람 있을때만
            if(ny >= 0 && nx >= 0 && ny < 5 && nx < 5 && room[ny].charAt(nx) != 'X')
            {
                if(visited[ny][nx])continue;
                visited[ny][nx] = true;
                dfs(roomNumber, depth+1, ny, nx, room);
                visited[ny][nx] = false;
            }
        }
    }
}

///BFS
import java.util.Queue;
import java.util.LinkedList;
class Solution
{
    int[] ans;
    boolean[][] visited;
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    public int[] solution(String[][] places)
    {
        ans = new int[places.length];
        for(int i=0;i<places.length;i++)
        {
            ans[i] = 1;
        }
        for(int i=0;i<places.length;i++)
        {
            visited = new boolean[5][5];
            for(int j=0;j<5;j++)
            {
                for(int k=0;k<5;k++)
                {
                    if(places[i][j].charAt(k) == 'P')
                    {
                        if(ans[i] == 1)
                            bfs(i,j,k,places[i]);
                    }
                }
            }
        }
        return ans;
    }
    void bfs(int roomNumber, int y, int x, String[] room)
    {
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(y, x, 0));
        visited[y][x] = true;

        while(!q.isEmpty())
        {
            int sy = q.peek().y;
            int sx = q.peek().x;
            int depth = q.peek().depth;
            q.remove();
            if(depth > 2)
                break;
            if(depth >= 1 && depth <=2 && room[sy].charAt(sx) == 'P')
            {
                ans[roomNumber] = 0;
                break;
            }
            for(int i=0;i<4;i++)
            {
                int ny = sy + dy[i];
                int nx = sx + dx[i];
                if(ny >= 0 && nx >=0 && ny < 5 && nx < 5 && room[ny].charAt(nx) != 'X')
                {
                    if(!visited[ny][nx])
                    {
                        visited[ny][nx] = true;
                        q.add(new Pos(ny,nx,depth+1));
                    }
                }
            }
        }
    }
}
class Pos{
    int y,x, depth;
    public Pos(int y, int x, int depth)
    {
        this.y = y;
        this.x = x;
        this.depth =depth;
    }
}