프로그래머스라는 홈페이지에도 굉장히 많은 알고리즘 문제들이 있다는 것을 확인했습니다.
특히, 카카오 공채 문제들이라던지, 엄청 많이 있죠!
오늘은 이중에서 2018 섬머 코딩 4 문제를 풀어보겠습니다!!
https://programmers.co.kr/learn/challenges
문제는 위에 링크를 클릭하시면 볼 수 있습니다!!
1. 숫자 게임
문제 설명
xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.
먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다.
각 사원은 딱 한 번씩 경기를 합니다.
각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다.
만약 숫자가 같다면 누구도 승점을 얻지 않습니다.
전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 팀원들의 출전 순서를 정했습니다. 이때의 B팀이 얻는 승점을 구해주세요.
A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열 A와 i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열 B가 주어질 때, B 팀원들이 얻을 수 있는 최대 승점을 return 하도록 solution 함수를 완성해주세요.
제한사항
A와 B의 길이는 같습니다.
A와 B의 길이는 1 이상 100,000 이하입니다.
A와 B의 각 원소는 1 이상 1,000,000,000 이하의 자연수입니다.
입출력 예
A B result
[5,1,3,7] [2,2,6,8] 3
[2,2,2,2] [1,1,1,1] 0
입출력 예 설명
입출력 예 #1
A 팀은 숫자 5를 부여받은 팀원이 첫번째로 출전하고, 이어서 1,3,7을 부여받은 팀원들이 차례대로 출전합니다.
B 팀원들을 4번, 2번, 3번, 1번의 순서대로 출전시킬 경우 팀원들이 부여받은 숫자들은 차례대로 8,2,6,2가 됩니다. 그러면, 첫 번째, 두 번째, 세 번째 경기에서 승리하여 3점을 얻게 되고, 이때가 최대의 승점입니다.
입출력 예 #2
B 팀원들을 어떤 순서로 출전시켜도 B팀의 승점은 0점입니다.
어떻게 풀까?
그리디 알고리즘입니다!
어짜피 상대의 팀은 순서가 정해져 있습니다!
이 경우에 팀이 많이 이기기 위해선 어떻게 해야할까요!?
바로, 이길때는 아슬아슬하게 이기고, 질 때는 아주 확실하게 낮은 플레이어로 지는 것 입니다!
그리고, 해당 문제는 승점만을 따지기 때문에, 무승부를 하는 경우에도 자신의 팀에서 가장 낮은 카드인 플레이어가 나가면 됩니다!
특히, A팀에서 높은 자연수를 들고 있을 수록 B팀에서는 가장 낮은 자연수를 들고있는 팀원이 경기에 나가서 지는 것이 승점을 더 얻기 위한 방법이 될 수 있습니다!
즉, A팀과 B팀을 서로 정렬한 후에, A팀과 B팀에서 가장 큰 선수들을 우선 비교합니다!
만약, B팀에서 가장 높은 자연수의 선수가 무승부를 하거나 진다면, 자신의 팀에선 가장 낮은 선수가 출전하고,
B팀 선수가 이길 수 있다면 B팀에서 가장 높은 선수가 나가면 됩니다.
여기서 약간의 의문이 드는 분이 있을 수 있습니다!
엇! B팀에서 제일 높은 선수가 아니더라도 A 선수보다 살짝 높은 B의 선수가 나가는게 승률에 조금 더 보탬이 되지 않을까!? 라고 말이죠!
위의 경우로 예를 들어드리겠습니다! 현재 A팀에서 가장 높은 자연수는 8 입니다!
B 선수는 11이라고 하죠!
여기서, 11을 아끼는 것이 별로 필요가 없다는 것을 알 수 있습니다.
어짜피 10으로도 이길 수 있는 수라면, 그 뒤에 나오는 수들도 10으로 이길 수 있는 수 이기 때문이죠!
즉, B팀에서 8 보다 큰 수라면, 어짜피 A의 나머지 선수들도 다 이길 수 있기 때문에 결과적으로 9, 10, 11이라는 카드들은 모두 같은 승점을 얻을 수 있는 것입니다!
이렇게 그리디로 문제를 해결할 수 있습니다!
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include <iostream> #include <stdio.h> #include <string> #include <vector> #include<algorithm> using namespace std; int solution(vector<int> d, int budget) { int answer = 0; sort(d.begin(), d.end()); int value = 0; int i = 0; while(i < d.size()&& value + d[i] <= budget){ value += d[i]; i++; answer++; } return answer; } | cs |
여담
시간 복잡도는 정렬하는 시간이 주가 되기 때문에, O(N log(N)) 입니다.
2. 끝말 잇기
문제 설명
1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.
1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
이전에 등장했던 단어는 사용할 수 없습니다.
한 글자인 단어는 인정되지 않습니다.
다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.
tank → kick → know → wheel → land → dream → mother → robot → tank
위 끝말잇기는 다음과 같이 진행됩니다.
1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
(계속 진행)
끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.
사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.
제한 사항
끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
단어의 길이는 2 이상 50 이하입니다.
모든 단어는 알파벳 소문자로만 이루어져 있습니다.
끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
정답은 [ 번호, 차례 ] 형태로 return 해주세요.
만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.
입출력 예
n words result
3 [tank, kick, know, wheel, land, dream, mother, robot, tank] [3,3]
5 [hello, observe, effect, take, either, recognize, encourage, ensure, establish, hang, gather, refer, reference, estimate, executive] [0,0]
2 [hello, one, even, never, now, world, draw] [1,3]
입출력 예 설명
입출력 예 #1
3명의 사람이 끝말잇기에 참여하고 있습니다.
1번 사람 : tank, wheel, mother
2번 사람 : kick, land, robot
3번 사람 : know, dream, tank
와 같은 순서로 말을 하게 되며, 3번 사람이 자신의 세 번째 차례에 말한 tank라는 단어가 1번 사람이 자신의 첫 번째 차례에 말한 tank와 같으므로 3번 사람이 자신의 세 번째 차례로 말을 할 때 처음 탈락자가 나오게 됩니다.
입출력 예 #2
5명의 사람이 끝말잇기에 참여하고 있습니다.
1번 사람 : hello, recognize, gather
2번 사람 : observe, encourage, refer
3번 사람 : effect, ensure, reference
4번 사람 : take, establish, estimate
5번 사람 : either, hang, executive
와 같은 순서로 말을 하게 되며, 이 경우는 주어진 단어로만으로는 탈락자가 발생하지 않습니다. 따라서 [0, 0]을 return하면 됩니다.
입출력 예 #3
2명의 사람이 끝말잇기에 참여하고 있습니다.
1번 사람 : hello, even, now, draw
2번 사람 : one, never, world
와 같은 순서로 말을 하게 되며, 1번 사람이 자신의 세 번째 차례에 'r'로 시작하는 단어 대신, n으로 시작하는 now를 말했기 때문에 이때 처음 탈락자가 나오게 됩니다.
어떻게 풀까?
해당 문제는 map을 사용하여 풀도록 합시다!
그리고, 플레이어마다 몇 번의 차례를 돌았는지 저장하기 위해서 플레이어 수와 동일한 배열을 만들어 줍시다.
이렇게 하면, turn이라는 변수를 통해서 (turn + 1) % 인원 을 통해서 몇 번째 사람이 말하는지 확인해 주면 됩니다!
그리고, 말을 할 때마다 몇 번 말했는지에 대한 정보를 저장하는 배열을 1 증가 시키면 되죠!
또한, 단어를 말할때 마다 해당 단어의 끝 자리를 prev라는 변수에 저장하고, map을 통해 문자열을 저장하면,
이 prev안에 저장된 단어와 다음에 나오는 첫 번째 글자의 비교 + map에 이미 나왔던 단어인지를 체크하면, 탈락자가 나오는지 알 수 있습니다!
간단한 예제를 통해 확인해보겠습니다 !
처음시작은 1 번 부터이고, 1번은 tank를 말했기 때문에 map에는 tank만 들어있습니다.
2번이 kick을 말하지만, map에도 들어있고, 뒤의 끝 말이 현재의 시작 말과 똑같기 때문에 계속 진행합니다.
3번이 know를 말하지만, 문제가 없습니다.
3 번에서 4번으로 가야하지만, 3 % 3 + 1을 통해 1로 변환해 줍니다!
1번이 wheel을 말하지만, 여전히 문제가 없습니다.
여전히 문제 없습니다. map만 늘어납니다.
중간을 생략하고, 이제 3번의 차례에 root 다음에 tank를 말했습니다. 앞의 단어의 끝과 현재 단어의 시작이 같지만, tank는 이미 map 안에 들어있는 단어이기 때문에 문제가 생깁니다!
현재 3번 플레이어가 3번째 말하는 중이기 때문에 답은 [3,3] 을 출력합니다.
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include <string> #include <vector> #include <iostream> #include<map> using namespace std; map<string, bool> mp; int turns[10]; vector<int> solution(int n, vector<string> words) { mp.clear(); vector<int> answer; answer.resize(2); answer[0] = 0; answer[1] = 0; char last = words[0][words[0].size()-1]; mp[words[0]] = true; int turn = 1; turns[0]++; for(int i = 1; i < words.size(); i++){ string& str = words[i]; if(mp[words[i]] || last != str[0]) { answer[0] = turn + 1; answer[1] = turns[turn]+1; break; } mp[str] = true; turns[turn]++; last = str[str.size()-1]; turn = (turn+1)%n; } return answer; } | cs |
여담
map을 사용할 수 있다면 매우 쉽게 풀 수 있는 문제입니다!
시간 복잡도는 처음에 들어오는 단어의 개수가 N이라고 한다면, O(N)이 될 것입니다!
3. 지형 편집
문제 설명
XX 게임에서는 지형 편집 기능을 이용하여 플레이어가 직접 게임 속 지형을 수정할 수 있습니다. 이 게임에서는 1 x 1 x 1 크기의 정육면체 블록을 쌓아 게임 속 지형을 표현합니다. 이때, 블록이 공중에 떠 있거나, 블록 하나가 여러 개의 칸에 걸쳐 놓일 수는 없습니다. 따라서 지형을 편집하기 위해서는 각 칸의 제일 위에 블록 1개를 새로 추가하거나, 제일 위에 있는 블록 한 개를 삭제하는 방식으로 지형을 수정해야 합니다. 이때, 블록 한 개를 새로 추가하거나 삭제하기 위해서는 게임머니를 사용해야 하므로 몇 개의 블록을 추가하고 삭제할지 신중한 선택이 필요합니다.
이 게임을 즐기던 한 플레이어는 N x N 크기의 지역에 자신만의 별장을 만들고 싶어졌습니다. 이를 위해서는 울퉁불퉁한 지형의 모든 칸의 높이가 같아지도록 만들어야 합니다. 이때, 블록 한 개를 추가하려면 P의 비용이, 제거하려면 Q의 비용이 들게 됩니다.
다음은 블록 한 개를 추가할 때 5의 비용이, 제거할 때 3의 비용이 드는 경우, 3 x 3 넓이의 모든 칸의 블록 높이가 같아지도록 만드는 예시입니다.
위 그림과 같이 지형 블록이 놓여 있는 경우 모든 칸의 높이가 3으로 같아지도록 한다면 다음과 같은 모양이 됩니다.
이를 위해서는 3보다 높은 칸의 블록 2개를 제거하고, 3보다 낮은 칸에 총 8개의 블록을 추가해야 하며, 2 x 3 + 8 x 5 = 46의 비용이 들게 됩니다.
그러나 아래 그림과 같이 모든 칸의 높이가 2로 같아지도록 할 때는 6개의 블록을 제거하고, 3개의 블록을 추가하면 6 x 3 + 3 x 5 = 33의 비용이 들게 되며, 이때가 최소비용이 됩니다.
현재 지형의 상태를 나타내는 배열 land와 블록 한 개를 추가하는 데 필요한 비용 P, 블록 한 개를 제거하는 데 필요한 비용 Q가 매개변수로 주어질 때, 모든 칸에 쌓여있는 블록의 높이가 같아지도록 하는 데 필요한 비용의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
제한사항
land는 N x N 크기의 2차원 배열이며, N의 범위는 1 ≤ N ≤ 300입니다.
land의 각 원소는 각 칸에 놓여 있는 블록의 수를 나타내며, 0 이상 10억 이하의 정수입니다.
각 칸에 블록 하나를 추가하는 데는 P, 제거하는 데는 Q의 비용이 들며, P, Q의 범위는 1 ≤ P, Q ≤ 100인 자연수입니다.
입출력 예
land P Q result
[[1, 2], [2, 3]] 3 2 5
[[4, 4, 3], [3, 2, 2], [ 2, 1, 0 ]] 5 3 33
입출력 예 설명
입출력 예 #1
모든 땅의 높이를 1로 맞추는 데는 블록 4개를 제거해야 하므로 8의 비용이 듭니다.
모든 땅의 높이를 2로 맞추는 데는 블록 1개를 추가하고 블록 1개를 제거해야 하므로 5의 비용이 듭니다.
모든 땅의 높이를 3으로 맞추는 데는 블록 4개를 추가해야 하므로 12의 비용이 듭니다.
따라서 최소 비용은 5이므로 5를 return 합니다.
입출력 예 #2
문제의 예시와 같으며 최소 비용은 33입니다.
어떻게 풀까?
문제에서 높이는 10억 까지 나올 수 있습니다! 모든 땅의 높이는 0부터 10억까지 맞추는데에 정답이 존재할 것입니다.
그리고, 문제에서 가장 비용이 작은 지점에 대해서 생각해봅시다! 해당 높이에서는 높이가 증가하던, 감소하던 비용이 증가하는 지점일 것입니다!
왜냐하면, 비용이 최소가 되는 지점이기 때문이죠! 그리고 맞추려고 하는 높이가 낮아질수록이던, 높아질수록이던 가장 최소인 비용보다는 계속해서 늘어날 것입니다.
그래프로 나타내면 아래로 오목한 그래프가 나오겠죠!
그리고 아래로 볼록한 그래프의 특징은 기울기가 항상 증가한다는 점 입니다!!
즉, 파라메트릭 서치를 통해서, 기울기가 0이 되는 점이나, 그에 가까운 곳들 근처의 지점들을 비교해서 가장 비용이 적게 드는 지점을 고르면 됩니다!!
그렇다면, 한 높이의 지점이 h라고 했을 때, 이 높이를 맞추기위한 비용은 어떻게 구할 수 있을까요??
블록을 새로 놓는데는 P의 비용이, 제거하는데에는 Q의 비용이 듭니다.
n*n의 평면을 보면서
h보다 높은 지점은 (높이 - h)*P 만큼의 비용이 들 것입니다!
그리고 h보다 낮은 지점은 (h-높이) * Q 만큼의 비용이 들겠죠.
이를 이용하면, 높이 정보를 통해서 
이를 통해, 0과 10억 사이에서 파라메트릭 서치를 통해 m지점과 m+1지점에서의 기울기를 비교해서 0이 되거나 0과 가까운 부분을 찾아서
가장 비용이 작은 높이를 출력하면 답을 구할 수 있습니다!!
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #include<vector> #include<cstdio> using namespace std; int n; //높이가 height일 때의 가격 long long cal(vector<vector<int> >& vec, long long height, int P, int Q){ long long res = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ long long mul = vec[i][j] - height > 0 ? Q : -P; res += (long long)(vec[i][j] - height) * mul; } } return res; } long long solution(vector<vector<int> > land, int P, int Q) { n = land.size(); long long answer = 0x7fffffffffffffff; //최대 높이 찾기 int s = 0, e = 300; int m; //기울기로 이분 탐색 while(s <= e){ m = (s+e)/2; long long res[2] = {cal(land, m, P,Q), cal(land, m+1, P,Q)}; if(res[0] == res[1]) break; if(res[0] < res[1]){ e = m - 1; } else{ s = m + 1; } } //오차가 있을 수 있음 for(int i = m - 1; i <= m+1; i++) { long long temp = cal(land, i, P, Q); answer = answer > temp ? temp : answer; } return answer; } | cs |
여담
높이를 h로 정했을 때의 가격을 정하는 부분의 시간 복잡도가 
총 
4. 예산
S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.
물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.
부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원해 줄 수 있는지 return 하도록 solution 함수를 완성해주세요.
제한사항
d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다.
d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100,000 이하의 자연수입니다.
budget은 예산을 나타내며, 1 이상 10,000,000 이하의 자연수입니다.
물품을 구매해 줄 수 있는 부서 개수의 최댓값을 return 하세요.
입출력 예
d budget result
[1,3,2,5,4] 9 3
[2,2,3,3] 10 4
입출력 예 설명
입출력 예 #1
각 부서에서 [1원, 3원, 2원, 5원, 4원]만큼의 금액을 신청했습니다. 만약에, 1원, 2원, 4원을 신청한 부서의 물품을 구매해주면 예산 9원에서 7원이 소비되어 2원이 남습니다. 항상 정확히 신청한 금액만큼 지원해 줘야 하므로 남은 2원으로 나머지 부서를 지원해 주지 않습니다. 위 방법 외에 3개 부서를 지원해 줄 방법들은 다음과 같습니다.
1원, 2원, 3원을 신청한 부서의 물품을 구매해주려면 6원이 필요합니다.
1원, 2원, 5원을 신청한 부서의 물품을 구매해주려면 8원이 필요합니다.
1원, 3원, 4원을 신청한 부서의 물품을 구매해주려면 8원이 필요합니다.
1원, 3원, 5원을 신청한 부서의 물품을 구매해주려면 9원이 필요합니다.
3개 부서보다 더 많은 부서의 물품을 구매해 줄 수는 없으므로 최대 3개 부서의 물품을 구매해 줄 수 있습니다.
입출력 예 #2
모든 부서의 물품을 구매해주면 10원이 됩니다. 따라서 최대 4개 부서의 물품을 구매해 줄 수 있습니다.
어떻게 풀까?
마찬가지로 그리~디 한 문제입니다.
이 문제는 최대의 가격을 구하는 것이 아닙니다! 물품을 구매해줄 수 있는 최대 부서의 개수를 구하는 것입니다!
어떻게 구할 수 있을까요??
당연히, 많은 부서를 사주기 위해서는 제일 신청하는 금액이 적은 부서들부터 물건을 사 주면 됩니다.
즉, 처음에 입력받은 신청 금액들을 오름차순으로 정렬한 뒤에, 맨 앞에서부터 금액을 누적해가면서 누잭된 금액이 물품을 구매해줄수 있는 가격을 넘는다면 지금까지 물건을 사준 부서의 개수를 출력하면 끝납니다!
허무하군요!
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include <iostream> #include <stdio.h> #include <string> #include <vector> #include<algorithm> using namespace std; int solution(vector<int> d, int budget) { int answer = 0; sort(d.begin(), d.end()); int value = 0; int i = 0; while(i < d.size()&& value + d[i] <= budget){ value += d[i]; i++; answer++; } return answer; } | cs |
여담
정렬하는데 걸리는 시간이 가장 길기 때문에, 시간 복잡도는 