프로그래머스 코딩테스트 고득점 Kit ( 쉽게, 깔끔하게, 시간복잡도가 좋게 )
카테고리: Algorithm
Chapter 01 해시
01-1 폰켓몬
- 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다
- 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다
- 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다
- 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다
- 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다
- 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
- 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
- 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
- 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
- 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
- 세 번째(2번), 네 번째(3번) 폰켓몬을 선택
- 이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다
- 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다
- 당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다
- N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요
#include <vector>
#include <unordered_map>
using namespace std;
int solution(vector<int> nums)
{
int answer = 0;
unordered_map<int, int> mMonster;
int iCount = nums.size();
// 몬스터가 종류별로 몇개가 있는지 분류한다
for(int i = 0; i < iCount; ++i)
{
mMonster[nums[i]] = mMonster[nums[i]] + 1;
}
// 몬스터 종류의 최대 갯수를 구한다
int iMax = mMonster.size();
// 문제에서 N/2마리 까지 몬스터를 가질수 있다고 했으니 이를 초과하지 못하게 방지한다
if(nums.size()/2 < iMax)
answer = nums.size()/2;
else
answer = iMax;
return answer;
}
01-2 완주하지 못한 선수
- 수많은 마라톤 선수들이 마라톤에 참여하였습니다
- 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다
- 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요
#include<bits/stdc++.h>
using namespace std;
string solution(vector<string> participant, vector<string> completion)
{
string answer = "";
// 맵은 중복키 허용하지 않는다
unordered_map<string, int> mListCount;
// 해당하는 이름의 value를 증가시킨다
for (auto name : completion)
{
mListCount[name] = mListCount[name] + 1;
}
// 해당하는 이름의 value를 감소시킨다
for (auto name : participant)
{
mListCount[name] = mListCount[name] - 1;
// 해당하는 이름이 음수가 되면 완주하지 못한 애다
if (mListCount[name] < 0)
answer = name;
}
return answer;
}
01-3 전화번호 목록
- 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다
- 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다
- 구조대 : 119
- 박준영 : 97 674 223
- 지영석 : 11 9552 4421
- 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
bool solution(vector<string> phone_book)
{
// phoneBook 배열을 정렬한다
sort(phone_book.begin(), phone_book.end());
// 1중 Loop을 돌며 앞 번호가 뒷 번호의 접두어인지 확인한다
for (int i = 0; i < phone_book.size() - 1; i++)
if (phone_book[i + 1].find(phone_book[i]) == 0)
return false;
// 여기까지 오면 접두어가 없다는 것이다
return true;
}
01-4 위장
- 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다
- 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다
- 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int solution(vector<vector<string>> clothes)
{
int answer = 1;
unordered_map<string, int> mClothes;
// 모든 종류를 체크한다
for(auto cloth : clothes)
{
mClothes[cloth[1]] = mClothes[cloth[1]] + 1;
}
// 만약, 상의 3개, 하의 2개, 장신구 2개가 있었다고 가정하면, 총 가능한 경우의 수는 (3+1) * (2+1) * (2+1) = 36가지 이다
// 참고로 (3+1) * (2+1) * (2+1) = 36가지 에서 +1은 선택 안함에 해당하는 경우의 수이다 ( 트리 구조로 그림을 그려보자 )
for(auto it = mClothes.begin(); it != mClothes.end(); it++)
{
answer = answer * (it->second + 1);
}
// 그런데, 이 경우에는 (상의 선택 안 함, 하의 선택 안 함, 장신구 선택 안 함)이 포함되어 있으므로 그 경우를 빼주는 것이다
// 덧 붙이자면, 문제의 제한사항에 스파이는 하루에 최소 한 개의 의상은 입습니다 라고 했다
return answer - 1;
}
01-5 베스트앨범
- 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다
- 속한 노래가 많이 재생된 장르를 먼저 수록합니다
- 장르 내에서 많이 재생된 노래를 먼저 수록합니다
- 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다
- 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요
#include <string>
#include <vector>
#include <map>
using namespace std;
vector<int> solution(vector<string> genres, vector<int> plays)
{
// 여기에 고유번호 저장
vector<int> answer;
//각 장르별로 횟수저장
map<string, int> music;
//각 장르별로 무슨노래가 몇번씩 저장 되었는지
map<string, map<int, int>> musiclist;
//들어온 리스트만큼 반복
for (int i = 0; i < genres.size(); i++)
{
//music map에 장르별로 횟수추가
music[genres[i]] += plays[i];
//musiclist map에 노래번호와 플레이횟수 추가
musiclist[genres[i]][i] = plays[i];
}
//장르가 다없어질때까지 반복
while (music.size() > 0)
{
string genre{};
int max{0};
//장르중에서 제일높은것 찾기
for (auto mu : music)
{
if (max < mu.second)
{
max = mu.second;
genre = mu.first;
}
}
//2곡을 넣어야하므로 2번반복
for (int i = 0; i < 2; i++)
{
int val = 0, ind = -1;
//노래중에서 제일높은것 찾기
for (auto ml : musiclist[genre])
{
if (val < ml.second)
{
val = ml.second;
ind = ml.first;
}
}
//만약 노래가 0~1곡밖에없다면 반복문 탈출
if (ind == -1) break;
//리턴할 리스트에 노래번호 추가
answer.push_back(ind);
musiclist[genre].erase(ind);
}
//map 에서 사용한 장르삭제
music.erase(genre);
}
return answer;
}
Chapter 02 스택/큐
02-1 같은 숫자는 싫어
- 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다
- 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다
- 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다
- 예를 들면, arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다
- arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다
- 배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요
#include <vector>
#include <iostream>
using namespace std;
vector<int> solution(vector<int> arr)
{
vector<int> answer;
answer.push_back(arr[0]);
for (auto num : arr)
{
if (answer.back() != num)
answer.push_back(num);
}
return answer;
}
#include <vector>
#include <iostream>
using namespace std;
vector<int> solution(vector<int> arr)
{
vector<int> answer;
// 첫번째 숫자는 이전값과 비교할 수 없으니 무조건 넣어준다
answer.push_back(arr[0]);
for(int i = answer.size(); i < arr.size(); ++i)
{
// 두번째 숫자 부터는 이전값과 비교하여 다르면 넣는다
if(arr[i-1] != arr[i])
{
answer.push_back(arr[i]);
}
}
return answer;
}
02-2 기능개발
- 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다
- 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다
- 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요
#include <string>
#include <vector>
#include <queue>
using namespace std;
vector<int> solution(vector<int> progresses, vector<int> speeds)
{
// 정답을 담을 곳
vector<int> answer;
// 배포될 작업을 임시로 담을 곳
queue<int> q;
// 작업 개수라고 보면 되는 사이즈
int size = progresses.size();
// 작업에 해당하는 인덱스를 담는다
for (int i = 0; i < size; ++i)
{
q.push(i);
}
// 큐에 인덱스 값이 남아 있으면 없을때 까지 돈다
while(!q.empty())
{
int cnt = 0;
// 작업 진척도 퍼센테이지를 담아놓은 벡터의 값을 증가시킨다
for(int j = 0; j < size; ++j)
{
progresses[j] += speeds[j];
}
// 여기서 각 배포마다 몇 개의 기능이 배포되는지를 카운트 한다
while(!q.empty() && 100 <= progresses[q.front()])
{
++cnt;
q.pop();
}
// 각 배포마다 몇 개의 기능이 배포되는지 정답지에 담는다
if(cnt != 0)
answer.push_back(cnt);
}
return answer;
}
02-3 올바른 괄호
- 괄호가 바르게 짝지어졌다는 것은 ‘(‘ 문자로 열렸으면 반드시 짝지어서 ‘)’ 문자로 닫혀야 한다는 뜻입니다
- 예를 들어 “()()” 또는 “(())()” 는 올바른 괄호입니다
- ”)()(“ 또는 “(()(“ 는 올바르지 않은 괄호입니다
- ’(‘ 또는 ‘)’ 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요
#include <string>
#include <iostream>
#include <stack>
using namespace std;
bool solution(string s)
{
stack<char> stk;
for(int i = 0; i < s.size(); ++i)
{
// 첫번째 문자가 '(' 이면 그냥 넣는다
if(s[i] == '(')
stk.push('(');
// 첫번째 문자가 '(' 가 아닌데 스택이 비어 있다면 false를 리턴한다
else if(stk.empty())
return false;
// 첫번째 문자가 '(' 가 아닌데 스택이 비어 있지 않다면 pop 한다
else
stk.pop();
}
return stk.size() == 0;
}
02-4 프린터
- 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다
- 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다
- 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다
- 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다
- 예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다
- 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다
- 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다
- 현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int solution(vector<int> priorities, int location)
{
int answer = 0, count = 0;
//일반큐
queue<pair<int, int>> que;
//우선순위 큐
priority_queue<int> prio_que;
//우선순위 큐 정렬 반대로
//priority_queue<int, vector<int>, greater<int>> prio_que;
for (int i = 0; i < priorities.size(); ++i)
{
//큐에 들어온 순서와 중요도를 넣음
que.push(make_pair(i, priorities[i]));
//우선순위 큐에 중요도를 넣음
prio_que.push(priorities[i]);
}
//큐가 빌때까지 반복
while (!que.empty())
{
int index = que.front().first;
int value = que.front().second;
que.pop();
//우선순위 1순위와 현재값이 같다면
if (prio_que.top() == value)
{
//우선순위큐 pop
prio_que.pop();
//하나가 나갔으므로 count
count++;
//현재 나간것이 원하는것과 같다면
if (index == location)
{
//현재 카운터를 리턴
answer = count;
break;
}
}
//우선순위 1순위와 현재값이 같지않다면 큐 뒤에 넣기
else
que.push(make_pair(index, value));
}
return answer;
}
02-5 다리를 지나는 트럭
- 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다
- 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다
- 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다
- 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights)
{
queue<int> que;
int time = 0;
int sum = 0;
int truckIdx = 0;
while(true)
{
// 1초인 시점부터 트럭이 진입하기 시작하자나 그러니까 시작하자 마자 ++ 시켜준거다
time++;
// 트럭의 무게가 다리의 무게보다 작으면, 트럭을 삽입
if(sum + truck_weights[truckIdx] <= weight)
{
// 마지막 트럭이 삽입되면 종료
if(truckIdx == truck_weights.size()-1)
{
// 마지막 트럭 도착시간 추가
time += bridge_length;
break;
}
que.push(truck_weights[truckIdx]);
sum += truck_weights[truckIdx];
truckIdx++;
}
// 트럭의 무게가 다리의 무게보다 크면, 0을 삽입해서 트럭을 도착점으로 민다
else
{
que.push(0);
}
// 큐 사이즈 = 다리길이 -> 트럭 도착
// ( 이 상황에서 트럭이 도착했다는 처리를 해줘야 다음 time++ 에서 새로운 트럭이 들어올 수 있다 )
if(que.size() == bridge_length)
{
sum -= que.front();
que.pop();
}
}
return time;
}
02-6 주식가격
- 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요
#include <string>
#include <vector>
#include <stack>
using namespace std;
vector<int> solution(vector<int> prices)
{
// 7 8 9 7 8 9 7 8 9 이 숫자 세트가 예시로서 적당하다
vector<int> answer(prices.size());
stack<int> st;
int size = prices.size();
for (int i = 0; i < size; i++)
{
// 스택이 비어있지않고
// 스택의 마지막 인덱스가 가리키는 가격이 현재 가격보다 크다면 ( 가격이 떨어 졌다면 )
while (!st.empty() && prices[st.top()] > prices[i])
{
// 지금까지 쌓인 모든 스택 인덱스를 검사하여 얼마만에 가격이 떨어졌는지 죄다 기록한다
answer[st.top()] = i - st.top();
// 가격이 떨어진 인덱스는 제거하자
st.pop();
}
// 현재 인덱스를 스택에 넣기
st.push(i);
}
// 스택이 빌때까지 반복
while (!st.empty())
{
// 가격을 버텨낸 인덱스들이 얼마나 버텼는지 기록해준다
// 유의사항1. 위에서 특정위치에 이미값을 넣었으므로 pushback이나 insert로하면 안된다.
// 유의사항2. 뒤에서부터 넣어야하므로 size-1 에서 버텨낸 인덱스값을 빼준다.
answer[st.top()] = (size - 1) - st.top();
st.pop();
}
return answer;
}
Chapter 03 힙(Heap)
03-1 더 맵게
- 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다
- 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다
- 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
- Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다
- Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요
#include <string>
#include <vector>
#include<queue>
using namespace std;
int solution(vector<int> scoville, int K)
{
int answer = 0;
priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());
while (pq.size() > 1 && pq.top() < K)
{
// 스코빌 지수가 가장 낮은 음식과 두번째로 낮은 음식의 스코빌 지수를 섞는다
int first = pq.top();
pq.pop();
int second = pq.top();
pq.pop();
pq.push(first + (second * 2));
// 섞은 횟수를 ++ 한다
answer++;
}
// 스코빌 지수를 K 이상으로 만들 수 없을 경우 -1로 answer를 갱신한다
if (pq.top() < K) answer = -1;
return answer;
}
Chapter 04 정렬
04-1 K번째수
- 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다
- 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면
- array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다
- 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다
- 2에서 나온 배열의 3번째 숫자는 5입니다
- 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(vector<int> array, vector<vector<int>> commands)
{
vector<int> answer;
int size = commands.size();
for(int i=0; i < size; i++)
{
vector<int> subArray;
// 문자열 일부를 자른다
subArray.assign(array.begin() + commands[i][0] - 1, array.begin() + commands[i][1]);
// 해당 문자열을 집합을 정렬한다
sort(subArray.begin(), subArray.end());
// 커맨더가 가리키는 숫자를 담는다
answer.push_back(subArray[commands[i][2] - 1]);
}
return answer;
}
04-2 가장 큰 수
- 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요
- 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다
- 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(string a, string b)
{
return a + b > b + a;
}
string solution(vector<int> numbers)
{
string answer = "";
vector<string> numbers_str;
// numbers 벡터를 스트링벡터로 바꾸기
for(int i: numbers) numbers_str.push_back(to_string(i));
// 사용자 함수 cmp로 정렬
sort(numbers_str.begin(), numbers_str.end(), cmp);
// numbers_str의 원소들을 다 합치기
for(string str: numbers_str) answer+=str;
// 처음 수가 0이면 뒤 수도 모두 0이므로 0반환
if (answer[0] == '0') return "0";
return answer;
}
04-3 H-Index
- H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다
- 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다
- 위키백과1에 따르면, H-Index는 다음과 같이 구합니다
- 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다
- 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> citations)
{
int answer = 0;
// 문제 기준으로 0, 1, 3, 5, 6 순으로 정렬된다
sort(citations.begin(), citations.end());
for(int i = 0; i < citations.size(); ++i)
{
// 이 구문을 통해 H_Index는 인용된 논문의 개수를 보장한다
int H_Index = citations.size() - i;
// 이 구문을 통해 H_Index는 인용된 논문의 횟수를 보장한다
if(citations[i] >= H_Index) return H_Index;
}
return answer;
}
Chapter 05 완전탐색
05-1 최소직사각형
- 명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다
- 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다
- 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다
- 아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다
- 가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다
- 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다
- 이때의 지갑 크기는 4000(=80 x 50)입니다
- 모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다
- 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> sizes)
{
int w = 0, h = 0;
// 너비와 높이중 한 부분이 최대치를 담당하고, 다른 한 부분이 최소치를 담당한다
for (int i = 0; i < sizes.size(); i++)
{
w = max(w, max(sizes[i][0], sizes[i][1]));
h = max(h, min(sizes[i][0], sizes[i][1]));
}
return w * h;
}
05-2 모의고사
- 수포자는 수학을 포기한 사람의 준말입니다
- 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다
- 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다
- 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, …
- 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, …
- 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, …
- 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> solution(vector<int> answers)
{
vector<int> answer;
// 찍는 방식에 대한 패턴을 정의한다
int n1[5] = {1, 2, 3, 4, 5};
int n2[8] = {2, 1, 2, 3, 2, 4, 2, 5};
int n3[10] = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
int sum[3] = {0};
// 각자 찍는 방식에서 정답을 맞춘 개수를 체크
for(int i = 0; i < answers.size(); ++i)
{
int ans = answers[i];
if(ans == n1[i%5]) sum[0]++;
if(ans == n2[i%8]) sum[1]++;
if(ans == n3[i%10]) sum[2]++;
}
// 가장 정답을 많이 맞춘 사람 기준으로 최대값 구하기
int max = *max_element(sum, sum+3);
// 최대값과 일치하는 사람의 인덱스를 집어넣기
for(int i = 0; i < 3; i++)
{
if(sum[i] == max) answer.push_back(i+1);
}
return answer;
}
05-3 소수 찾기
- 한자리 숫자가 적힌 종이 조각이 흩어져있습니다
- 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다
- 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요
#include<bits/stdc++.h>
using namespace std;
// 소수 판별 함수
bool isPrime(int n)
{
if (n < 2) return false;
// 에라토스테네스의 체
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0) return false;
return true;
}
int solution(string numbers)
{
int answer = 0;
vector<char> vChar; // 종이 조각의 각 숫자 저장
vector<int> vInt; // 종이 조각으로 만들 수 있는 모든 수 저장
// numbers의 각 숫자를 char vector에 입력한다
for (int i = 0; i < numbers.size(); i++)
vChar.push_back(numbers[i]);
// 순열을 구하는 next_premutation를 사용하기 위해서는 무조건 오름차순으로 정렬되어 있어야 한다
sort(vChar.begin(), vChar.end());
// 순열을 이용해 만들 수 있는 모든 숫자 int vector에 저장
do
{
string temp = "";
for (int i = 0; i < vChar.size(); i++)
{
temp.push_back(vChar[i]);
vInt.push_back(stoi(temp));
}
} while (next_permutation(vChar.begin(), vChar.end()));
// 중복 값 지우기 ( https://sangwoo0727.github.io/c++/Cplus-unique/ 참고 )
sort(vInt.begin(), vInt.end());
vInt.erase(unique(vInt.begin(), vInt.end()), vInt.end());
// 소수일 경우 answer++
for (int i = 0; i < vInt.size(); i++)
if (isPrime(vInt[i]))
answer++;
return answer;
}
#include <string>
#include <unordered_map>
#include <algorithm>
#include <cmath>
using namespace std;
unordered_map<int, bool> m;
bool isPrime(string num)
{
int n = stoi(num);
// 이미 확인한 수라면 중복이기 때문에 false 리턴
if(m[n]) return false;
// 확인이 안된 수라면 등록한다
m[n] = true;
if (n < 2) return false;
// 에라토스테네스의 체
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0) return false;
return true;
}
int solution(string numbers)
{
int answer = 0;
// 오름차순 정렬
sort(numbers.begin(), numbers.end());
// 순열(next_premutation)을 이용하여 모든 경우를 따진다
do
{
for(int i=1; i<=numbers.size(); i++)
{
string num = numbers.substr(0, i);
if(isPrime(num)) answer++;
}
}while(next_permutation(numbers.begin(), numbers.end()));
return answer;
}
05-4 카펫
- Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다
- Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다
- Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(int brown, int yellow)
{
vector<int> answer;
// 전체개수 계산
int sum = brown + yellow;
// 갈색 격자의 수 brown은 8 이상 이라고 했으니 yellow는 당연히 1개 즉 height는 3부터 시작
for (int height = 3; ; height++)
{
// 총합을 높이로 나누었을때 나머지가 0일때만 확인하자
if (!(sum % height))
{
// 합을 높이로 나누면 가로길이가 된다.
int width = sum / height;
// 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다
// 라고 했으니 위, 아래 2개와 양옆 2개를 뺀 뒤 곱한 값이 노란색 개수와 같다면 가로 세로 높이를 찾은 것이다
if (((height - 2) * (width - 2)) == yellow)
{
answer.push_back(width);
answer.push_back(height);
break;
}
}
}
return answer;
}
05-5 피로도
- XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다
- 이때, 각 던전마다 탐험을 시작하기 위해 필요한 “최소 필요 피로도”와 던전 탐험을 마쳤을 때 소모되는 “소모 피로도”가 있습니다
- “최소 필요 피로도”는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, “소모 피로도”는 던전을 탐험한 후 소모되는 피로도를 나타냅니다
- 예를 들어 “최소 필요 피로도”가 80, “소모 피로도”가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다
- 이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다
- 유저의 현재 피로도 k와 각 던전별 “최소 필요 피로도”, “소모 피로도”가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int solution(int k, vector<vector<int>> dungeons)
{
int answer = 0;
// 순열을 구하는 next_premutation를 사용하기 위해서는 무조건 오름차순으로 정렬되어 있어야 한다
sort(dungeons.begin(), dungeons.end());
do
{
int iTempK = k;
int iClearStage = 0;
// 클리어한 스테이지 수를 체크한다
for(int i = 0; i < dungeons.size(); ++i)
{
if(dungeons[i][0] <= iTempK)
{
iTempK = iTempK - dungeons[i][1];
iClearStage++;
}
else
break;
}
// 클리어한 스테이지 수가 현재까지의 최대치보다 크면 해당 값을 저장
if(answer < iClearStage) answer = iClearStage;
}while(next_permutation(dungeons.begin(),dungeons.end()));
return answer;
}
05-6 전력망을 둘로 나누기
- n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다
- 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다
- 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다
- 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다
- 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAX = 101;
// 각 노드는 중복이 존재할 수 없다
set<int> graph[MAX];
int getLength(int nodecount, int node)
{
int length = 0;
queue<int> que;
// 현재 노드 세팅
que.push(node);
// 메모이제이션 기법으로 중복 계산 방지
vector<bool> visited(nodecount);
visited[node] = true;
while (!que.empty())
{
// 다음 노드 세팅
int cur = que.front();
que.pop();
length++;
// 현재 노드와 연결된 노드를 모두 큐에 등록한다
for (auto next : graph[cur])
{
if (visited[next])
continue;
que.push(next);
visited[next] = true;
}
}
return length;
}
int solution(int n, vector<vector<int>> wires)
{
// 엣지들을 서로 연결
for (auto wire : wires)
{
graph[wire[0]].insert(wire[1]);
graph[wire[1]].insert(wire[0]);
}
int answer = INF;
// 모든 간선을 한번씩 끊어가면서, 노드 개수의 차이가 최소가 되는 값을 구하자
for (auto wire : wires)
{
graph[wire[0]].erase(wire[1]);
graph[wire[1]].erase(wire[0]);
answer = min(answer, abs(getLength(n, wire[0]) - getLength(n, wire[1])));
graph[wire[0]].insert(wire[1]);
graph[wire[1]].insert(wire[0]);
}
return answer;
}
05-7 모음 사전
- 사전에 알파벳 모음 ‘A’, ‘E’, ‘I’, ‘O’, ‘U’만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다
- 사전에서 첫 번째 단어는 “A”이고, 그다음은 “AA”이며, 마지막 단어는 “UUUUU”입니다
- 단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요
#include<bits/stdc++.h>
using namespace std;
vector<string> arr;
string temp[5] = {"A", "E", "I", "O", "U"};
void go(int maxlen, string s)
{
if(maxlen == s.size())
{
arr.push_back(s);
return;
}
for(int i=0 ; i<5 ; i++)
{
go(maxlen, s+temp[i]);
}
}
int solution(string word)
{
int answer = 0;
// 각 길이별로 가능한 모든 문자열을 저장한다
for(int i=1 ; i<=5 ; i++)
{
go(i, "");
}
// 사전 순으로 정렬한다
sort(arr.begin(), arr.end());
// 원하는 문자가 몇번째 인덱스에 속해있는지 구한다 ( 인덱스 구하는 방법, https://notepad96.tistory.com/41 참고 )
answer = find(arr.begin(), arr.end(), word) - arr.begin() + 1;
return answer;
}
Chapter 06 그리디
06-1 체육복
- 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다
- 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다
- 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다
- 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다
- 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다
- 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요
#include <string>
#include <vector>
#include<algorithm>
using namespace std;
int students[30];
int solution(int n, vector<int> lost, vector<int> reserve)
{
int answer = 0;
// 여벌의 체육복을 가지고 있는 학생 체크, 체육복을 잃어버린 학생 체크
for(int iStudentCount : reserve) students[iStudentCount] += 1;
for(int iStudentCount : lost) students[iStudentCount] += -1;
// 여별의 체육복을 가지고 있는 학생의 체육복을 잃어버린 학생에게 준다
for(int iStudentCount = 1; iStudentCount <= n; iStudentCount++)
{
if(students[iStudentCount] == -1)
{
if(students[iStudentCount-1] == 1)
students[iStudentCount-1] = students[iStudentCount] = 0;
else if(students[iStudentCount+1] == 1)
students[iStudentCount+1] = students[iStudentCount] = 0;
}
}
// 체육복을 가지고 있는 학생수 체크 ( 체육 수업을 들을 수 있는 학생 수 체크 )
for(int iStudentCount = 1; iStudentCount <= n; iStudentCount++)
{
if(students[iStudentCount] != -1) answer++;
}
return answer;
}
06-2 조이스틱
- 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다
- ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA
- 조이스틱을 각 방향으로 움직이면 아래와 같습니다
- 예를 들어 아래의 방법으로 “JAZ”를 만들 수 있습니다
- 만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요
// https://velog.io/@rlagksql219/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4C-%EC%A1%B0%EC%9D%B4%EC%8A%A4%ED%8B%B1-Greedy-nu1ltwjh 참고
#include<bits/stdc++.h>
using namespace std;
int solution(string name)
{
int answer = 0;
int n = name.length();
int turn = n-1;
for(int i = 0; i < n; i++)
{
int index = i+1;
// i 다음에 있는 A가 아닌 문자가 나올때 까지 index++
while(index < n && name[index] == 'A')
{
index++;
}
int left = i;
int right = n - index;
// 한쪽으로만 움직이면서 글자를 바꿀때와, 왼쪽영역 오른쪽영역 번갈라 가며 글자를 바꿀때중 더 좋은 쪽을 선택하자
// 만약 후자가 더 좋은 방법 이라면 왼쪽영역을 먼저 처리하는 방법과 오른쪽영역을 먼저 처리 하는 방법중 더 좋은쪽을 선택
turn = min(turn, min(2*left+right, 2*right+left));
}
answer = answer + turn;
// 상하 움직임을 더해주자, 'Z' - vertical + 1 에서 +1을 하는 이유는 A에서 Z으로 한칸 움직인뒤 계산해주기 위함
for(auto vertical : name)
answer += min(vertical - 'A', 'Z' - vertical + 1);
return answer;
}
06-3 큰 수 만들기
- 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다
- 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다
- 이 중 가장 큰 숫자는 94 입니다
- 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다
- number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요
#include<bits/stdc++.h>
using namespace std;
string solution(string number, int k)
{
string answer = "";
// 앞에서 부터 k 이후 문자를 저장한다 ( https://min-ingful.tistory.com/44 참고 )
answer = number.substr(k);
// 제거된 문자중에서 쓸만한 놈이 있으면 answer의 앞자리 부터 교체해주자 ( 그리디 방식 )
for(int garbage_index = k-1; 0 <= garbage_index; garbage_index--)
{
int answer_index = 0;
while(true)
{
if(answer[answer_index] <= number[garbage_index])
{
char temp = answer[answer_index];
answer[answer_index] = number[garbage_index];
number[garbage_index] = temp;
answer_index++;
}
else
break;
}
}
return answer;
}
06-4 구명보트
- 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다
- 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다
- 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다
- 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다
- 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> people, int limit)
{
int answer = 0;
int head = 0, tail = people.size() - 1;
sort(people.begin(), people.end());
while(head <= tail)
{
// 양 끝단에 있는 사람들을 동시에 태워보내는게 가장 좋은 방법이다
if(people[head] + people[tail] <= limit)
{
head++;
tail--;
}
// 양 끝단에 있는 사람들을 동시에 태워 보낼수 없다면 가장 무거운 사람부터 태워 보내는게 두번째로 좋은 방법이다
else
{
tail--;
}
answer++;
}
return answer;
}
06-5 섬 연결하기
- n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요
- 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다
- 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다
#include<bits/stdc++.h>
using namespace std;
vector<int> island(101);
bool cmp(vector<int> a, vector<int> b)
{
return a[2] < b[2];
}
// https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=8 경로 압축 기법( 14:04 )
int findParent(int idx)
{
if(island[idx] == idx)
return idx;
return island[idx] = findParent(island[idx]);
}
int solution(int n, vector<vector<int>> costs)
{
int answer = 0;
// 섬 초기화
for(int i=0; i<n; i++)
{
island[i] = i;
}
// 비용이 적은순으로 정렬
sort(costs.begin(), costs.end(), cmp);
for(int i=0; i<costs.size(); i++)
{
int start = findParent(costs[i][0]);
int end = findParent(costs[i][1]);
int cost = costs[i][2];
// cycle이 만들어지지 않으면 다리 추가 ( https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=8 서로소 집합을 활용한 사이클 판별, 16:22 )
if(start!=end)
{
answer+=cost;
island[end] = start;
}
}
return answer;
}
06-6 단속카메라
- 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다
- 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요
#include <bits/stdc++.h>
using namespace std;
int solution(vector<vector<int>> routes)
{
int answer = 0, flag = 30001;
// 진입 지점 기준으로 역순 정렬 ( 자동차가 진입해서 진출하는 방향은 고정되어 있다는 점을 명심하자 )
sort(routes.rbegin(), routes.rend());
// 진출 지점 보다 카메라가 앞에 있다면 진입 지점에 카메라를 설치한다
for(size_t i = 0; i < routes.size(); i++)
{
if(flag > routes[i][1])
{
flag = routes[i][0];
answer++;
}
}
return answer;
}
Chapter 07 동적계획법
07-1 N으로 표현
- 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요
// https://ggjjdiary.tistory.com/139 참고
#include<bits/stdc++.h>
using namespace std;
int solution(int N, int number)
{
int answer = -1;
set<int> dp[8];
// N을 나열해서만 수를 표현한 경우
int num = 0;
for (int i = 0; i < 8; i++)
{
num = 10 * num + N;
dp[i].insert(num);
}
// N을 여러번 사칙연산해서 수를 표현한 경우
// DP[i] = DP[i-1] + DP[i-j-1] (0 <= j < i)
for (int i = 1; i < 8; i++)
{
for (int j = 0; j < i; j++)
{
for (int a : dp[j])
{
for (int b : dp[i - j - 1])
{
dp[i].insert(a + b);
dp[i].insert(a - b);
dp[i].insert(a * b);
if (b != 0)
{
dp[i].insert(a / b);
}
}
}
}
}
for (int i = 0; i < 8; i++)
{
if (dp[i].count(number))
{
answer = i + 1;
break;
}
}
return answer;
}
Chapter 08 DFS / BFS
08-1 타겟 넘버
- n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다
- 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다
- 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요
#include <bits/stdc++.h>
using namespace std;
int answer = 0;
void dfs(vector<int> numbers, int target, int sum, int count)
{
// 다섯번이 수행되었을 시점에 sum이 target과 같다면 answer++ 한후 함수 빠져나옴
if (count == numbers.size())
{
if (sum == target) answer++;
return;
}
// 경로 1
dfs(numbers, target, sum + numbers[count], count + 1);
// 경로 2
dfs(numbers, target, sum - numbers[count], count + 1);
}
int solution(vector<int> numbers, int target)
{
dfs(numbers, target, 0, 0);
return answer;
}
08-2 네트워크
- 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다
- 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다
- 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다
- 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오
#include<bits/stdc++.h>
using namespace std;
bool check[201] = { false };
void dfs(vector<vector<int>> computers, int n, int current_computer)
{
// 현재 노드 방문 처리
check[current_computer] = true;
// 현재 노드와 연결된 모든 노드를 체크한다
for(int i = 0; i < n; ++i)
{
if(check[i] == false && computers[current_computer][i] == 1)
{
dfs(computers, n, i);
}
}
}
int solution(int n, vector< vector<int> > computers)
{
int answer = 0;
// 방문이 가능하다는 뜻은 해당 노드와 연결된 노드가 없었다는 뜻이다
for(int i = 0; i < n; ++i)
{
if(check[i] == false)
{
dfs(computers, n, i);
answer++;
}
}
return answer;
}
08-3 게임 맵 최단거리
- 게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요
- 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요
#include<bits/stdc++.h>
using namespace std;
const int MAX = 100;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int solution(vector<vector<int> > maps)
{
// 맵 관련 변수 초기화
vector<vector<bool>> visited(MAX, vector<bool>(MAX, false));
int row = maps.size();
int col = maps[0].size();
// 큐 관련 변수 초기화
queue<pair<pair<int, int>, int>> que;
que.push(make_pair(make_pair(0, 0), 1));
visited[0][0] = true;
while(!que.empty())
{
// 다음 위치 세팅
int x = que.front().first.first;
int y = que.front().first.second;
int cnt = que.front().second;
que.pop();
// 목적지에 도착했다면 정답 리턴
if(x == col - 1 && y == row - 1) return cnt;
// 현재 노드에서 방문할 수 있는 노드를 모두 큐에 담는다
for(int i = 0; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && ny >= 0 && nx < col && ny < row)
{
if(visited[ny][nx] == false && maps[ny][nx] == 1)
{
visited[ny][nx] = true;
que.push(make_pair(make_pair(nx, ny), cnt + 1));
}
}
}
}
return -1;
}
08-4 단어 변환
- 두 개의 단어 begin, target과 단어의 집합 words가 있습니다 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다
#include <string>
#include <vector>
#include <queue>
using namespace std;
bool check[51] = { false };
int solution(string begin, string target, vector<string> words)
{
int answer = 1e9;
int word_count = words.size();
int word_length = begin.size();
queue<pair<int, string>> que;
que.push({ 0, begin });
while (!que.empty())
{
// 다음 단어 세팅
int cnt = que.front().first;
string current_s = que.front().second;
que.pop();
if (current_s == target)
{
answer = cnt;
break;
}
for (int i = 0; i < word_count; ++i)
{
if (check[i]) continue;
// 현재 문자와 후보 문자를 비교해 다른 글자 개수를 체크한다
int diff_cnt = 0;
for (int j = 0; j < word_length; j++)
{
if (words[i][j] != current_s[j]) diff_cnt++;
}
if (diff_cnt == 1)
{
que.push({ cnt + 1, words[i] });
check[i] = true;
}
}
}
// 최소 카운트가 여전히 1e9라면 현재 문자를 타겟 문자로 변환할 수 없는 경우이다
if (answer == 1e9) answer = 0;
return answer;
}
08-5 여행경로
- 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 “ICN” 공항에서 출발합니다
#include<bits/stdc++.h>
using namespace std;
vector<string> nodepoint;
vector<string> answer;
bool visited[10000];
int max_use_tickets = 0;
void dfs(vector<vector<string>>& tickets, string cur, int use_tickets)
{
// 현재 위치를 후보 노드로 등록한다
nodepoint.push_back(cur);
// 사용한 티켓 개수가 이전 최고치를 갱신할 수 있을때만 answer를 갱신한다
// 참고로 사용한 티켓의 개수가 티켓의 총 개수와 같을때 라는 조건을 사용하면 엉뚱한 결과로 갱신될 수 있다
// 이유는 최초 max 갱신시의 순서만 담아야 하기 때문이다
if (max_use_tickets < use_tickets)
{
max_use_tickets = use_tickets;
answer = nodepoint;
}
// 사용할 수 있는 티켓을 찾아 사용하고, 다음 위치를 방문한다
for (int i = 0; i < tickets.size(); i++)
{
if (tickets[i][0] == cur && visited[i] == false)
{
visited[i] = true;
dfs(tickets, tickets[i][1], use_tickets + 1);
visited[i] = false;
}
}
// 현재 위치에서 사용할 수 있는 티켓이 없다면 리턴한다
nodepoint.pop_back();
}
vector<string> solution(vector<vector<string>> tickets)
{
// 알파벳 순으로 방문하기 위해 티켓을 정렬한다
sort(tickets.begin(), tickets.end());
dfs(tickets, "ICN", 0);
return answer;
}
08-6 아이템 줍기
- 지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요
// https://jaimemin.tistory.com/1999 참고
08-7 퍼즐 조각 채우기
- 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다
// https://congsoony.tistory.com/170 참고
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vector<int>>
#define vpii vector<pair<int,int>>
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int n;
bool isrange(int y, int x) { return 0 <= y && y < n && 0 <= x && x < n; }
void dfs(int y, int x, int color, vvi& board, vvi& visit, vpii& v)
{
if (!isrange(y, x))return;
if (visit[y][x] || board[y][x] != color)return;
visit[y][x] = 1;
//도형들을 찾아 v에 집어넣기
v.push_back({ y,x });
for (int i = 0; i < 4; i++)dfs(y + dy[i], x + dx[i], color, board, visit, v);
}
void rotate(vvi& board)
{
//board의 행사이즈과 열사이즈가 바뀜
vvi temp(board[0].size(), vi(board.size()));
for (int i = 0, j2 = board.size() - 1; i < board.size(); i++, j2--)
{
for (int j = 0, i2 = 0; j < board[i].size(); j++, i2++)
{
temp[i2][j2] = board[i][j];
}
}
board = temp;
}
void makeboard(vpii& v, map<int, vector<vvi>>& block)
{
int fy, fx, my, mx;
tie(fy, fx, my, mx) = { v[0].first,v[0].second,v[0].first,v[0].second };
for (int i = 1; i < v.size(); i++)
{
fy = max(fy, v[i].first);
fx = max(fx, v[i].second);
my = min(my, v[i].first);
mx = min(mx, v[i].second);
}
int height = fy - my + 1;
int width = fx - mx + 1;
vvi board(height, vi(width));
for (int i = 0; i < v.size(); i++)
{
board[v[i].first - my][v[i].second - mx] = 1;
}
block[v.size()].push_back(board);
}
bool issame(vvi& board, vvi& board2)
{
for (int i = 0; i < 4; i++)
{
if (board == board2)return true;
rotate(board2);
}
return false;
}
int solution(vector<vector<int>> game_board, vector<vector<int>> table)
{
int answer = 0;
n = table.size();
vvi visit(n, vi(n));
vvi visit2 = visit;
map<int, vector<vvi>> block, block2;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (game_board[i][j] == 0 && visit[i][j] == 0)
{
vpii v;
dfs(i, j, 0, game_board, visit, v);
makeboard(v, block);
}
if (table[i][j] && visit2[i][j] == 0)
{
vpii v;
dfs(i, j, 1, table, visit2, v);
makeboard(v, block2);
}
}
}
for (auto it : block)
{
int size = it.first;
for (vvi v : it.second)
{
for (int i = 0; i < block2[size].size(); i++)
{
if (issame(v, block2[size][i]))
{
block2[size].erase(block2[size].begin() + i);
answer += size;
break;
}
}
}
}
return answer;
}
Chapter 09 이분탐색
09-1 입국심사
- 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요
#include<bits/stdc++.h> // 필요한 헤더 파일들을 한번에 include하기 위한 코드
using namespace std;
long long solution(int n, vector<int> times)
{
long long answer = 0; // 최종적으로 반환될 정답
// times 배열을 오름차순으로 정렬하여 가장 큰 값이 times.back()에 위치하도록 함
sort(times.begin(), times.end());
long long left = 1; // 이진 탐색을 위한 왼쪽 끝 값
long long right = (long long)times.back() * n; // 이진 탐색을 위한 오른쪽 끝 값
while(left <= right) // 이진 탐색
{
long long mid = (left + right) / 2; // 중앙 값
long long cnt = 0; // mid 시간 동안 심사 가능한 인원 수
for(long long i = 0; i < times.size(); i++) // 모든 심사관이 mid 시간 동안 처리할 수 있는 인원 수를 합산
{
cnt = cnt + (mid / times[i]);
}
if(cnt < n) // 처리 가능한 인원 수가 n보다 작은 경우
{
left = mid + 1; // 이진 탐색의 왼쪽 끝 값을 mid+1로 조정하여 다시 탐색
}
else // 처리 가능한 인원 수가 n 이상인 경우
{
answer = mid; // 현재 시간을 정답에 저장
right = mid - 1; // 이진 탐색의 오른쪽 끝 값을 mid-1로 조정하여 다시 탐색
}
}
return answer; // 정답 반환
}
09-2 징검다리
- 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요
Chapter 10 그래프
10-1 가장 먼 노드
- 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요
#include<bits/stdc++.h>
using namespace std;
int maxlevel = 1;
int solution(int n, vector<vector<int>> edge)
{
int answer = 0;
vector<vector<int>> graph(n + 1);
vector<bool> visited(n + 1, false);
for(int i = 0; i < edge.size(); i++)
{
graph[edge[i][0]].push_back(edge[i][1]);
graph[edge[i][1]].push_back(edge[i][0]);
}
queue<pair<int, int>> que;
que.push({1, 1});
visited[1] = true;
while(!que.empty())
{
int node = que.front().first;
int currentlevel = que.front().second;
que.pop();
if(maxlevel != currentlevel)
{
maxlevel = currentlevel;
answer = 1;
}
else
answer++;
for(int i = 0; i < graph[node].size(); i++)
{
if(!visited[graph[node][i]])
{
visited[graph[node][i]] = true;
que.push({graph[node][i], currentlevel + 1});
}
}
}
return answer;
}
10-2 순위
- 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요
// 플로이드 워셜 알고리즘 기반
#include<bits/stdc++.h>
using namespace std;
int solution(int n, vector<vector<int>> results)
{
int answer = 0;
vector<vector<bool>> graph(n+1, vector<bool>(n+1, false));
for (auto r : results) graph[r[0]][r[1]] = true;
for (size_t i = 1; i <= n; i++)
for (size_t j = 1; j <= n; j++)
for (size_t k = 1; k <= n; k++)
if (graph[j][i] && graph[i][k])
graph[j][k] = true;
for (size_t i = 1; i <= n; i++)
{
int count = 0;
for (size_t j = 1; j <= n; j++)
if (graph[i][j] || graph[j][i]) count++;
if (count == n - 1) answer++;
}
return answer;
}
Chapter N 문자열
N-1 문자열 내 p와 y의 개수
- 예를 들어 s가 “pPoooyY”면 true를 return하고 “Pyy”라면 false를 return합니다
#include<bits/stdc++.h>
using namespace std;
bool solution(string s)
{
unordered_map<char, int> mCharCount;
// 해당하는 문자 카운트를 올린다
for(auto charpart : s)
{
mCharCount[charpart] = mCharCount[charpart] + 1;
}
// 해당하는 문자 카운트를 계산한다
int pCount = mCharCount['p'] + mCharCount['P'];
int yCount = mCharCount['y'] + mCharCount['Y'];
// 문자 카운트를 비교해 결과를 출력한다
if(pCount == yCount)
return true;
else
return false;
}
N-2 문자열을 정수로 바꾸기
- 문자열 s를 숫자로 변환한 결과를 반환하는 함수, solution을 완성하세요
#include<bits/stdc++.h>
using namespace std;
int solution(string s)
{
int answer = 0;
// 첫번째 문자가 - 이면 해당 문자를 제거한뒤, 숫자로 변환하고 음수로 만들어 준다
if(s[0] == '-')
{
s.erase(s.begin());
answer = stoi(s);
answer = answer * -1;
}
// 첫번째 문자가 - 가 아니면 바로 숫자로 변환한다
else
{
answer = stoi(s);
}
return answer;
}
N-3 문자열 내림차순으로 배치하기
- s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 간주합니다
#include<bits/stdc++.h>
using namespace std;
string solution(string s)
{
// 문자열을 역순으로 정렬한다
sort(s.rbegin(), s.rend());
return s;
}
N-4 문자열 다루기 기본
- 문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요
#include<bits/stdc++.h>
using namespace std;
bool solution(string s)
{
bool answer = true;
// 문자열 길이가 4 혹은 6인지 체크하자
if(s.size() == 4 || s.size() == 6)
{
// 문자에 숫자 이외의 문자가 들어 있다면 false 처리 하자
for(auto charpiece : s)
{
if('0' <= charpiece && charpiece <= '9')
continue;
else
{
answer = false;
break;
}
}
}
else
answer = false;
return answer;
}
N-5 JadenCase 문자열 만들기
- 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요
// https://notepad96.tistory.com/51 참고
#include<bits/stdc++.h>
using namespace std;
string solution(string s)
{
string answer = "";
bool levelup = true;
for(int i = 0; i < s.size(); ++i)
{
// 현재 문장의 첫번째 인덱스가 소문자이면 대문자로 바꿔준다
if('a' <= s[i] && s[i] <= 'z' && levelup == true)
{
char charfrom = s[i];
char charto = charfrom - 32;
replace(s.begin() + i, s.begin() + (i+1), charfrom, charto);
levelup = false;
}
// 현재 인덱스가 첫글자가 아니면서 대문자이면 소문자로 바꿔준다
else if('A' <= s[i] && s[i] <= 'Z' && levelup == false)
{
char charfrom = s[i];
char charto = charfrom + 32;
replace(s.begin() + i, s.begin() + (i+1), charfrom, charto);
levelup = false;
}
// 현재 인덱스가 공백 문자라면 다음 문자는 대문자로 바뀔 기회를 준다
else if(s[i] == ' ')
levelup = true;
// 기본적으로는 대문자로 바뀔 기회를 주지 않는다
else
levelup = false;
}
answer = s;
return answer;
}
#include<bits/stdc++.h>
using namespace std;
string solution(string s)
{
string answer = s;
// 첫글자니까 대문자로 바꿔준다
answer.at(0) = toupper(answer.at(0));
for (int i = 1; i<answer.size(); i++)
{
// 이전 문자가 공백문자 일때만 대문자로 바꿔준다
if (answer[i - 1] == ' ')
answer[i]=toupper(answer[i]);
// 이전 문자가 공백문자가 아니라면 소문자로 바꿔준다
else
answer[i]=tolower(answer[i]);
}
return answer;
}
N-6 이상한 문자 만들기
- 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 리턴하는 함수, solution을 완성하세요
#include<bits/stdc++.h>
using namespace std;
string solution(string s)
{
string answer = s;
// 첫글자는 무조건 대문자로 만들어 준다
answer.at(0) = toupper(answer.at(0));
bool levelup = false;
for(int i = 1; i < answer.size(); ++i)
{
// 이전 문자가 공백 문자이면 대문자로 바꿀 기회를 준다
if(answer[i-1] == ' ') levelup = true;
// 대문자로 바꿀 기회가 있으면 대문자로 바꾼다
if(levelup == true)
{
answer[i] = toupper(answer[i]);
levelup = false;
}
// 대문자로 바꿀 기회가 없으면 소문자로 바꾼다
else
{
answer[i] = tolower(answer[i]);
levelup = true;
}
}
return answer;
}
N-7 문자열 내 마음대로 정렬하기
- 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다
#include<bits/stdc++.h>
using namespace std;
int compareindex;
bool cmp(string a, string b)
{
// 비교할 인덱스 위치의 문자가 같다면 사전순으로 앞선 문자열이 앞쪽에 위치하게 한다
if(a[compareindex] == b[compareindex])
return a < b;
// 비교할 인덱스 위치의 문자가 같지 않다면 n번째 글자를 기준으로 오름차순 정렬한다
else
return a[compareindex] < b[compareindex];
}
vector<string> solution(vector<string> strings, int n)
{
compareindex = n;
sort(strings.begin(), strings.end(), cmp);
return strings;
}
N-8 숫자 문자열과 영단어
- s가 의미하는 원래 숫자를 return 하도록 solution 함수를 완성해주세요
#include<bits/stdc++.h>
using namespace std;
unordered_map<string, char> stringcount;
int solution(string s)
{
string answer = "";
string num = "";
stringcount["zero"] = '0';
stringcount["one"] = '1';
stringcount["two"] = '2';
stringcount["three"] = '3';
stringcount["four"] = '4';
stringcount["five"] = '5';
stringcount["six"] = '6';
stringcount["seven"] = '7';
stringcount["eight"] = '8';
stringcount["nine"] = '9';
for (int i = 0; i < s.size(); i++)
{
// 현재 인덱스 문자가 0 ~ 9 사이면 정답지에 쌓는다
if (s[i] >= '0' && s[i] <= '9') answer += s[i];
else
{
// 현재 인덱스 문자가 0 ~ 9 사이가 아니라면 num에 쌓는다
num += s[i];
// num에 쌓은 문자가 검색되면 숫자로 변환해 정답지에 쌓는다
if (stringcount.count(num))
{
answer += stringcount[num];
num = "";
}
}
}
int result = stoi(answer);
return result;
}
N-9 시저 암호
- 문자열 s와 거리 n을 입력받아 s를 n만큼 민 암호문을 만드는 함수, solution을 완성해 보세요
#include<bits/stdc++.h>
using namespace std;
string solution(string s, int n)
{
string answer = "";
for(int i = 0; i < s.size(); i++)
{
// 공백 문자가 아닐때만
if(s[i] != ' ')
{
// 순수 이동량을 구한뒤 더하자
if(s[i] >= 'a' && s[i] <= 'z')
answer += (s[i] - 'a' + n) % 26 + 'a';
else
answer += (s[i] - 'A' + n) % 26 + 'A';
}
else
answer += ' ';
}
return answer;
}
N-10 문자열 압축
- 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요
#include<bits/stdc++.h>
using namespace std;
int solution(string s)
{
int stringcount = s.size();
int answer = s.size();
for(int i = 1; i <= (stringcount / 2); i++)
{
string matchstring = s.substr(0, i);
int matchcount = 1;
string res = "";
for(int j = i; j < stringcount; j = j+i)
{
if(matchstring == s.substr(j, i)) matchcount++;
else
{
if(matchcount > 1) res = res + to_string(matchcount);
res = res + matchstring;
matchstring = s.substr(j, i);
matchcount = 1;
}
}
if(matchcount > 1) res = res + to_string(matchcount);
res = res + matchstring;
answer = min(answer, (int)res.size());
}
return answer;
}
N-11 괄호 변환
- 균형잡힌 괄호 문자열 p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 올바른 괄호 문자열로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요
#include<bits/stdc++.h>
using namespace std;
string make_bracket(string w)
{
// 1. 빈 문자열인 경우
if (w == "")
return "";
// 2. u, v 분리
string u = "";
string v = "";
int left = 0;
int right = 0;
for (int i = 0; i < w.length(); ++i)
{
if (w[i] == '(')
++left;
else
++right;
if (left == right)
{
u = w.substr(0, i + 1);
v = w.substr(i + 1);
break;
}
}
// 3. u가 "올바른 괄호 문자열" 일 경우
if (u.front() == '(' && u.back() == ')')
return u + make_bracket(v);
// 4. u가 "올바른 괄호 문자열"이 아닐 경우
else
{
string new_str = "";
new_str += '(';
new_str += make_bracket(v);
new_str += ')';
u = u.substr(1, u.length() - 2);
for (int i = 0; i < u.length(); ++i)
{
if (u[i] == '(')
u[i] = ')';
else
u[i] = '(';
}
new_str += u;
return new_str;
}
}
string solution(string p)
{
string answer = make_bracket(p);
return answer;
}
댓글남기기