2018 프로그래머스 서머 코딩 해설

1. 숫자 게임

[ Greedy/ Sorting ]

 

  Greedy하게 접근해보자. A팀의 점수를 알고 있다. 여기서 B팀의 순서를 결정하여 최대 이길 수 있는 회수를 결정한다. 이기기 위해서는 A 팀원의 수보다 큰 수를 B가 내야한다.

  B의 최대값을 X라고 하자, A의 최대값을 Y라고 하자. 그러면 X가 Y보다 작다면, 답은 명확하게 0이다. 다르게 표현하자면, X가 Y보다 크다면 X와 Y를 짝을 지어주자. 그러면 답은 1이 증가한다.

  만약 B안에 X보다 작고 Y보다 큰 값이 있다면 어떻게 될까. 어떻게 되든 X는 "반드시" 소모되며 A의 모든 요소보다 크기 때문에 큰 값끼리 묶어 주는 것이다.

 

 

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> A, vector<int> B) {
	int answer = 0,i;
	priority_queue<int> qA,qB;
    for(i=0;i<(int)A.size();i++){
        qA.push(-A[i]);
        qB.push(-B[i]);
    }
    while(!qA.empty() && !qB.empty()){
        if(-qA.top() < -qB.top()){
            qA.pop();
            answer++;
        }
        qB.pop();
    }
	return answer;
}

 

 

 

2. 지형 편집

[ Ternary search/ 구현 ]

 

  board 상의 가장 낮은 위치를 low, 가장 높은 위치를 high라고 하자. 명확하게 목표 높이 k가 low보다 낮거나 high보다 높으면 반드시 비용이 더 발생하게 된다. 따라서 답은 [low, high]에 존재하게 된다.

  높이 k에 대해 생각해보자. 높이 k+1를 목표로 했을 대, 높이 k에서의 채워야 하는 블록 수 Pn과 제거해야하는 블록 수 Qn이라고 할 때, 높이 k+1가 됐을 때, Pn은 Qn의 "일부"를 가져오게 된다. 이 "일부"는 0보다 크다.

이 값은 일정하지 않고 때마다 다르기 때문에 선형적이진 않다. 또한 전체 비용적으로 보면 이 변화량 D에 대해 abs(P-Q)*D 만큼 생긴다.

  따라서 높이 k에 대해 k=[low,high] 모든 비용을 그래프로 나타낸다면 극소점을 하나 갖는 그래프가 나온다. 따라서 이를 찾기 위해 삼분탐색을 적절하게 수행하자. 이 그래프는 이산 그래프이므로 적절히 범위를 주어 double 오차를 극복하도록 한다.

 

  a_ij를 i행 j열에 있는 높이, k를 목표 높이, x를 추가해야 하는 블록 수, y를 제거해야하는 위치 수로 정의하자.

  1. x + y <= N^2이다.

  2. 최소값 찾기

총 비용 = sigma P * (k - a_ij) if(k > a_ij) + sigma Q * (a_ij - k) if (k < a_ij) = Pxk + QN^2k - Qxk - sigma P * (a_ij) if(k > a_ij) + sigma Q * (a_ij) if (k < a_ij) = (P-Q)xk + QN^2k - sigma P * (a_ij) if(k > a_ij) + sigma Q * (a_ij) if (k < a_ij)

  f(k) = (P-Q)xk로 두자

  x는 계단함수고, f(k)는 (P-Q)x를 기울기로 두는 직선들을 그어주면 되므로 P > Q일 때는 증가하는 그래프가, P < Q일 때는 감소하는 그래프가 생긴다. 계단 함수의 끊기는 지점에서 이전 함수의 값이 다음 함수의 값를 역전할 수 없는 구조임을 확인하자. 그러면 이 f(k)는 최소값을 찾기 위해서 큰 의미를 가지지 않는다.

k: 목표 높이, f(k) = (P-Q)xk

  다시 수식을 가져와서

총 비용 = f(k) + QN^2k - sigma P * (a_ij) if(k > a_ij) + sigma Q * (a_ij) if (k < a_ij)

  여기서 QN^2k 역시 일차식이므로 필요한 데이터만 정리해보면 아래 값이 최소값을 찾기위한 핵심 수식임을 알 수 있다.

