IT 공부방

https://school.programmers.co.kr/learn/courses/30/lessons/92335

※ 문제

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  • 예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

※ 나의 풀이

뭔가 카카오 문제치고는 쉬웠다고 생각이 들었다.

그런데 코어 덤프가 떴다 ㅠㅠ

그래서 int를 long long으로 변경해주었다.

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

using namespace std;

typedef long long ll;

string change_num(int n, int k)
{
    string out;
    while (n)
    {
        out += to_string(n % k);
        n /= k;
    }

    reverse(out.begin(), out.end());
    return out;
}

vector<string> divide_num(string num)
{
    vector<string> out;
    string tmp = "";

    for (int i = 0; i < num.size(); i++)
    {
        if (num[i] == '0' && tmp != "")
        {
            if (tmp != "1")
            {
                out.push_back(tmp);
            }
            tmp = "";
        }
        else  // num[i] != '0'
        {
            tmp += num[i];
        }
    }

    if (!tmp.empty()) out.push_back(tmp);

    return out;
}

bool check_answer(ll num)
{
    if (num < 2) return false;

    for (int i = 2; i <= sqrt(num); i++)
    {
        if (num % i == 0) return false;
    }

    return true;
}

int solution(int n, int k) {
    int answer = 0;
    
    // k 진수로 바꿔주기
    string num = change_num(n, k);

    // 0을 기준으로 값 나눠주기
    vector<string> divi_num = divide_num(num);

    // 소수 판단하기
    for (int i = 0; i < divi_num.size(); i++)
    {
        ll num = stol(divi_num[i]);
        if (check_answer(num)) answer++;
    }
    
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/92341

※ 문제

주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 아래는 하나의 예시를 나타냅니다.

• 어떤 차량이 입차된 후에 출차된 내역이 없다면, 23:59에 출차된 것으로 간주합니다.
  • 0000번 차량은 18:59에 입차된 이후, 출차된 내역이 없습니다. 따라서, 23:59에 출차된 것으로 간주합니다.
• 00:00부터 23:59까지의 입/출차 내역을 바탕으로 차량별 누적 주차 시간을 계산하여 요금을 일괄로 정산합니다.
• 누적 주차 시간이 기본 시간이하라면, 기본 요금을 청구합니다.
• 누적 주차 시간이 기본 시간을 초과하면, 기본 요금에 더해서, 초과한 시간에 대해서 단위 시간 마다 단위 요금을 청구합니다.
  • 초과한 시간이 단위 시간으로 나누어 떨어지지 않으면, 올림합니다.
  • ⌈a⌉ : a보다 작지 않은 최소의 정수를 의미합니다. 즉, 올림을 의미합니다.

주차 요금을 나타내는 정수 배열 fees, 자동차의 입/출차 내역을 나타내는 문자열 배열 records가 매개변수로 주어집니다. 차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

※ 나의 풀이

그냥 구현문제로 생각이 된다.

중요하다고 생각되는 점은 차량마다의 주차장 이용시간을 정리할때 map을 이용하는 것.

#include <string>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <cmath>

using namespace std;

vector<int> solution(vector<int> fees, vector<string> records) {
    vector<int> answer;
    
    // 정리하기
    map<int, queue<pair<string, int>>> ch;
    for (int i = 0; i < records.size(); i++)
    {
        int time = stoi(records[i].substr(0, 2)) * 60 + stoi(records[i].substr(3, 2));
        int car_num = stoi(records[i].substr(6, 4));
        string in_out = records[i].substr(11, -1);

        ch[car_num].push(make_pair(in_out, time));
    }

    // 정리된 records로 계산하기
    auto iter = ch.begin();
    while (iter != ch.end())
    {
        int tmp = 0;
        int start = 0;
        int end = 0;
        int total_time = 0;
        while (!(iter->second.empty()))
        {
            string status = iter->second.front().first;
            if (status == "IN" && iter->second.size() != 1)
            {
                start = iter->second.front().second;
                iter->second.pop();
                continue;
            }
            else  if (status == "OUT")
            {
                end = iter->second.front().second;
                total_time += end - start;
                start = 0;
                end = 0;
                iter->second.pop();
            }
            else if(status == "IN")
            {
                start = iter->second.front().second;
                total_time += (1439 - start);
                iter->second.pop();
            }
        }
        if (total_time <= fees[0])
        {
            answer.push_back(fees[1]);
        }
        else  // total_time > fees[0]
        {
            float tmp_time = total_time - fees[0];
            answer.push_back(fees[1] + ceil(tmp_time / fees[2]) * fees[3]);
        }

        iter++;
    }
    
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/92342

※ 문제

카카오배 양궁대회가 열렸습니다.
라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다.
카카오배 양궁대회 운영위원회는 한 선수의 연속 우승보다는 다양한 선수들이 양궁대회에서 우승하기를 원합니다. 따라서, 양궁대회 운영위원회는 결승전 규칙을 전 대회 우승자인 라이언에게 불리하게 다음과 같이 정했습니다.

1. 어피치가 화살 n발을 다 쏜 후에 라이언이 화살 n발을 쏩니다.
2. 점수를 계산합니다.
   1. 과녁판은 아래 사진처럼 생겼으며 가장 작은 원의 과녁 점수는 10점이고 가장 큰 원의 바깥쪽은 과녁 점수가 0점입니다. 
   2. 만약, k(k는 1~10사이의 자연수)점을 어피치가 a발을 맞혔고 라이언이 b발을 맞혔을 경우 더 많은 화살을 k점에 맞힌 선수가 k 점을 가져갑니다. 단, a = b일 경우는 어피치가 k점을 가져갑니다. k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져가는 게 아니고 k점만 가져가는 것을 유의하세요. 또한 a = b = 0 인 경우, 즉, 라이언과 어피치 모두 k점에 단 하나의 화살도 맞히지 못한 경우는 어느 누구도 k점을 가져가지 않습니다.
      1. 예를 들어, 어피치가 10점을 2발 맞혔고 라이언도 10점을 2발 맞혔을 경우 어피치가 10점을 가져갑니다.
      2. 다른 예로, 어피치가 10점을 0발 맞혔고 라이언이 10점을 2발 맞혔을 경우 라이언이 10점을 가져갑니다.
   3. 모든 과녁 점수에 대하여 각 선수의 최종 점수를 계산합니다.
3. 최종 점수가 더 높은 선수를 우승자로 결정합니다. 단, 최종 점수가 같을 경우 어피치를 우승자로 결정합니다.

현재 상황은 어피치가 화살 n발을 다 쏜 후이고 라이언이 화살을 쏠 차례입니다.
라이언은 어피치를 가장 큰 점수 차이로 이기기 위해서 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 구하려고 합니다.

화살의 개수를 담은 자연수 n, 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열 info가 매개변수로 주어집니다. 이때, 라이언이 가장 큰 점수 차이로 우승하기 위해 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 만약, 라이언이 우승할 수 없는 경우(무조건 지거나 비기는 경우)는 [-1]을 return 해주세요.

※ 나의 풀이

일단 DFS로 접근했지만... 시간초과가 떴다.

결국 풀이를 참고하여 접근해보기로 했다.

풀이하시는 분들을 보면 굉장히 똑똑하신거 같다.

나는 화살 한방 한방을 count해서 진행했지만.

아래 코드는 점수별로 진행을 해주었다.

조금 다른 시각을 가지는 노력을 해야겠다.

#include <string>
#include <vector>

using namespace std;
vector<int> answer(1,-1);
int maxDiff = 0;

bool cmp(vector<int> ryan) {
    
    for(int i = 10; i >= 0; i--) {
        if(ryan[i] > answer[i]) return true;
        else if (ryan[i] < answer[i]) return false;
    }
}

void calcScore(vector<int> ryan, vector<int> apeach) {
    int ryanScore = 0;
    int apeachScore = 0;
    
    for(int i = 0; i < 11; i++) {
        if(ryan[i] > apeach[i]) ryanScore += 10 - i;
        else if(apeach[i] > 0) apeachScore += 10 - i;
    }
    
    int diff = ryanScore - apeachScore;
    if(diff > 0 && maxDiff <= diff) {
        if(maxDiff == diff && !cmp(ryan)) return;
        maxDiff = diff;
        answer = ryan;
    }
}


void solve(int idx, int arrows, vector<int> ryan, vector<int> apeach) {
    if(idx==11 || arrows == 0) { //분배 끝 
        ryan[10] += arrows;
        calcScore(ryan, apeach);
        ryan[10] -= arrows;
        return;
    }
    if(apeach[idx] < arrows) {
        ryan[idx] += apeach[idx] +1;
        solve(idx+1, arrows-apeach[idx]-1, ryan,apeach);
        ryan[idx] -= apeach[idx] +1;
    }
    solve(idx+1, arrows, ryan, apeach);
}

vector<int> solution(int n, vector<int> info) {
    vector<int> ryan(11,0);
    
    solve(0,n, ryan, info);

    if(answer.empty()) answer.push_back(-1);
    
    return answer;
}

※ 시간초과 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int n = 0;
int lion_sum_tmp = 0;
vector<int> info;
vector<int> answer;

void sum_check(int& lion_sum, int& apeach_sum, vector<int> lion_info)
{
    for (int i = 0; i < info.size(); i++)
    {
        if (info[i] >= lion_info[i] && info[i] != 0) apeach_sum += (10 - i);
        else if (info[i] < lion_info[i]) lion_sum += (10 - i);
    }
}

void DFS(int cnt, vector<int>& lion_info)
{
    if (cnt >= n)
    {
        int lion_sum = 0, apeach_sum = 0;
        sum_check(lion_sum, apeach_sum, lion_info);
        if (lion_sum > apeach_sum)
        {
            int lion_apeach = lion_sum - apeach_sum;
            if (lion_apeach > lion_sum_tmp)
            {
                answer = lion_info;
                lion_sum_tmp = lion_apeach;
            }
            else if (lion_apeach == lion_sum_tmp)
            {
                for (int i = lion_info.size() - 1; i >= 0; i--)
                {
                    if (answer[i] < lion_info[i])
                    {
                        answer = lion_info;
                        break;
                    }
                }
            }
        }
    }
    else
    {
        for (int i = 0; i < lion_info.size(); i++)
        {
            if (lion_info[i] > info[i]) continue;   // 이미 lion이 점수 획득 가능한건 PASS
            lion_info[i]++;
            DFS(cnt + 1, lion_info);
            lion_info[i]--;
        }
    }
}

vector<int> solution(int r_n, vector<int> r_info) {
    n = r_n;
    info = r_info;
    
    // DFS로 접근...?
    // 체크벡터, 저장해줄 벡터(answer)
    vector<int> lion_info(info.size(), 0);

    // count, lion_info
    DFS(0, lion_info);

    // 못 이길때
    if (answer.size() == 0) answer.push_back(-1);
    
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/118667

※ 문제

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.

다음은 두 큐를 나타내는 예시입니다.

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]
두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.

1. queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.

2. queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다.

따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.
길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

※ 나의 풀이

테스트 케이스 몇개 때문에 정말 시간을 많이 날렸다.

처음에는 while (que1_sum != que2_sum) 이렇게 진행했는데 시간초과가 몇개 발생했다...

적정 값을 찾다가 결국 질문하기를 봤다 ㅠㅠ

정확히 적정값에 관한 내용은 없었고 60만으로 설정하면 통과된다고 했다...

진짜 왜 60만이 적당한지 아시는 분은 댓글 부탁드립니다 ㅠㅠ

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    
    // queue로 옮겨주기, 전체 합 구하기
    long long total_sum = 0;
    long long que1_sum = 0, que2_sum = 0;
    queue<int> que1;
    queue<int> que2;
    for (int i = 0; i < queue1.size(); i++)
    {
        que1.push(queue1[i]);
        que2.push(queue2[i]);

        que1_sum += queue1[i];
        que2_sum += queue2[i];
        total_sum += (queue1[i] + queue2[i]);
    }

    // 체크해주기!
    if (total_sum % 2 != 0) return -1;

    // while (que1_sum != que2_sum)
    for(int i = 0; i < 600000; i++)
    {
        if (que1.empty() || que2.empty())
        {
            answer = -1;
            break;
        }

        if (que1_sum > que2_sum)
        {
            que1_sum -= que1.front();
            que2_sum += que1.front();
            que2.push(que1.front());
            que1.pop();
            answer++;
        }
        else if (que1_sum < que2_sum)
        {
            que2_sum -= que2.front();
            que1_sum += que2.front();
            que1.push(que2.front());
            que2.pop();
            answer++;
        }
    }
    if(answer == 600000) answer = -1;
    
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/131127

※ 문제

XYZ 마트는 일정한 금액을 지불하면 10일 동안 회원 자격을 부여합니다. XYZ 마트에서는 회원을 대상으로 매일 한 가지 제품을 할인하는 행사를 합니다. 할인하는 제품은 하루에 하나씩만 구매할 수 있습니다. 알뜰한 정현이는 자신이 원하는 제품과 수량이 할인하는 날짜와 10일 연속으로 일치할 경우에 맞춰서 회원가입을 하려 합니다.

예를 들어, 정현이가 원하는 제품이 바나나 3개, 사과 2개, 쌀 2개, 돼지고기 2개, 냄비 1개이며, XYZ 마트에서 15일간 회원을 대상으로 할인하는 제품이 날짜 순서대로 치킨, 사과, 사과, 바나나, 쌀, 사과, 돼지고기, 바나나, 돼지고기, 쌀, 냄비, 바나나, 사과, 바나나인 경우에 대해 알아봅시다. 첫째 날부터 열흘 간에는 냄비가 할인하지 않기 때문에 첫째 날에는 회원가입을 하지 않습니다. 둘째 날부터 열흘 간에는 바나나를 원하는 만큼 할인구매할 수 없기 때문에 둘째 날에도 회원가입을 하지 않습니다. 셋째 날, 넷째 날, 다섯째 날부터 각각 열흘은 원하는 제품과 수량이 일치하기 때문에 셋 중 하루에 회원가입을 하려 합니다.

정현이가 원하는 제품을 나타내는 문자열 배열 want와 정현이가 원하는 제품의 수량을 나타내는 정수 배열 number, XYZ 마트에서 할인하는 제품을 나타내는 문자열 배열 discount가 주어졌을 때, 회원등록시 정현이가 원하는 제품을 모두 할인 받을 수 있는 회원등록 날짜의 총 일수를 return 하는 solution 함수를 완성하시오. 가능한 날이 없으면 0을 return 합니다.

※ 나의 풀이

딱히 크게 어려운 부분이 없다.

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    
    // want 정리해주기
    int wants_total = 0;
    map<string, int> ch_wants;
    for (int i = 0; i < want.size(); i++)
    {
        wants_total += number[i];
        ch_wants.insert(make_pair(want[i], number[i]));
    }

    // Check 해주기
    int copy_total = 0;
    bool flag = true;
    map<string, int> copy_ch;
    for (int i = 0; i <= discount.size() - wants_total; i++)
    {
        copy_total = wants_total;
        flag = true;
        copy_ch = ch_wants;
        for (int j = i; j < i + wants_total; j++)
        {
            string item = discount[j];
            if (copy_ch[item] == 0)
            {
                flag = false;
                break;
            }
            else
            {
                copy_total--;
                copy_ch[item]--;
            }
        }
        if (flag && copy_total == 0) answer++;
    }
    
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/131130

※ 문제

혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다.

숫자 카드 더미에는 카드가 총 100장 있으며, 각 카드에는 1부터 100까지 숫자가 하나씩 적혀있습니다. 2 이상 100 이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비하고, 준비한 카드의 수만큼 작은 상자를 준비하면 게임을 시작할 수 있으며 게임 방법은 다음과 같습니다.

준비된 상자에 카드를 한 장씩 넣고, 상자를 무작위로 섞어 일렬로 나열합니다. 상자가 일렬로 나열되면 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙입니다.

그 다음 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다. 다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다. 마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다.

이렇게 연 상자들은 1번 상자 그룹입니다. 이제 1번 상자 그룹을 다른 상자들과 섞이지 않도록 따로 둡니다. 만약 1번 상자 그룹을 제외하고 남는 상자가 없으면 그대로 게임이 종료되며, 이때 획득하는 점수는 0점입니다.

그렇지 않다면 남은 상자 중 다시 임의의 상자 하나를 골라 같은 방식으로 이미 열려있는 상자를 만날 때까지 상자를 엽니다. 이렇게 연 상자들은 2번 상자 그룹입니다.

1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값이 게임의 점수입니다.

상자 안에 들어있는 카드 번호가 순서대로 담긴 배열 cards가 매개변수로 주어질 때, 범희가 이 게임에서 얻을 수 있는 최고 점수를 구해서 return 하도록 solution 함수를 완성해주세요.

※ 나의 풀이

이 문제는 설명만 길었지 그렇게 어렵지 않은 문제였다.

생각한 걸 구현만 할 수 있으면 될 것 같다.

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

using namespace std;

int solution(vector<int> cards) {
    int answer = 0;
    
    // 임의의 상자 인덱스
    int idx = 0;

    // 뽑았는지 안뽑았는지 체크하는 변수
    vector<bool> ch_box(cards.size(), true);

    // count 변수 및 사이즈 저장
    int cnt = 0;
    vector<int> cnt_size;

    // 체크해주기
    for (int i = 0; i < cards.size(); i++)
    {
        if (ch_box[idx])
        {
            ch_box[idx] = false;
            idx = cards[idx] - 1;
            cnt++;
            if (i == cards.size() - 1)
            {
                cnt_size.push_back(cnt);
            }
        }
        else  // ch_box[idx] = false
        {
            i--;
            cnt_size.push_back(cnt);
            cnt = 0;
            for (int j = 0; j < ch_box.size(); j++)
            {
                if (ch_box[j])
                {
                    idx = j;
                    break;
                }
            }
        }
    }

    sort(cnt_size.begin(), cnt_size.end());

    answer = cnt_size[cnt_size.size() - 1] * cnt_size[cnt_size.size() - 2];
    
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/131701

※ 문제

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

※ 나의 풀이

원형 수열은 처음봤다.

그래서 고민하다가 힌트를 봤다.

결론은 elements 배열을 복사해서 합쳐준다.

예를 들면, {1, 2, 3}의 elements 배열이 있다고 가정한다면, {1, 2, 3, 1, 2, 3} 배열로 만들어 준다.

그리고 투포인트를 활용하여 모든 경우의 수를 계산해준다.

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<int> elements) {
    int answer = 0;
    
    // 원형 수열 1d로 만들어주기
    vector<int> two_elements(elements);
    two_elements.insert(two_elements.end(), elements.begin(), elements.end() - 1);

    // Check List
    map<int, int> ch_elements;

    // 일일이 구해주기
    for (int i = 0; i < elements.size(); i++)
    {
        int sum = 0;
        for (int j = i; j < i + elements.size(); j++)
        {
            sum += two_elements[j];
            if (ch_elements[sum] == 0) answer++;
            ch_elements[sum]++;
        }
    }
    
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/131704

※ 문제

영재는 택배상자를 트럭에 싣는 일을 합니다. 영재가 실어야 하는 택배상자는 크기가 모두 같으며 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달됩니다. 컨테이너 벨트는 한 방향으로만 진행이 가능해서 벨트에 놓인 순서대로(1번 상자부터) 상자를 내릴 수 있습니다. 하지만 컨테이너 벨트에 놓인 순서대로 택배상자를 내려 바로 트럭에 싣게 되면 택배 기사님이 배달하는 순서와 택배상자가 실려 있는 순서가 맞지 않아 배달에 차질이 생깁니다. 따라서 택배 기사님이 미리 알려준 순서에 맞게 영재가 택배상자를 실어야 합니다.

만약 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 트럭에 실을 순서가 될 때까지 잠시 다른 곳에 보관해야 합니다. 하지만 고객의 물건을 함부로 땅에 둘 수 없어 보조 컨테이너 벨트를 추가로 설치하였습니다. 보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다). 보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않습니다.

예를 들어, 영재가 5개의 상자를 실어야 하며, 택배 기사님이 알려준 순서가 기존의 컨테이너 벨트에 네 번째, 세 번째, 첫 번째, 두 번째, 다섯 번째 놓인 택배상자 순서인 경우, 영재는 우선 첫 번째, 두 번째, 세 번째 상자를 보조 컨테이너 벨트에 보관합니다. 그 후 네 번째 상자를 트럭에 싣고 보조 컨테이너 벨트에서 세 번째 상자 빼서 트럭에싣습니다. 다음으로 첫 번째 상자를 실어야 하지만 보조 컨테이너 벨트에서는 두 번째 상자를, 기존의 컨테이너 벨트에는 다섯 번째 상자를 꺼낼 수 있기 때문에 더이상의 상자는 실을 수 없습니다. 따라서 트럭에는 2개의 상자만 실리게 됩니다.

택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 영재가 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.

※ 나의 풀이

이 문제는 그렇게 어렵지 않게 풀었다.

보조 컨테이너를 보관할 변수를 stack으로 해야하는 것 외에는 어려운건 없었다.

하지만 처음 풀이 코드가 너무 지저분했다.

그래서 문제를 푼 후에 코드를 정리해보았다.

처음코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    
    int order_idx = 0;
    stack<int> sub_container;
    for (int i = 1; i <= order.size(); i++)
    {
        int order_num = order[order_idx];
        if (order_num == i)
        {
            order_idx++;
            answer++;
        }
        else  // order_num != i
        {
            sub_container.push(i);
        }

        order_num = order[order_idx];
        while (!sub_container.empty() && sub_container.top() == order_num)
        {
            sub_container.pop();
            answer++;
            order_idx++;
            if (order_idx >= order.size()) break;
            order_num = order[order_idx];
        }
    }
    
    return answer;
}

정리한 코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    
    int order_idx = 0;
    stack<int> sub_container;
    for (int i = 1; i <= order.size(); i++)
    {
        int order_num = order[order_idx];
        sub_container.push(i);
        while (!sub_container.empty() && sub_container.top() == order_num)
        {
            sub_container.pop();
            answer++;
            order_idx++;
            if (order_idx >= order.size()) break;
            order_num = order[order_idx];
        }
    }
    
    return answer;
}