11/25(토)에 있었던 2024 KAKAO WINTER INTERNSHIP 코딩테스트에 참여하고 싶었지만, ICPC 본선 일정과 겹쳐 아쉽게도 참여하지는 못했습니다.
문제가 궁금해서 프로그래머스에 문제가 올라오기만 기다리다 드디어 올라와서 빨리 풀어보고 왔습니다. :) (링크)
개인적으로 구현이 오래 걸려서인지, 문제 푸는데 시간이 2번>5번>3번>4번>1번 순으로 오래 걸렸습니다. (저는 2번이 가장 오래 걸렸네요...)
1. 가장 많이 받은 선물
선물을 주고받은 기록을 map이나 dictionary 등의 자료구조에 저장해준 후, 문제에서 설명한 규칙대로 선물을 주고받는 과정을 시뮬레이션해줍시다. (자기 자신에게 선물을 주는 입력은 주어지지 않으므로, 코드의 마지막 이중 for 문에서 딱히 예외처리는 하지 않아도 됩니다.)
코드
#include <bits/stdc++.h>
using namespace std;
int solution(vector<string> friends, vector<string> gifts) {
map<string,map<string,int>> ma;
map<string,int> gift;
string give,get;
for(auto i:gifts){
istringstream iss(i);
iss>>give>>get;
//ma[A][B] : A가 B에게 준 선물 수 - A가 B에게 받은 선물 수
ma[give][get]++,ma[get][give]--;
//gift[A] : A의 선물 지수
gift[give]++,gift[get]--;
}
int answer=0;
map<string,int> ans;
for(auto a:friends)for(auto b:friends)
if(ma[a][b]>0||(ma[a][b]==0&&gift[a]>gift[b]))
ans[a]++,answer=max(answer,ans[a]);
return answer;
}2. 도넛과 막대 그래프
각 모양의 그래프의 정점이 갖는 특징에 대해 관찰해야 하는 문제였습니다.
- 생성한 정점 : 들어오는 간선이 없고, 나가는 간선이 2개 이상입니다.
- 막대 모양 그래프 : 나가는 간선이 없는 정점이 정확히 1개 존재합니다.
- 8자 모양 그래프 : 들어오는 간선이 2개, 나가는 간선이 2개인 정점이 정확히 1개 존재합니다.
- 도넛 모양 그래프 : 들어오는 간선이 1개, 나가는 간선이 1개인 정점들로만 이루어져 있습니다.
이제 문제를 풀어봅시다.
- 위의 특징을 활용하기 위해, 간선들을 보면서 들어오는 간선, 나가는 간선의 개수를 먼저 구해줍시다.
- 생성한 정점을 찾아주고, 정점들을 모양 그래프 단위로 분리하기 위해 생성한 정점과 연결된 간선들을 모두 제거해줍시다. (제거하지 않으면 막대 모양 그래프와 8자 모양 그래프의 특징이 있는 정점을 찾는 데 방해가 됩니다.)
- 막대 모양 그래프와 8자 모양 그래프의 개수를 세어줍시다.
- 이제 도넛 모양 그래프의 개수를 구해야 합니다. 그런데 도넛 모양 그래프의 특징은, 다른 모양 그래프들도 갖고 있기 때문에 활용하기가 어렵습니다. 하지만 우리는 도넛 모양을 제외한 그래프들의 개수를 알고 있죠?
- 따라서 (모든 그래프 덩어리의 개수 - (막대 모양 그래프의 개수 + 8자 모양 그래프의 개수))를 구하면 도넛 모양 그래프의 개수가 됩니다. 모든 그래프 덩어리의 개수는 저는 union-find를 사용했지만, bfs, dfs등으로도 충분히 구할 수 있습니다.
아래 문제들로 연습해보시면 도움이 될 것 같습니다.
코드
#include<bits/stdc++.h>
using namespace std;
//exist[i] : i번 정점이 존재하는가? (이게 없으면, 존재하지 않는 정점과 size=1인 막대 모양 그래프가 구분이 안 됩니다.)
int u[1000001],in[1000001],out[1000001],exist[1000001];
//union-find
int find(int a){return u[a]<0?a:u[a]=find(u[a]);}
bool merge(int a,int b){
a=find(a),b=find(b);
if(a==b)return false;
u[a]+=u[b],u[b]=a;
return true;
}
vector<int> solution(vector<vector<int>> edges) {
int add=-1,doughnut=0,stick=0,eight=0;
for(auto i:edges)in[i[1]]++,out[i[0]]++,exist[i[1]]=exist[i[0]]=1;
//생성한 정점 찾기. (특징 : 나가는 간선 2개 이상, 들어오는 간선 없음)
for(int i=1;i<=1000000;i++)if(out[i]>=2&&!in[i]){add=i;break;}
//생성한 정점과 직접 이어진 간선들 모두 제거.
for(auto i:edges)if(i[0]==add||i[1]==add)in[i[1]]--,out[i[0]]--;
exist[add]=0;
//막대 모양 그래프 특징 : 나가는 간선이 없는 정점이 유일하게 존재.
//8자 모양 그래프 특징 : 나가는 간선, 들어오는 간선이 각각 정확히 2개인 정점이 유일하게 존재.
for(int i=1;i<=1000000;i++){
if(exist[i]&&!out[i])stick++;
if(in[i]==2&&out[i]==2)eight++;
}
//그래프 연결 후,
memset(u,-1,sizeof(u));
for(auto i:edges){
int s=i[0],e=i[1];
if(s==add)continue;
merge(s,e);
}
int all=0;
//그래프 덩어리 개수 세기.
for(int i=1;i<=1000000;i++)all+=exist[i]&&i==find(i);
//남은 덩어리는 도넛 모양 그래프의 개수.
doughnut=all-stick-eight;
return {add,doughnut,stick,eight};
}3. 주사위 고르기
A가 주사위를 가져가고 굴리는 모든 경우를 효율적으로 탐색하면 됩니다.
A가 가져갈 주사위를 고르기 위해, 비트마스킹을 사용해 보겠습니다.
dice[i]를 A가 가져가는 것을 1, B가 가져가는 것을 0으로 표현하고, A와 B가 가져가는 주사위의 개수는 신경 쓰지 않는다고 가정해보면, n 자리의 이진수로 표현할 수 있습니다.
예를 들면, 34 = 100010(2) -> A가 dice[1], dice[5]를 가져갔고, B가 dice[0], dice[2], dice[3], dice[4]를 가져간 상황입니다.
그러면 for 문을 $[0$~$2^n)$ 범위에서 돌면서, 각자 가져간 주사위 수가 같은지 확인하면 모든 경우를 탐색할 수 있습니다.
이때 C++의 __builtin_popcount(s) 함수를 이용하면 s의 이진수 표현해서 1의 개수를 알 수 있고,
dice[i]를 누가 가져갔는지 알고 싶다면 (s>>i&1)이 1인지 0인지 확인하면 됩니다. (잘 이해가 되지 않는다면 이 글의 마지막 설명 부분을 참고하시거나 댓글 달아주세요!)
가져간 주사위를 굴리는 과정은 코드에 주석으로 설명하여 대체하겠습니다. (가독성을 위해 들여쓰기를 약간 수정했습니다.)
코드
#include<bits/stdc++.h>
using namespace std;
vector<int> solution(vector<vector<int>> dice) {
pair<int,vector<int>> ans={-1,{}};
int n=dice.size();
for(int s=0;s<1<<n;s++){
/* s를 이진수로 나타냈을 때, 1의 개수가 n/2개가 아니라면 넘어갑니다.
이때 1이 A가 굴릴 주사위, 0이 B가 굴릴 주사위의 번호입니다. */
if(__builtin_popcount(s)!=n/2)continue;
vector<int> a(501);a[0]=1;//a[i]:A가 B보다 i점 높은 경우의 수
vector<int> A_dice;
//A가 얻는 점수.
for(int j=0;j<n;j++)
if(s>>j&1){
vector<int> nx(501);
//A의 점수는 500점을 초과할 수 없습니다.
for(int i=0;i<=500;i++)
if(a[i])for(auto add:dice[j])nx[add+i]+=a[i];
a=nx;
A_dice.push_back(j+1);
}
//B가 얻는 점수.
for(int j=0;j<n;j++){
if(s>>j&1)continue;
vector<int> nx(501);
for(int i=0;i<=500;i++)
//음수(A가 B보다 점수가 낮은 경우)는 고려할 필요가 없습니다.
for(auto del:dice[j])nx[max(0,i-del)]+=a[i];
a=nx;
}
int number_of_win=0;
//A가 1점이라도 높으면 승리.
for(int i=1;i<=500;i++)number_of_win+=a[i];
ans=max(ans,{number_of_win,A_dice});
}
return ans.second;
}4. n + 1 카드게임
만약 아이디어가 떠오르지 않으셨다면, 이 문제를 풀어보고 오시면 도움이 될 것 같습니다.
일단 처음에 갖고 시작하는 n/3장의 카드 중에서 낼 수 있는 카드 쌍이 있다면 그만큼 공짜로 라운드를 넘길 수 있습니다.
그리고 이렇게 벌어둔 라운드에서 갖고 있던 카드의 페어 카드가 나온다면, 일단 사둬야 합니다. 1원만 들여서 라운드를 넘기는 셈이 되니까요.
이제 남은 경우는 처음에 들고 있지 않은 카드 쌍으로 라운드를 넘겨야 하는 경우. 즉, 2원으로 카드 쌍을 사는 경우가 되는데, 이 카드들의 구매 전략을 정하는 게 이 문제의 핵심 아이디어입니다.
내가 어떤 라운드에 카드를 샀는데, 게임이 끝날 때까지 페어 카드가 안 나오면 동전을 낭비한 것이 되고,
내가 어떤 라운드에 카드를 버렸는데, 이후 라운드에 페어 카드가 나와버리면 카드를 사지 않은 것을 후회하게 되니까요.
그런데 그리디를 잘 이용하면, 약간의 반칙(?)이 가능합니다.
내가 이전 라운드에 카드를 버렸는데, 이번 라운드에 페어 카드가 나와서 후회하는 상황을 가정해보면, 이전에 카드를 버렸던 행동을 철회하고 구매했던 것으로 치는 게(???) 가능합니다!
왜냐하면, 그 버렸던 카드는 이번 라운드까지 넘기는 데 아무 역할도 안 했거든요.
여기서 한 가지 주의할 점이 있는데, 2원으로 카드 쌍을 살 수 있다고 해서 무턱대고 바로 구매하면 안 됩니다. 정확히는, 1원으로 라운드를 넘길 수 있는 경우를 더 우선시해야 합니다. (이 설명은, 코드 마지막의 else if 문의 순서에 해당합니다.)
이 점에 유의하면서 그대로 구현해주시면 됩니다.
+) 코드에서 one++, two++ 부분은 카드를 구매하는 것을 의미하는 것이 아니라, 라운드를 1원/2원으로 넘길 방법이 생겼다는 의미입니다. 실제로 구매하는 부분은 one--, two-- 부분입니다.
코드
#include<bits/stdc++.h>
using namespace std;
int solution(int coin, vector<int> cards) {
int n=cards.size();
vector<int> have(n+1),buy(n+1);
int zero=0,one=0,two=0,ans=1;
for(int i=0;i<n/3;i++){
int x=cards[i];
have[x]++;
//가진 카드들로 한 턴을 넘길 수 있다.
if(have[x]&&have[n+1-x])
zero++,have[x]--,have[n+1-x]--;
}
for(int i=n/3;i<n;i+=2){
int a=cards[i],b=cards[i+1];
buy[a]++,buy[b]++;
//만약 1코인 써서 카드 a만 구매하면 한 턴을 넘길 수 있다.
if(buy[a]&&have[n+1-a])one++,buy[a]--,have[n+1-a]--;
if(buy[b]&&have[n+1-b])one++,buy[b]--,have[n+1-b]--;
//만약 2코인 써서 카드 a와 카드 n+1-a를 구매하면 한 턴을 넘길 수 있다.
if(buy[a]&&buy[n+1-a])two++,buy[a]--,buy[n+1-a]--;
if(buy[b]&&buy[n+1-b])two++,buy[b]--,buy[n+1-b]--;
if(zero)zero--,ans++;
else if(one&&coin)coin--,one--,ans++;
else if(two&&coin>=2)coin-=2,two--,ans++;
//코인이 없거나 카드 쌍이 없어 더 이상 라운드를 진행할 수 없다.
else break;
}
return ans;
}5. 산 모양 타일링
먼저, dp[i][j]를 아래 그림과 같이 정의해 보겠습니다. (빨간색은 어떤 방법으로든 타일링이 완료된 부분, 하얀색은 아직 타일링이 완료되지 않은 부분, 보라색은 마름모 타일로 채워진 부분입니다.) 이때, dp[x][1]은 항상 마지막 부분이 마름모 타일로 채워져야 하는데, 그렇지 않으면 dp[x][0] 이후에 첫 부분을 정삼각형 타일로 채운 것과 중복이 됩니다.
이제 다음 상태로 넘어가기 위해 8가지로 케이스가 분류되는데, 이들 중 예시로 3가지만 살펴보겠습니다.
1. tops[x]=1이고, dp[x][0] -> dp[x+1][1]로 넘어가는 경우
노란색 부분이 지금 채워야 할 부분인데, dp[x+1][1]로 넘어가기 때문에 2, 4번이 마름모 타일로 채워져야 하죠.
그래서 1, 3번은 무조건 정삼각형 타일로 채울 수밖에 없고, 경우의 수는 1가지입니다.
2. tops[x]=0이고, dp[x][0] -> dp[x+1][0]로 넘어가는 경우
2, 3번을 각각 정삼각형 타일로 채우거나, 마름모 타일로 한 번에 채우거나.
경우의 수는 2가지입니다.
3. tops[x]=1이고, dp[x][0] -> dp[x+1][0]로 넘어가는 경우
1, 2번을 마름모 타일로 채우거나, 2, 3번을 마름모 타일로 채우거나, 모두 정삼각형 타일로 채우거나.
경우의 수는 3가지입니다.
위와 마찬가지 방법으로 다른 다섯 가지 경우도 구해주시면 됩니다.
+) dp[n][0]의 경우 아직 타일링이 완료되지 않았지만, 어차피 마지막 4번 타일 하나는 당연히 정삼각형 타일로 채워야 하기 때문에 답은 (dp[n][0]+dp[n][1])%10007이 됩니다.
코드
#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
/*
정삼각형 블록 4개를 위,오른쪽순으로 1,2,3,4번으로 가정.
문제의 두 번째 그림을 예시로 들면,
첫 번째 도형 : 1, 두 번째 도형 : 23, 세 번째 도형 : 34, 네 번째 도형 : 13.
*/
int dp[100001][2];//1/0 : 4번 블록이 채워진 거/안 채워진 거. 근데 채우려면 보라색 블록으로만 채워야 함.
int solution(int n, vector<int> tops) {
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=0;i<n;i++){
if(tops[i]){
dp[i+1][0]=(dp[i+1][0]+dp[i][0]*3)%mod;//123
dp[i+1][1]=(dp[i+1][1]+dp[i][0]*1)%mod;//1234
dp[i+1][0]=(dp[i+1][0]+dp[i][1]*2)%mod;//13
dp[i+1][1]=(dp[i+1][1]+dp[i][1]*1)%mod;//134
}
else{
dp[i+1][0]=(dp[i+1][0]+dp[i][0]*2)%mod;//23
dp[i+1][1]=(dp[i+1][1]+dp[i][0]*1)%mod;//234
dp[i+1][0]=(dp[i+1][0]+dp[i][1]*1)%mod;//3
dp[i+1][1]=(dp[i+1][1]+dp[i][1]*1)%mod;//34
}
}
return (dp[n][0]+dp[n][1])%mod;
}코드에 이해되지 않는 부분이나 설명이 부족한 부분이 있다면 편하게 댓글 달아주세요!
감사합니다.
'PS > 프로그래머스' 카테고리의 다른 글
| [프로그래머스 LV.4] 1,2,3 떨어트리기 (C++) - 2023 KAKAO BLIND RECRUITMENT (1) | 2023.05.30 |
|---|---|
| [프로그래머스 LV.4] 미로 탈출 (C++) - 2021 카카오 채용연계형 인턴십 (0) | 2023.05.29 |