2021 KAKAO BLIND RECRUITMENT 문제 연습

문제 출처: 코딩테스트 연습 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습

---

신규 아이디 추천

주어진 문자열을 규칙에 맞게 변형하는 문제이다. 문제만 잘 읽으면 어렵지 않게 구현할 수 있다. 주어지는 문자열의 길이가 최대 $1,000$이므로 시간복잡도에 크게 신경쓰지 않고 문제를 풀어도 된다. 사실 코딩테스트가 다 그렇다.

메뉴 리뉴얼

대충 읽으면 헷갈리기 쉬운 문제. 가장 많이 주문된 조합의 메뉴를 골라야 하는 문제이다. 이때 조합의 길이는 $l \in orders$이고, 조합에서 2번 이상 주문된 메뉴 중 가장 많이 주문된 메뉴를 모두 골라야 한다.

 

어렵지 않게 풀이를 생각할 수 있다.

1. $\forall order \in orders$에 대해 메뉴 $l$개를 고르는 모든 조합을 구한다.
2. 2번 이상 등장한 조합 중 가장 많이 등장한 조합을 모두 고른다.
3. 고른 조합을 $answer$에 추가한다.

그런데 $order$에서 $l$개를 고르는 조합을 구현하기가 귀찮다까다롭다. 이거 때문에 Python으로 풀었다. Python의 ``itertools.combinations``와 ``collections.Counter``를 사용하면 편리하다.

 

코딩 테스트 환경 특성상 중간 결과값을 확인하기 까다로우므로, 예외 처리에 주의하자.

순위 검색

조건에 맞는 사람의 수를 검색하는 문제이다. 개발언어, 지원 직군 등은 하나의 값만을 가질 수 있고, 검색 조건도 하나 또는 전부로 단순한 편이다. 각 속성이 하나의 값만을 가질 수 있기 때문에 점수를 잘 나누어 저장하고 검색하면 된다. 문자열을 인덱스로 바꾸는 방법은 여러 가지가 있는데, 나는 ``std::map<std::string, int>``를 사용했다. 귀찮지만 가장 확실한 방법이다.

 

속성이 4개이므로 ``std::vector<int>``의 4차원 배열을 선언하자. 인덱스 순서는 개발언어, 지원 직군, 지원 경력구분, 소울푸드이다. 

std::vector<int> scores[3][2][2][2];

인덱스를 통해 속성의 값을 알 수 있으므로 벡터에는 점수만 저장해도 된다. 이것저것 다 넣으면 시간 초과 난다. 

 

이제 쿼리를 수행해야 한다. 위에서 말했듯이 쿼리가 매우 단순하다. 하나 또는 전부이기 때문에 4중 for문으로 배열을 순회하면 된다. for 내부 변수의 시작과 끝을 잘 정하기만 하면 된다.

합승 택시 요금

읽자마자 보여야 한다. 플로이드 와샬이다. 안 보인다면 백준에서 플로이드 와샬 문제를 많이 풀어 보자.

 

$n$이 최대 $200$이기 때문에 플로이드 와샬을 적용하는 데에 무리가 없다. 풀이는 다음과 같다.

1. 임의의 두 지점 $i$와 $j$ 사이의 최저 요금 $cost[i][j]$를 플로이드 와샬로 구한다.
2. A와 B가 $i$번 지점까지 합승할 때의 최저 요금 $cost[s][i] + cost[i][a] + cost[i][b]$ 중 가장 작은 값을 구한다.
3. 위에서 구한 값과 A와 B가 합승하지 않을 때의 최저 요금 $cost[s][a] + cost[s][b]$을 비교하여 더 작은 값을 구한다.

간단하죠?

이 정도는 즉석에서 구현할 수 있어야 한다.

광고 삽입

여기서부터 난이도가 확 올라간다.

 

뭔가 자주 본 듯한 문제. 언뜻 보면 선분이 가장 많이 겹쳐있는 구간을 구해야 하는 문제로 보이지만, 그렇지 않다. 요지는 누적 재생 시간이 가장 긴 구간을 찾으라는 것이다.

 

흠.. 일단 입력으로 문자열이 주어지므로 모조리 정수로 바꿔놓고 생각해 보자. 그러고 보니 ``play_time``의 최댓값 ``99:59:99``를 초 단위로 변환하면 $359,999$이다. 생각보다 크지 않은데? 이정도면 ``play_time`` 크기의 배열을 하나 만들어도 되겠다. 그러니까 대략 다음과 같다.

 