-sigma P * (a_ij) if(k > a_ij) + sigma Q * (a_ij) if (k < a_ij)

  수식 자체를 보면 k에 따라 P가 감소하거나 Q가 증가하거나 한다. 이는 추가해야하는 위치의 수와 제거해야하는 위치의 수 x, y에 따라 달라진다. k가 증가함에 따라 추가해야하는 x값은 증가하거나 유지, 반대로 y값은 감소하거나 유지된다. 

  k가 증가할 때,

  1. x값이 증가하는 경우 - 현재 높이를 k라고 하면 a_ij가 정확히 k-1인 위치의 수만큼 x가 증가한다.

  2. y값이 감소하는 경우 - 현재 높이를 k라고 하면 a_ij가 정확히 k인 위치의 수만큼 y가 감소한다.

  따라서 y의 감소량은 x의 증가량으로 변경되는 시점 간격은 정확히 1만큼 차이가 나고 이로 인해 위 수식은 마치 2차원 그래프를 나타내는 것처럼 보이게 되고 여기서 최소점을 찾으면 되게된다. 이는 삼분탐색으로 구현 가능하다.

k: 목표 높이, x: 추가해야 하는 블록 수, y: 제거해야 하는 블록 수

 

 

#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
ll max_v(ll a, ll b) { return a > b ? a : b; }
ll min_v(ll a, ll b) { return a < b ? a : b; }
inline ll cal(vector<vector<int>>& land, int P, int Q, ll st, int n) {
    ll s = 0;
    for (int i = 0; i<n; i++) for (int j = 0; j<n; j++)
        s += (land[i][j] - st) * (land[i][j] - st > 0 ? Q : -P);
    return s;
}
ll solution(vector<vector<int>> land, int P, int Q)
{
    ll answer = -1, i, j, k, n = (ll)land.size();
    double l2h, lh2, s1, s2, l = 1, r = 0, mid;
    for(i=0;i<n;i++) for(j=0;j<n;j++)
        r = max_v(r, land[i][j]);
    for (i = 0; i<64; i++) {
        l2h = (2 * l + r) / 3.;
        lh2 = (l + 2 * r) / 3.;
        s1 = cal(land, P, Q, l2h, n);
        s2 = cal(land, P, Q, lh2, n);

        if (s1 > s2) l = l2h;
        else r = lh2;
    }
    answer = 1e17;
    mid = (l + r) / 2;
    for(i=mid-10;i<=mid+10;i++)
        answer = min_v(answer, cal(land, P, Q,i, n));

    return answer;
}

 

 

 

3. 영어 끝말잇기

[ 구현 ]

 

  쭉 순회하면서 사용된적이 있는지, 아니면 첫 글자가 알맞지 않은지 확인만하면 된다.

 

 

 

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

using namespace std;

vector<int> solution(int n, vector<string> words) {
	vector<int> answer;
	set<string> used;
	int i;
	char bef = words[0].back();
    used.insert(words[0]);
	for(i=1;i<(int)words.size();i++){
		if(bef != words[i][0] || used.find(words[i]) != used.end()){
			break;
		}
		bef = words[i].back();
        used.insert(words[i]);
	}
	if(i == (int)words.size()) {
		answer.push_back(0); answer.push_back(0);
	} else {
		answer.push_back(i%n+1);
		answer.push_back(i/n+1);
	}
	
	return answer;
}

 

 

 

4. 예산

[ Greedy/ Sorting ]

 

  Greedy하게 접근하자. 최대한 많이 나눠주기 위해서는 예산이 적게 드는 부서에게만 부여해주면 된다.

  정렬하여 처음부터 순회하면서 예산이 떨어질 때까지 나눠주자.

 

 

 

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

using namespace std;

int solution(vector<int> d, int budget) {
    int answer = 0, i;
    sort(d.begin(), d.end());
    for(i=0;i<(int)d.size();i++){
        if(d[i] > budget) break;
        budget -= d[i];
    }
    return answer = i;
}