아래 모든 문제들은 프로그래머스에서 제공 되는 문제를 이용하였습니다, 감사합니다.

• 모두 풀었음.

1. 단체사진 찍기

문제 설명

가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다. 사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다. 각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.

입력 형식

입력은 조건의 개수를 나타내는 정수 n과 n개의 원소로 구성된 문자열 배열 data로 주어진다. data의 원소는 각 프렌즈가 원하는 조건이 N~F=0과 같은 형태의 문자열로 구성되어 있다. 제한조건은 아래와 같다.

• 1 <= n <= 100

• data의 원소는 다섯 글자로 구성된 문자열이다. 각 원소의 조건은 다음과 같다.

• 첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다. {A, C, F, J, M, N, R, T} 각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다. 첫 번째 글자는 조건을 제시한 프렌즈, 세 번째 글자는 상대방이다. 첫 번째 글자와 세 번째 글자는 항상 다르다.

• 두 번째 글자는 항상 ~이다.

• 네 번째 글자는 다음 3개 중 하나이다. {=, <, >} 각각 같음, 미만, 초과를 의미한다.

• 다섯 번째 글자는 0 이상 6 이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.
  출력 형식

• 모든 조건을 만족하는 경우의 수를 리턴한다.

예제 입출력

풀이

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

void swap (char &a, char &b)
{
    char tmp = a;
    a = b;
    b = tmp;
}
void permutation(vector<char> &charactor, int depth, int n, vector<string> data, int *answer)
{
    if (depth == n)
    {
        int flag = 0;
        for (int i = 0; i < data.size(); i++)
        {

            auto a = find(charactor.begin(), charactor.end(), data[i][0]);
            auto b = find(charactor.begin(), charactor.end(), data[i][2]);
            if (data[i][3] == '=')
            {
                if ((abs(a - b) - 1) != data[i][4] - '0')
                {
                    flag = -1;
                    break;
                }
            }
            else if(data[i][3] == '>')
            {
                if ((abs(a - b) - 1) <= data[i][4] - '0')
                {
                    flag = -1;
                    break;
                }
            }
            else if(data[i][3] == '<')
            {
                if ((abs(a - b) - 1) >= data[i][4] - '0')
                {
                    flag = -1;
                    break;
                }
            }
        }
        if (flag == 0)
            (*answer)++;
        return;
    }
    for (int i = depth; i < n; i++)
    {
        swap(charactor[depth], charactor[i]);
        permutation(charactor, depth + 1, n, data, answer);
        swap(charactor[depth], charactor[i]);
    }

}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    vector<char> charactor = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    int answer = 0;
    permutation(charactor, 0, charactor.size(), data, &answer);

    return answer;
}

설명

{'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'}

• 문제에서 사진찍는 캐릭터들을 준다.
• 이 배열들이 찍을수 있는 모든 경우의수를 구해주어야하므로 나올수 있는 모든 조합을 구해주어야한다.
• 어차피 모든 조합을 다 찾아 볼거니까 bfs나 dfs상관없다.
• 그리고 데이터로 주는 조건들이 맞는지 비교해보고 맞으면 answer++을 해주었다.

2. 튜플

문제 설명

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

• (a1, a2, a3, ..., an)

  튜플은 다음과 같은 성질을 가지고 있습니다.

• 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)

• 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)

• 튜플의 원소 개수는 유한합니다.

  원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

• {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

  예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

  와 같이 표현할 수 있습니다. 이때, 집합은 원소의 순서가 바뀌어도 상관없으므로

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

• {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}

• {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

  는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• s의 길이는 5 이상 1,000,000 이하입니다.
• s는 숫자와 '{', '}', ',' 로만 이루어져 있습니다.
• 숫자가 0으로 시작하는 경우는 없습니다.
• s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.
• s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.
• return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다.

[입출력 예]

풀이

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

vector<int> solution(string s) {
    int j;
    vector<int> answer;
    string tmp;
    vector<vector<int>> value_save;

    for(int i = 0; i < s.size(); i++)
    {
        if(isdigit(s[i]))
        {
            tmp = s[i];
            for(j = 1; isdigit(s[i + j]); j++)
                tmp += s[i + j];
            if(tmp.size() != 1)
                i = i + j - 1;
            answer.push_back(stoi(tmp));
        }
        else if(s[i] == '}' && answer.size() != 0)
        {
            value_save.push_back(answer);
            answer.clear();
        }
    } // 문자열 2중 벡터로 만들기.
    sort(value_save.begin(), value_save.end(), [](vector<int> &a, vector<int> &b){
        return a.size() < b.size();
    });
    for(int i = 0; i < value_save.size(); i++)
    {
        for(int j = 0; j < value_save[i].size(); j++)
             if(answer.end() == find(answer.begin(), answer.end(), value_save[i][j]))
                 answer.push_back(value_save[i][j]);
    }
    return answer;
}

설명

• s로 정렬되지 않는 배열이 주어지는데, 이 배열을 사이즈 별로 정렬한다.
• 사이즈가 작은거는 앞에 오는것들이 모여있고, 클수록 무작위한 정렬일 가능성이 크다.
• 고로 앞에서 부터 원래 순서인 값들을 구하고 뒤에값들도 하나씩맞추어 가면된다.
• sort만 잘해주면 쉽게 풀리는 문제엿다.
• 아 문자열로 입력이 주어지는데 이걸 split 해줄려고 flag = '}'을 사용했다. 접근만 잘하면 쉬운 문제.

3. 올바른 괄호

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

  '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

입출력 예

풀이

#include<string>
#include <iostream>

using namespace std;

bool solution(string s)
{
    bool answer = true;
    int sum = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '(')
            sum++;
        else if (s[i] == ')')
            sum--;
        if (sum < 0)
            return false;
    }
    if (sum > 0)
        return false;
    return answer;
}

설명

• 생략

4. 다음 큰 숫자

문제 설명

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

• 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
• 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
• 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.

  예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

제한 사항

• n은 1,000,000 이하의 자연수 입니다.

입출력 예

풀이

using namespace std;

int tow(int n)
{
    int count = 0;
    while(n)
    {
        if(1 == (n % 2))
           count++;
        n = n / 2;
    }
    return count;
}

int solution(int n) {
    int save = tow(n);
    while(1)
        if(tow(++n) == save)
            return n;
    return n;
}

설명

• 이 문제는 라이브코딩(스터디 동료들이 보는앞에서 최대한 빠르게 코드를 작성하는거. 일명 공개처형이다.)을 햇다.
• 그냥 입력값을 1씩 증가하면서 처음 입력값과 이진수로 바꾸었을떄 1의 값의 개수가 같을떄 반환시킨다.