$graph[i]$: $0$초부터 $i$초까지 누적 재생 시간의 합

 

이렇게 하면 $i$초와 $j$초 사이의 누적 재생 시간을 $graph[j] - graph[i]$로 아주 쉽게 구할 수 있다. 좋은데?

 

이제 우리의 목표는 $graph$ 배열을 만드는 것이다. 아주 쉽게 각 로그의 처음부터 끝까지 $graph$값을 1씩 증가시키면 안 된다. 이러면 시간 초과가 난다. 더 효율적인 풀이를 생각해 보자.

// 시간 초과
for (auto &log: logs)
{
	for (int time = log.start + 1; time <= log.finish; time++)
    {
    	graph[time]++;
    }
}

$i$초부터 $i+1$초 사이 구간을 재생한 사람의 수를 $v$라고 하면, $graph[i + 1] = graph[i] + v$이므로 동적 계획법을 이용해 $graph$를 선형 시간에 계산할 수 있다. 그런데 $v$ 역시 동적 계획법으로 구할 수 있다. $v$의 초기값은 0이고, 각 시간마다 얼마나 많은 사람이 재생을 시작하고 멈추는지에 따라 값이 바뀐다. 따라서 시청자들의 재생 구간의 시작과 끝을 정리해 두면 $v$를 쉽게 계산할 수 있다.

vector<pair<ll, ll>> delta; // <시간, 증감>
for (auto &log: logs)
{
    // 문자열을 정수(초 단위)로 변환
    auto start = to_timestamp(log.substr(0, 8)), end = to_timestamp(log.substr(9, 8));
    delta.emplace_back(start, 1);
    delta.emplace_back(end, -1);
}
// 시간 순으로 정렬
sort(delta.begin(), delta.end());

이렇게 하면 시간 순서대로 사람이 들어오고 나간 기록을 저장할 수 있다. 이제 $graph$를 계산해 보자.

vector<ll> graph;    // graph[i]: 0 ~ i초까지의 누적 재생시간
graph.push_back(0);
ll idx = 0, val = 0; // val:  t ~(t+1)초 구간을 재생중인 사람의 수
for (int t = 0; t <= ptime; t++)
{
    while (idx != delta.size() && delta[idx].first == t)
    {
        val += delta[idx].second;
        idx++;
    }
    if (t == 0)
        graph.push_back(val);
    else
        graph.push_back(graph.back() + val);
}

같은 시간에 여러 사람이 들어오고 나갈 수 있으므로 while문을 사용하여 값의 변화를 모두 반영하였다. $graph$를 계산했으니 이제 길이가 ``adv_time``인 구간 중 값의 차이가 가장 큰 구간을 찾자. 이건 쉽게 할 수 있겠지?

 

주의: ``int``를 쓰면 안 된다! ``long long``을 사용해야 정답을 받을 수 있다. $300,000^{2}$가 ``int`` 범위를 벗어나기 때문이다.

 

아이디어는 의외로 어렵지 않았으나 구현이 빡셌던 문제. 

카드 짝 맞추기

탐색 문제이긴 한데, 상태를 어떻게 저장하지? 단순히 빈 칸만 표시해야 하는 경우라면 비트마스크를 사용하면 되지만, 지금은 카드의 종류(4가지)까지 저장해야 하기 때문에 비트마스크를 사용하기 어렵다. 한 칸이 가질 수 있는 상태가 5가지이므로 한 칸을 표현하려면 최소한 3비트가 필요하다. 격자를 나타내는 데는 최소 48비트. 또, 커서의 위치와 카드 한 장이 뒤집혀 있는지도 알아야 한다. 뭐 이리 저장할 게 많아?

 

아이디어가 잘 떠오르지 않아서 풀이를 검색했다. 남의 풀이를 여기에 적는 것은 적절하지 못하므로 생략하겠다.

매출 하락 최소화

대충 트리 DP같긴 하다. 근데 식을 어떻게 세워야 하지? 사실 이 문제도 풀이를 검색했다. 한 마디만 하자면, DP식을 최대한 간단하게 세우자. 구현은 그 다음의 문제이다.

---

최종 점수: 5 / 7

실제 테스트에서도 이 정도로 풀 수 있을까? 솔직히 잘 모르겠다. 코테 치는 연습을 많이 해봐야 할듯.