코드메모장

(1) 문제

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어수신 탑(높이)

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

(2) 제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

(3) 코드

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    vector<int> answer_temp;

    string temp = "";

    for (int i = 0; i < operations.size(); i++)
    {    
        temp = operations[i].substr(0,1);
        
        if (temp == "I")
        {
            temp = operations[i].substr(2);
            
            answer_temp.push_back(stoi(temp));
        }
        else if (temp == "D" && !answer_temp.empty())
        {
            temp = operations[i].substr(2, 1);
            sort(answer_temp.begin(), answer_temp.end());
            if (temp == "-")
            {
                answer_temp.erase(answer_temp.begin());
            }
            else
            {
                answer_temp.erase(answer_temp.begin() + answer_temp.size() - 1);
            }
        }   
    }

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

    if (answer_temp.empty())
    {
        answer.push_back(0);
        answer.push_back(0);
    }
    else
    {
        answer.push_back(answer_temp[answer_temp.size() - 1]);
        answer.push_back(answer_temp[0]);
    }

    return answer;
}

(4) 실행결과

(1) 문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

(2) 제한사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

(3) 코드

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int temp = 0;

    priority_queue<int,vector<int>, greater<int>> pq;

    for (int i = 0; i < scoville.size(); i++)
    {
        pq.push(scoville[i]);
    }

    while (true)
    {
        if (pq.top() >= K)
        {
            break;
        }

        temp = pq.top();
        pq.pop();

        temp += pq.top() * 2;
        pq.pop();
        pq.push(temp);

        answer++;

        if (pq.size() == 1 && pq.top() < K)
        {
            return -1;
        }
    }
    return answer;
}

(4) 실행결과

(1) 문제

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

(2) 제한사항

• 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
• 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
• location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

(3) 코드

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

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    int max = 0;
    int current_index;

    queue<int> que;

    for (int i = 0; i < priorities.size(); i++)
    {
        que.push(i);
    }

    max = *max_element(priorities.begin(), priorities.end());

    while (true)
    {
        current_index = que.front();
        que.pop();

        if (priorities[current_index] != max)
        {
            que.push(current_index);
        }

        else// if (priorities[current_index] == max)
        {
            answer++;
            priorities[current_index] = 0;
            if(current_index == location)
            {
                break; 
            }

            max = *max_element(priorities.begin(), priorities.end());
        }
    }

    return answer;
}

(4) 실행결과

(1) 문제

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

(2) 제한사항

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

(3) 코드

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
	int answer = 0;
	vector<pair<int, int>> vec;
	int max_weight = weight;
	int current_weight = 0;

	while (!(truck_weights.empty() && vec.empty()))
	{
		current_weight = 0;
		for (int i = 0; i < vec.size(); i++)
		{
			current_weight += vec[i].second;
		}
		if (!truck_weights.empty())
		{
			if (max_weight >= current_weight + truck_weights[0])
			{
				vec.push_back(make_pair(0, truck_weights[0]));
				truck_weights.erase(truck_weights.begin());
			}
		}		

		for (int i = 0; i < vec.size(); i++)
		{
			vec[i].first++;
		}

		if (vec[0].first == bridge_length)
		{
			current_weight = current_weight - vec[0].second;
			vec.erase(vec.begin());
		}
		answer++;
	}

	return answer + 1;
}

(4) 실행결과

(1) 문제

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

(2) 제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

(3) 코드

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

#define pp pair<string,int>

using namespace std;

bool comp(pair<string, int> a, pair<string, int> b);

vector<int> solution(vector<string> genres, vector<int> plays) {
	vector<int> answer;

	map<string, int> total_play;
	map<int, int> index_plays;
	int max = -1;
	int second_max = -1;

	for (int i = 0; i < genres.size(); i++)
	{
		total_play[genres[i]] += plays[i];
	}

	vector<pair<string, int>> vec(total_play.begin(), total_play.end());

	sort(vec.begin(), vec.end(), comp);

	for (int i = 0; i < vec.size(); i++)
	{
		for (int j = 0; j < genres.size(); j++)
		{
			if (vec[i].first == genres[j])
			{
				if (max == -1)
				{
					max = j;
				}
				else if (plays[j] > plays[max])
				{
					second_max = max;
					max = j;
				}
				else if (plays[j] > plays[second_max])
				{
					second_max = j;
				}
			}
		}
		answer.push_back(max);
		if (second_max != -1)
		{
			answer.push_back(second_max);
		}

		max = -1;
		second_max = -1;
	}

	return answer;
}

bool comp(pair<string, int> a, pair<string, int> b)
{
	return a.second > b.second;
}

(4) 실행결과

(1) 문제

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류이름

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

(2) 제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

(3) 코드

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;

    map<string, int> m;

	for (int i = 0; i < clothes.size(); i++)
	{
        m[clothes[i][1]]++;
	}

    for (auto it = m.begin(); it != m.end(); it++)
    {
        answer *= (it->second + 1);
    }

    answer--;

    return answer;
}

(4) 실행결과

(1) 문제

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

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

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

(2) 제한사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

(3) 코드

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

using namespace std;
bool comp(string a, string b);
bool solution(vector<string> phone_book) {
    bool answer = true;

    sort(phone_book.begin(), phone_book.end(), comp);

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

    return answer;
}

bool comp(string a, string b)
{
    if (a.length() < b.length())
    {
        return true;
    }
    else if (a.length() == b.length())
    {
        return a < b;
    }
    else
        return false;
}

(4) 실행결과

(1) 문제

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

(2) 제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

(3) 코드

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

using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 1;
    int n_end = 0;

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

    for (int i = 0; i < routes.size(); i++)
    {
        if (n_end > routes.at(i).at(1))
        {
            n_end = routes.at(i).at(1);
        }

        if (routes.at(i).at(0) > n_end)
        {
            answer++;
            n_end = routes.at(i).at(1);
        }
        
    }

    return answer;
}

(4) 실행결과

(1) 문제

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

(2) 제한사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

(3) 코드

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    
    int begin = 0;
    int end = people.size() - 1;

    while (begin <= end)
    {
        if (people.at(begin) + people.at(end) > limit)
        {
            answer++;
            end--;            
        }
        else
        {
            answer++;
            end--;
            begin++;            
        }
    }    

    return answer;
}

(4) 실행결과

(1) 문제

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

(2) 제한사항

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

(3) 코드

#include <iostream>
#include <string>
 
using namespace std;
 
string solution(string number, int k) {
    string answer = "";
    for (int j = 0, index = -1; j < number.length() - k; j++) {
        char max = 0;
        for (int i = index + 1; i <= k + j; i++) {
            if (max < number[i]) {
                index = i;
                max = number[i];
            }
        }
        answer += max;
    }
    return answer;
}

(4) 실행결과