grep

Engineering

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

tony.mb카카오

2022년 1월 14일

원문에서 보기 ↗

지난 2021년 9월 11일 토요일 오후 2시부터 7시까지 5시간 동안 2022 KAKAO BLIND RECRUITMENT 1차 코딩 테스트가 진행되었습니다. 테스트에는 총 7개의 문제가 출제되었으며, 개발 언어는 C++, Java, JavaScript, Kotlin, Python, Swift 총 6가지가 제공되었습니다.

문제는 작년과 마찬가지로 쉬운 난이도에서 어려운 난이도 순으로 배치했습니다. 6번 문제를 제외한 나머지 문제는 테스트 케이스를 모두 통과해야 정답으로 인정되었고, 부문 점수는 부여되지 않았습니다. 6번 문제에는 효율적인 풀이를 구현해야 통과되는 효율성 테스트를 추가했고, 효율성 테스트는 정확성 테스트와 별도의 점수가 부여되도록 배점을 설계했습니다.

그럼 각 문제들을 살펴보고 해설을 진행하겠습니다.

문제 1 - 신고 결과 받기

문제 설명

신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.

다음은 전체 유저 목록이 [“muzi”, “frodo”, “apeach”, “neo”]이고, k = 2(즉, 2번 이상 신고 당하면 이용 정지)인 경우의 예시입니다.

유저 ID신고 ID설명
“muzi”“frodo”"muzi"가 "frodo"를 신고했습니다.
“apeach”“frodo”"apeach"가 "frodo"를 신고했습니다.
“frodo”“neo”"frodo"가 "neo"를 신고했습니다.
“muzi”“neo”"muzi"가 "neo"를 신고했습니다.
“apeach”“muzi”"apeach"가 "muzi"를 신고했습니다.

각 유저별로 신고 당한 횟수는 다음과 같습니다.

유저 ID신고 당한 횟수
“muzi”1
“frodo”2
“apeach”0
“neo”2

위 예시에서는 2번 이상 신고당한 "frodo"와 "neo"의 게시판 이용이 정지됩니다. 이때, 각 유저별로 신고한 아이디와 정지된 아이디를 정리하면 다음과 같습니다.

유저 ID신고 ID정지 ID
“muzi”[“frodo”, “neo”][“frodo”, “neo”]
“frodo”[“neo”][“neo”]
“apeach”[“muzi”, “frodo”][“frodo”]
“neo”없음없음

따라서 "muzi"는 처리 결과 메일을 2회, "frodo"와 "apeach"는 각각 처리 결과 메일을 1회 받게 됩니다.

이용자의 id가 담긴 문자열 배열 id_list, 각 이용자가 신고한 이용자에 대한 정보가 담긴 문자열 배열 report, 정지 기준이 되는 신고 횟수 k가 매개변수로 주어질 때, 각 유저별로 처리 결과 메일을 받은 횟수를 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

입출력 예

id_listreportkresult
["muzi", "frodo", "apeach", "neo"]["muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"]2[2,1,1,0]
["con", "ryan"]["ryan con", "ryan con", "ryan con", "ryan con"]3[0,0]

입출력 예 설명

• 입출력 예 #1

문제의 예시와 같습니다.

• 입출력 예 #2

"ryan"이 "con"을 4번 신고했으나, 주어진 조건에 따라 한 유저가 같은 유저를 여러 번 신고한 경우는 신고 횟수 1회로 처리합니다. 따라서 "con"은 1회 신고당했습니다. 3번 이상 신고당한 이용자는 없으며, "con"과 "ryan"은 메일을 받지 않습니다. 따라서 [0, 0]을 return 합니다.

문제 풀이

이 문제는 해시 자료구조를 활용할 수 있는지 묻는 문제였습니다.

report를 하나씩 처리하면서 각 유저가 누구에게 신고를 당했는지 목록을 만듭니다.

[신고된 유저 아이디 1] : [신고한 유저 A, 신고한 유저 B, ... ]
[신고된 유저 아이디 2] : [신고한 유저 A, 신고한 유저 C, ... ]
...
[신고된 유저 아이디 N] : [신고한 유저 X, 신고한 유저 Y, ... ]

유저 아이디는 최대 1,000개, report의 길이는 최대 200,000이므로 신고된 유저 아이디를 배열에 관리한다면 최악의 경우 O(아이디 개수 * report의 길이) 만큼의 시간이 걸립니다. 따라서 신고된 유저 아이디를 해시(또는 연관 배열) 자료구조를 이용해 관리하면 효율적으로 목록을 완성할 수 있습니다. 이때, 신고한 유저 목록에는 같은 아이디가 중복되어 들어가지 않도록 주의해야 합니다.

위와 같이 목록을 만들었다면 신고된 유저 아이디를 순회하면서 정지 기준을 만족하는 유저가 있다면(신고한 유저 수가 k 이상이면) 신고한 유저 목록을 순회하면서 메일을 보냈다는 표시(카운트를 1 증가) 해주면 됩니다.

문제 2 - k 진수에서 소수의 개수 구하기

문제 설명

양의 정수 n이 주어집니다. 이 숫자를 k 진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

제한사항

입출력 예

nkresult
43767433
110011102

입출력 예 설명

• 입출력 예 #1

문제 예시와 같습니다.

• 입출력 예 #2

110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.

문제 풀이

이 문제는 진법 변환 후에 변환된 숫자를 0을 기준으로 파싱하고, 파싱 한 숫자를 소수 판별해 해결할 수 있는 문제입니다.

소수 판별하는 데에는 대표적으로 2가지 방법이 있습니다. 첫 번째로 에라토스테네스의 체가 있고, 두 번째는 어떤 수 n을 2부터 루트(n)까지 나눈 나머지가 모두 0이 아님을 확인하는 방법이 있습니다. 효율적인 소수 판별 알고리즘인 에라토스테네스의 체를 사용해서도 풀 수 있지만, 이 문제에서는 두 번째 방법으로도 충분히 해결할 수 있습니다.

이 문제의 제한사항을 살펴보면 n이 1부터 1,000,000까지이고 k는 3부터 10까지이므로, 1,000,000을 3진수로 바꾸면 1,212,210,202,001입니다. 일반적으로 진법 변환은 문자열을 사용해 구현하므로, 진법 변환된 문자열을 0을 기준으로 파싱 한 후에 소수를 판별하는 과정에서 정수 자료형으로 변환이 필요하게 됩니다. 이때, 개발 언어에 따라서 int 자료형의 표현 범위를 벗어날 수 있음을 유의해서 문제를 풀어야 합니다. 예를 들어 997,244를 3진수로 바꾸면 1,212,122,221,222가 됩니다. 이 숫자는 0이 없기 때문에 진법 변환된 숫자 그대로 정수 자료형으로 변환해서 소수 판별을 해야 하는데, 이는 int 자료형의 표현 범위를 벗어난다는 것을 알 수 있습니다.

문제 3 - 주차 요금 계산

문제 설명

주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 아래는 하나의 예시를 나타냅니다.

기본 시간(분)기본 요금(원)단위 시간(분)단위 요금(원)
180500010600
시각(시:분)차량 번호내역
05:345961입차
06:000000입차
06:340000출차
07:595961출차
07:590148입차
18:590000입차
19:090148출차
22:595961입차
23:005961출차
차량 번호누적 주차 시간(분)주차 요금(원)
000034 + 300 = 3345000 + ⌈(334 - 180) / 10⌉ x 600 = 14600
01486705000 +⌈(670 - 180) / 10⌉x 600 = 34400
5961145 + 1 = 1465000

주차 요금을 나타내는 정수 배열 fees, 자동차의 입/출차 내역을 나타내는 문자열 배열 records가 매개변수로 주어집니다. 차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 return 하도록 solution 함수를 완성해 주세요.

제한사항

입출력 예

feesrecordsresult
[180, 5000, 10, 600]["05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"][14600, 34400, 5000]
[120, 0, 60, 591]["16:00 3961 IN","16:00 0202 IN","18:00 3961 OUT","18:00 0202 OUT","23:58 3961 IN"][0, 591]
[1, 461, 1, 10]["00:00 1234 IN"][14841]

입출력 예 설명

• 입출력 예 #1

문제 예시와 같습니다.

• 입출력 예 #2

기본 시간(분)기본 요금(원)단위 시간(분)단위 요금(원)
120060591
시각(시:분)차량 번호내역
16:003961입차
16:000202입차
18:003961출차
18:000202출차
23:583961입차
차량 번호누적 주차 시간(분)주차 요금(원)
02021200
3961120 + 1 = 1210 +⌈(121 - 120) / 60⌉x 591 = 591

• 입출력 예 #3

기본 시간(분)기본 요금(원)단위 시간(분)단위 요금(원)
1461110
시각(시:분)차량 번호내역
00:001234입차
차량 번호누적 주차 시간(분)주차 요금(원)
12341439461 +⌈(1439 - 1) / 1⌉x 10 = 14841

문제 풀이

이 문제는 문자열 처리 능력과, 주어진 주차 요금표를 코드를 통해 정확히 구현할 수 있는지를 확인하는 문제였습니다.

특히, 이 문제는 입/출차 시각과 누적 주차 시간을 모두 '분’단위로 환산하여 저장하면 조금 더 쉽게 해결할 수 있습니다.

차량번호의 범위가 0000~9999이므로, 차량의 수는 최대 1만 대입니다. 이를 이용하여 두 배열 in_time, total_time을 다음과 같이 정의합니다.

그 후 records에 담긴 원소를 순차적으로 처리해 줍니다.

records를 모두 처리한 후에도 출차되지 않은 차량이 있다면, 즉, in_time[i] != -1인 모든 i번 차량에 대해서는 23시 59분(1439분)에 출차되었다고 간주하고, total_time[i]를 갱신해 줍니다.

위와 같은 방법으로 누적 주차 시간을 계산한 후, total_time[i] > 0 를 만족하는 모든 i번 차량에 대해서, 오름차순으로 주차 요금을 계산해서 배열에 담으면 문제를 해결할 수 있습니다.

문제 4 - 양궁 대회

문제 설명

카카오배 양궁대회가 열렸습니다.

라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원회는 한 선수의 연속 우승보다는 다양한 선수들이 양궁대회에서 우승하기를 원합니다. 따라서, 양궁대회 운영위원회는 결승전 규칙을 전 대회 우승자인 라이언에게 불리하게 다음과 같이 정했습니다.

  1. 어피치가 화살 n발을 다 쏜 후에 라이언이 화살 n발을 쏩니다.

  2. 점수를 계산합니다.

    * 예를 들어, 어피치가 10점을 2발 맞혔고 라이언도 10점을 2발 맞혔을 경우 어피치가 10점을 가져갑니다.
    * 다른 예로, 어피치가 10점을 0발 맞혔고 라이언이 10점을 2발 맞혔을 경우 라이언이 10점을 가져갑니다.
  1. 최종 점수가 더 높은 선수를 우승자로 결정합니다. 단, 최종 점수가 같을 경우 어피치를 우승자로 결정합니다.

현재 상황은 어피치가 화살 n발을 다 쏜 후이고 라이언이 화살을 쏠 차례입니다.

라이언은 어피치를 가장 큰 점수 차이로 이기기 위해서 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 구하려고 합니다.

화살의 개수를 담은 자연수 n, 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열 info가 매개변수로 주어집니다. 이때, 라이언이 가장 큰 점수 차이로 우승하기 위해 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 만약, 라이언이 우승할 수 없는 경우(무조건 지거나 비기는 경우)는 [-1]을 return 해주세요.

제한사항

입출력 예

ninforesult
5[2,1,1,1,0,0,0,0,0,0,0][0,2,2,0,1,0,0,0,0,0,0]
1[1,0,0,0,0,0,0,0,0,0,0][-1]
9[0,0,1,2,0,1,1,1,1,1,1][1,1,2,0,1,2,2,0,0,0,0]
10[0,0,0,0,0,0,0,0,3,4,3][1,1,1,1,1,1,1,1,0,0,2]

입출력 예 설명

• 입출력 예 #1

어피치와 라이언이 아래와 같이 화살을 맞힐 경우,

과녁 점수어피치가 맞힌 화살 개수라이언이 맞힌 화살 개수결과
1023라이언이 10점 획득
912라이언이 9점 획득
810어피치가 8점 획득
710어피치가 7점 획득
600
500
400
300
200
100
000

어피치의 최종 점수는 15점, 라이언의 최종 점수는 19점입니다. 4점 차이로 라이언이 우승합니다.

하지만, 라이언이 아래와 같이 화살을 맞힐 경우 더 큰 점수 차로 우승할 수 있습니다.

과녁 점수어피치가 맞힌 화살 개수라이언이 맞힌 화살 개수결과
1020어피치가 10점 획득
912라이언이 9점 획득
812라이언이 8점 획득
710어피치가 7점 획득
601라이언이 6점 획득
500
400
300
200
100
000

어피치의 최종 점수는 17점, 라이언의 최종 점수는 23점입니다. 6점 차이로 라이언이 우승합니다.

따라서 [0,2,2,0,1,0,0,0,0,0,0]을 return 해야 합니다.

• 입출력 예 #2

라이언이 10점을 맞혀도 어피치가 10점을 가져가게 됩니다.

따라서, 라이언은 우승할 수 없기 때문에 [-1]을 return 해야 합니다.

• 입출력 예 #3

어피치와 라이언이 아래와 같이 화살을 맞힐 경우,

과녁 점수어피치가 맞힌 화살 개수라이언이 맞힌 화살 개수결과
1001라이언이 10점 획득
901라이언이 9점 획득
812라이언이 8점 획득
723라이언이 7점 획득
600
512라이언이 5점 획득
410어피치가 4점 획득
310어피치가 3점 획득
210어피치가 2점 획득
110어피치가 1점 획득
010어피치가 0점 획득

어피치의 최종 점수는 10점, 라이언의 최종 점수는 39점입니다. 29점 차이로 라이언이 우승합니다.

하지만 라이언이 아래와 같이 화살을 맞힐 경우,

과녁 점수어피치가 맞힌 화살 개수라이언이 맞힌 화살 개수결과
1001라이언이 10점 획득
901라이언이 9점 획득
812라이언이 8점 획득
720어피치가 7점 획득
601라이언이 6점 획득
512라이언이 5점 획득
412라이언이 4점 획득
310어피치가 3점 획득
210어피치가 2점 획득
110어피치가 1점 획득
010어피치가 0점 획득

어피치의 최종 점수는 13점, 라이언의 최종 점수는 42점입니다. 이 경우도 29점 차이로 라이언이 우승합니다.

하지만, 첫 번째 경우와 두 번째 경우를 비교했을 때, 두 번째 경우가 두 경우 중 가장 낮은 점수인 4점을 더 많이 맞혔기 때문에 [1,1,2,3,0,2,0,0,0,0,0]이 아닌 [1,1,2,0,1,2,2,0,0,0,0]을 return 해야 합니다.

• 입출력 예 #4

여러 경우 중에서 가장 낮은 점수를 가장 많이 맞힌, 10~3점을 한 발씩 맞히고 나머지 두 발을 0점에 맞히는 경우인 [1,1,1,1,1,1,1,1,0,0,2]를 return 해야 합니다.

문제 풀이

이 문제는 완전 탐색, 구현 문제입니다. 이 문제는 DFS, 비트 마스킹, 중복조합 등등 다양한 방법으로도 풀이가 가능한데요, 가장 많은 풀이가 나온 DFS를 이용한 완전 탐색으로 풀이를 진행하겠습니다.

이 문제를 해결하기 위해서는 각 점수를 아예 안 맞추거나 어피치보다 1발을 더 맞히는 경우로 각 점수(10점 ~ 0점)마다 2가지(총 2048가지)를 완전 탐색하면 됩니다.

예를 들어, 어피치가 [2,0,1,1,0,0,0,0,0,0,0]처럼 화살을 맞췄을 경우 라이언은 과녁 점수 10점을 3발 맞추거나 0발 맞추거나만 선택하면 됩니다. 9점~0점도 동일한 방식으로 어피치보다 1발을 더 맞추거나 아예 안 맞추도록 구현하면 되고, 중간에 화살을 다 쐈을 경우는 나머지 과녁 점수를 모두 0발 맞춘 것으로 처리하면 됩니다. 만약 1점까지 쏘고도 화살이 남았을 경우는 남은 화살을 0점에 다 쏘도록 처리할 수 있습니다. 이렇게 가능한 모든 경우를 살펴보면서 라이언과 어피치의 최대 점수 차이를 구하면 됩니다.

만약 10점부터 0점까지를 0발부터 n발까지 하나씩 증가시키면서 완전탐색한다면 최악의 경우 시간 초과가 발생할 수 있는 점 유의하시길 바랍니다.

중복 조합으로 푸는 경우에도 10점부터 0점까지(11가지의 경우) 총, 10발의 화살을 쏘는 게 되기 때문에 11H10 = (11 + 10 - 1) C10 = 20C10 = 184,756으로 모든 경우의 수를 확인하면서 충분히 제한 시간 안에 문제를 해결할 수 있습니다.

문제 5 - 양과 늑대

문제 설명

2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수 보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 출발하면 양을 한 마리 모을 수 있습니다. 다음으로 1번 노드로 이동하면 당신이 모은 양은 두 마리가 됩니다. 이때, 바로 4번 노드로 이동하면 늑대 한 마리가 당신을 따라오게 됩니다. 아직은 양 2마리, 늑대 1마리로 양이 잡아먹히지 않지만, 이후에 갈 수 있는 모든 노드에는 늑대가 있고, 이어서 늑대가 있는 노드로 이동한다면(예를 들어 바로 6번 노드로 이동한다면) 양 2마리, 늑대 2마리가 되어 양이 모두 잡아먹힙니다. 여기서는 0번, 1번 노드를 방문하여 양을 2마리 모은 후, 8번 노드로 이동한 후(양 2마리 늑대 1마리) 이어서 7번, 9번 노드를 방문하면 양 4마리 늑대 1마리가 됩니다. 이제 4번, 6번 노드로 이동하면 양 4마리, 늑대 3마리가 되며, 이제 5번 노드로 이동할 수 있게 됩니다. 따라서 양을 최대 5마리 모을 수 있습니다.

각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해 주세요.

제한사항

입출력 예

infoedgesresult
[0,0,1,1,1,0,1,0,1,0,1,1][ [0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9] ]5
[0,1,0,1,1,0,1,0,0,1,0][ [0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10] ]5

입출력 예 설명

• 입출력 예 #1

문제의 예시와 같습니다.

• 입출력 예 #2

주어진 입력은 다음 그림과 같습니다.

0번 - 2번 - 5번 - 1번 - 4번 - 8번 - 3번 - 7번 노드 순으로 이동하면 양 5마리 늑대 3마리가 됩니다. 여기서 6번, 9번 노드로 이동하면 양 5마리, 늑대 5마리가 되어 양이 모두 잡아먹히게 됩니다. 따라서 늑대에게 잡아먹히지 않도록 하면서 최대로 모을 수 있는 양은 5마리입니다.

문제 풀이

4번 문제와 마찬가지로 이 문제 역시 다양한 방법으로 해결할 수 있는 문제인데요, 가장 많은 풀이가 나온 DFS를 이용한 완전탐색으로 풀이를 진행하겠습니다.

이 문제는 현재 위치, 현재까지 모은 양의 수, 늑대의 수, 그리고 다음으로 방문할 수 있는 노드 정보를 적절히 관리해 주면서 DFS를 이용해 완전탐색해서 해결할 수 있습니다. DFS를 수행하는 함수의 파라미터는 다음과 같이 구성할 수 있습니다.

현재 방문한 노드에 양이 있다면 양의 수를, 늑대가 있다면 늑대의 수를 1 증가시킵니다. 이때, xor 연산을 활용하면 아래와 같이 간단하게 구현할 수 있습니다. 현재 위치를 cur이라고 했을 때 현재 위치에 양이 있다면(info[cur]가 0인 경우) sheep에는 1이 더해지고, wolf에는 0이 더해집니다. 만약 늑대가 있다면 (info[cur]가 1이라면) sheep에는 0이 더해지고, wolf에는 1이 더해집니다.

sheep += info[cur] ^ 1  // xor
wolf += info[cur]

다음으로 양의 수와 늑대의 수를 비교합니다. 만약 늑대가 양보다 많다면 현재 노드를 방문하는 것은 불가능하므로 더 이상 탐색하지 않습니다.

양의 수가 늑대의 수보다 더 많다면 모은 양의 최댓값을 갱신하고, 현재 노드의 자식 노드들을 다음으로 방문할 수 있는 노드 집합에 추가합니다.

이제 '다음으로 방문할 수 있는 노드의 집합’에 들어있는 모든 노드를 하나씩 방문하며 DFS 탐색을 수행합니다. 이 때, 다음으로 방문하는 노드의 번호를 '다음으로 방문할 수 있는 노드의 집합’에서 제거해 주어야 합니다.

이러한 방식으로 완전 탐색이 종료되면 최대로 모을 수 있는 양의 수를 구할 수 있습니다.

문제 6 - 파괴되지 않은 건물

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.

적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.

예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.

첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.

세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다.

마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해 주세요.)

최종적으로 총 10개의 건물이 파괴되지 않았습니다.

건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return 하는 solution 함수를 완성해 주세요.

제한사항

정확성 테스트 케이스 제한사항

효율성 테스트 케이스 제한사항

입출력 예

boardskillresult
[ [5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5] ][ [1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1] ]10
[ [1,2,3],[4,5,6],[7,8,9] ][ [1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100] ]6

입출력 예 설명

• 입출력 예 #1

문제 예시와 같습니다.

• 입출력 예 #2

<초기 맵 상태>

첫 번째로 적이 맵의 (1,1)부터 (2,2)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

두 번째로 적이 맵의 (0,0)부터 (1,1)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

마지막으로 아군이 맵의 (2,0)부터 (2,0)까지 회복하여 100만큼 건물의 내구도를 높이면 아래와 같은 상황이 됩니다.

총, 6개의 건물이 파괴되지 않았습니다. 따라서 6을 return 해야 합니다.

문제 풀이

이 문제는 2차원 배열에서 구간의 변화를 어떻게 효율적으로 처리할지가 관건인 문제입니다. 가장 쉽게 생각할 수 있는 브루트 포스로 풀 경우 정확성 테스트 케이스는 모두 맞출 수 있지만, 시간 복잡도가 O(N * M * K)가 되어 효율성 테스트케이스에서 시간 초과가 발생하게 됩니다.

2차원 배열에 대한 구간의 변화를 처리하는 방법을 설명드리기 전에, 우선 1차원 배열을 효율적으로 처리할 수 있는 방법을 설명드리겠습니다.

예를 들어, [1,2,4,8,9]의 배열이 있고, 0번째부터 3번째 원소까지 2만큼 빼야 하는 상황이라고 가정하겠습니다. 즉, 배열을 [-1,0,2,6,9]로 만들고 싶은 상황입니다. 가장 쉬운 방법으로는 0번째부터 3번째 원소까지 반복문을 사용해 2만큼 빼주는 방법이 있지만, 이 방법은 O(M)의 시간 복잡도가 걸립니다.

O(M)의 시간 복잡도를 O(1)로 만들 수 있는 방법은 바로 누적합을 이용하는 방법입니다. 위의 예시의 경우 [-2,0,0,0,2]를 저장한 새로운 배열을 생성합니다. 이 배열을 앞에서부터 누적합하면 [-2,-2,-2,-2,0]이 되기 때문에 초기 배열인 [1,2,4,8,9]과 더해주면 [-1,0,2,6,9]를 얻을 수 있게 됩니다. 즉, 1차원 배열의 a번째 원소부터 b번째 원소까지 c만큼의 변화를 주겠다고 하면 새로운 배열의 a번째 원소에 c를 더하고 b+1번째 원소에 c를 빼면 됩니다.

이 방식으로 문제를 풀면 O(N * M * K)의 복잡도를 O(N * K)로 줄일 수 있지만, 이 또한 시간 초과가 발생합니다.

따라서 이 아이디어를 2차원 배열로 확장해 줘야 합니다. 이번엔 2차원 배열에서 (0,0)부터 (2,2)까지 n만큼 변화시키는 경우를 예로 들어보겠습니다.

배열의 행만 따로 봐서 위에서 설명한 아이디어를 하나의 행씩 적용시키면, 1차원 배열의 0번째 원소부터 2번째 원소까지 n만큼의 변화를 3개의 행에 적용시키는 것이 됩니다.

n 0 0 -n
n 0 0 -n
n 0 0 -n

위 행렬을 다시 열만 따로 보면, 가장 왼쪽 열의 0번째 원소부터 2번째 원소까지 n만큼의 변화와 가장 오른쪽 열의 0번째 원소부터 2번째 원소까지 -n만큼의 변화와 같습니다. 각 열에 위의 아이디어를 적용시키면 아래와 같습니다. 이런 식으로 2차원 배열에도 적용시킬 수가 있습니다.

n 0 0 -n
0 0 0 0
0 0 0 0
-n 0 0 n

즉, 2차원 배열에서 (x1,y1)부터 (x2,y2)까지 n만큼의 변화는 (x1,y1)에 +n, (x1,y2+1)에 -n, (x2+1,y1)에 -n, (x2+1,y2+1)에 +n을 한 것과 같습니다. 위 배열을 위에서 아래로 누적합한 뒤, 왼쪽에서 오른쪽으로 누적합하거나 왼쪽에서 오른쪽으로 누적합 한 뒤, 위에서 아래로 누적합하면 처음에 의도한 (0,0)부터 (2,2)까지 n만큼 변화시키는 배열이 나오는 것을 확인할 수 있습니다.

n n n 0
n n n 0
n n n 0
0 0 0 0

이러한 방법으로 skill의 한 원소를 O(1)만에 처리할 수 있다는 것을 알 수 있습니다. 따라서 위의 방법으로 K개의 skill을 모두 처리할 수 있는 배열을 만드는데 O(K)가 걸리게 됩니다. 그리고 해당 배열을 누적합 배열로 바꾸는 과정이 필요한데, 행과 열을 각각 누적합 해줘야 하기 때문에 O(N * M)가 걸리게 됩니다. 따라서 O(K + N * M)으로 문제를 해결할 수 있습니다.

이해를 돕기 위해 2번 테스트케이스를 예시로 추가 설명드리겠습니다.

  1. (1,1)부터 (2,2)까지 -4만큼 변화를 줘야 합니다. (배열의 (1,1)과 (3,3)에 -4, 배열의 (1,3)과 (3,1)에 4만큼 변화를 줍니다.)
     0    0    0    0
     0   -4    0    4
     0    0    0    0
     0    4    0   -4
  1. (0,0)부터 (1,1)까지 -2만큼 변화를 줘야 합니다. (배열의 (0,0)과 (2,2)에 -2, 배열의 (0,2)과 (2,0)에 2만큼 변화를 줍니다.)
    -2    0    2    0
     0   -4    0    4
     2    0   -2    0
     0    4    0   -4
  1. (2,0)부터 (2,0)까지 +100의 변화를 줘야 합니다. (배열의 (2,0)과 (3,1)에 100, 배열의 (2,1)과 (3,0)에 -100만큼 변화를 줍니다.)
    -2    0    2    0
     0   -4    0    4
    102  -100 -2    0
   -100   104  0   -4

이 배열을 이제 위에서 아래로 누적합 해주겠습니다.

-2    0    2    0
-2   -4    2    4
100  -104  0    4
 0    0    0    0

그다음 왼쪽에서 오른쪽으로 누적합 해주겠습니다.

-2   -2    0    0
-2   -6   -4    0
100  -4   -4    0
 0    0    0    0

이 배열을 board와 합쳐 주겠습니다.

1 2 3         -2  -2   0        -1  0  3
4 5 6    +    -2  -6  -4    =    2 -1  2
7 8 9         100 -4  -4        107 4  5

마지막 결과 배열과 같은 배열이 나왔습니다. 이 배열에서 0보다 큰 정수의 개수를 구하면 됩니다.

문제 7 - 사라지는 발판

문제 설명

플레이어 A와 플레이어 B가 서로 게임을 합니다. 당신은 이 게임이 끝날 때까지 양 플레이어가 캐릭터를 몇 번 움직이게 될지 예측하려고 합니다.

각 플레이어는 자신의 캐릭터 하나를 보드 위에 올려놓고 게임을 시작합니다. 게임 보드는 1x1 크기 정사각 격자로 이루어져 있으며, 보드 안에는 발판이 있는 부분과 없는 부분이 있습니다. 발판이 있는 곳에만 캐릭터가 서있을 수 있으며, 처음 캐릭터를 올려놓는 곳은 항상 발판이 있는 곳입니다. 캐릭터는 발판이 있는 곳으로만 이동할 수 있으며, 보드 밖으로 이동할 수 없습니다. 밟고 있던 발판은 그 위에 있던 캐릭터가 다른 곳으로 이동하여 다른 발판을 밟음과 동시에 사라집니다. 양 플레이어는 번갈아가며 자기 차례에 자신의 캐릭터를 상하좌우로 인접한 4개의 칸 중에서 발판이 있는 칸으로 옮겨야 합니다.

다음과 같은 2가지 상황에서 패자와 승자가 정해지며, 게임이 종료됩니다.

게임은 항상 플레이어 A가 먼저 시작합니다. 양 플레이어는 최적의 플레이를 합니다. 즉, 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이합니다. '이길 수 있는 플레이어’는 실수만 하지 않는다면 항상 이기는 플레이어를 의미하며, '질 수밖에 없는 플레이어’는 최선을 다해도 상대가 실수하지 않으면 항상 질 수밖에 없는 플레이어를 의미합니다. 최대한 오래 버틴다는 것은 양 플레이어가 캐릭터를 움직이는 횟수를 최대화한다는 것을 의미합니다.

아래 그림은 초기 보드의 상태와 각 플레이어의 위치를 나타내는 예시입니다.

위와 같은 경우, 플레이어 A는 실수만 하지 않는다면 항상 이길 수 있습니다. 따라서 플레이어 A는 이길 수 있는 플레이어이며, B는 질 수밖에 없는 플레이어입니다. 다음은 A와 B가 최적의 플레이를 하는 과정을 나타냅니다.

  1. 플레이어 A가 초기 위치 (1, 0)에서 (1, 1)로 이동합니다. 플레이어 A가 (0, 0)이나 (2, 0)으로 이동할 경우 승리를 보장할 수 없습니다. 따라서 무조건 이길 방법이 있는 (1, 1)로 이동합니다.
  2. 플레이어 B는 (1, 1)로 이동할 경우, 바로 다음 차례에 A가 위 또는 아래 방향으로 이동하면 발판이 없어져 패배하게 됩니다. 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이하기 때문에 (1, 1)로 이동하지 않습니다. (1, 2)에서 위쪽 칸인 (0, 2)로 이동합니다.
  3. A가 (1, 1)에서 (0, 1)로 이동합니다.
  4. B에게는 남은 선택지가 (0, 1)밖에 없습니다. 따라서 (0, 2)에서 (0, 1)로 이동합니다.
  5. A가 (0, 1)에서 (0, 0)으로 이동합니다. 이동을 완료함과 동시에 B가 서있던 (0, 1)의 발판이 사라집니다. B가 패배합니다.
  6. 만약 과정 2에서 B가 아래쪽 칸인 (2, 2)로 이동하더라도 A가 (2, 1)로 이동하면 됩니다. 이후 B가 (2, 1)로 이동, 다음 차례에 A가 (2, 0)으로 이동하면 B가 패배합니다.

위 예시에서 양 플레이어가 최적의 플레이를 했을 경우, 캐릭터의 이동 횟수 합은 5입니다. 최적의 플레이를 하는 방법은 여러 가지일 수 있으나, 이동한 횟수는 모두 5로 같습니다.

게임 보드의 초기 상태를 나타내는 2차원 정수 배열 board와 플레이어 A의 캐릭터 초기 위치를 나타내는 정수 배열 aloc, 플레이어 B의 캐릭터 초기 위치를 나타내는 정수 배열 bloc이 매개변수로 주어집니다. 양 플레이어가 최적의 플레이를 했을 때, 두 캐릭터가 움직인 횟수의 합을 return 하도록 solution 함수를 완성해 주세요.

제한사항

입출력 예

boardalocblocresult
[ [1, 1, 1], [1, 1, 1], [1, 1, 1] ][1, 0][1, 2]5
[ [1, 1, 1], [1, 0, 1], [1, 1, 1] ][1, 0][1, 2]4
[ [1, 1, 1, 1, 1] ][0, 0][0, 4]4
[ [1] ][0, 0][0, 0]0

입출력 예 설명

• 입출력 예 #1

문제 예시와 같습니다.

• 입출력 예 #2

주어진 조건을 그림으로 나타내면 아래와 같습니다.

이길 수 있는 플레이어는 B, 질 수밖에 없는 플레이어는 A입니다.

다음은 B가 이기는 방법 중 하나입니다.

  1. A가 (1, 0)에서 (0, 0)으로 이동
  2. B가 (1, 2)에서 (2, 2)로 이동
  3. A가 (0, 0)에서 (0, 1)로 이동
  4. B가 (2, 2)에서 (2, 1)로 이동
  5. A가 (0, 1)에서 (0, 2)로 이동
  6. B가 (2, 1)에서 (2, 0)으로 이동
  7. A는 어디로도 이동할 수가 없어 패배

위와 같이 플레이할 경우 이동 횟수 6번 만에 게임을 B의 승리로 끝낼 수 있습니다.

B가 다음과 같이 플레이할 경우 게임을 더 빨리 끝낼 수 있습니다. 이길 수 있는 플레이어는 최대한 빨리 게임을 끝내려 하기 때문에 위 방법 대신 아래 방법을 선택합니다.

  1. A가 (1, 0)에서 (0, 0)으로 이동
  2. B가 (1, 2)에서 (0, 2)로 이동
  3. A가 (0, 0)에서 (0, 1)로 이동
  4. B가 (0, 2)에서 (0, 1)로 이동
  5. A가 어디로도 이동할 수가 없어 패배

위와 같이 플레이할 경우 이동 횟수 4번 만에 게임을 B의 승리로 끝낼 수 있습니다. 따라서 4를 return 합니다.

• 입출력 예 #3

양 플레이어는 매 차례마다 한 가지 선택지밖에 고를 수 없습니다. 그 결과, (0, 2)에서 어디로도 이동할 수 없는 A의 패배합니다. 양 플레이어가 캐릭터를 움직인 횟수의 합은 4입니다.

• 입출력 예 #4

게임을 시작하는 플레이어 A가 처음부터 어디로도 이동할 수 없는 상태입니다. 따라서 A의 패배이며, 이동 횟수의 합은 0입니다.

문제 풀이

이 문제는 완전 탐색으로 해결할 수 있는 문제입니다. 문제에서 주어진 게임판의 크기가 크지 않고, 발판을 밟으면 사라진다는 조건이 있기 때문에 탐색해야 하는 가짓수가 크게 줄어듭니다. 따라서 완전 탐색을 하더라도 제한 시간 내에 충분히 풀 수 있습니다. 이번에는 재귀 함수를 이용한 완전 탐색으로 해설을 진행하겠습니다.

재귀 함수는 어떤 함수 내에서 자신을 다시 호출하여 작업을 수행하는 함수를 말합니다. 이 문제에서는 게임판의 상태에 따라 이번에 움직여야 하는 플레이어가 이길 수 있는지, 질 수밖에 없는지를 판단하고 판단한 결과와 이동한 횟수를 반환하는 재귀 함수를 구현해서 해결할 수 있습니다. 즉, 함수의 매개변수로 게임판의 상태, A의 위치, B의 위치 등을 넘겨주면, 이번 턴에 움직여야 하는 플레이어의 승패 여부와 총 이동 횟수를 알려주는 함수입니다.

플레이어들의 총 이동 횟수를 이용해 플레이어 A의 턴인지, B의 턴인지 구분하는 방식으로 하나의 재귀 함수로 구현할 수도 있지만, 설명 상의 편의를 위해서 A의 승패 여부와 플레이어의 총 이동 횟수를 반환하는 함수와 B의 승패 여부와 플레이어의 총 이동 횟수를 반환하는 함수를 분리하고, 각각 A 함수와 B 함수라고 부르겠습니다. 이 함수들은 플레이어가 상하좌우 4가지 방향 중 이동할 수 있는 방향으로 이동하여 게임판의 상태를 바꾼 뒤, 그 상태를 상대 플레이어에게 넘기는 방식으로 동작합니다. 즉, A 함수는 플레이어 A를 움직이는 함수, B 함수는 플레이어 B를 움직이는 함수가 되고, A 함수에서는 B 함수를, B 함수에서는 A 함수를 호출하게 됩니다.

A 함수와 B 함수는 플레이어의 승패 여부와 이동 횟수를 반환합니다. 따라서 A 함수에서는 B 함수의 호출 결과를 통해 플레이어 B의 승패 여부와 총 이동 횟수를 알 수 있고, B 함수에서는 플레이어 A의 승패 여부와 총 이동 횟수를 알 수 있습니다. 만약 상대 턴으로 넘어간 모든 함수의 결과가 '패배’일 경우, '나’는 반드시 이길 수 있습니다. 반대로, 상대 턴으로 넘어간 모든 함수의 결과가 '승리’일 경우, '나’는 무조건 질 수밖에 없습니다. 따라서 함수를 호출한 결과를 종합해 ‘이길 수 있는 방법이 있는지’, '질 수밖에 없는지’를 구할 수 있습니다. 그리고 문제에 '양 플레이어는 최적의 플레이를 합니다.'라는 조건이 있기 때문에, 승리하는 플레이어는 최소한의 이동으로 승리하고 패배하는 플레이어는 최대한의 이동으로 패배해야 합니다. 따라서 이동 횟수의 최댓값 또는 최솟값을 상대방의 결과에 따라 적절하게 반환해 주면 됩니다.

이러한 방식으로 A 함수와 B 함수를 구현하고, '게임은 항상 플레이어 A가 먼저 시작합니다.'라는 문제 조건에 의해 A 함수를 호출해 줍니다. 그러면 A 함수는 함수 내부에서 B 함수를 호출하고, B 함수 역시 함수 내부에서 A 함수를 호출하면서 가능한 모든 경우에 대해서 탐색하게 되고, 결국 초기 매개변수들을 전달한 A 함수의 결과로 최적의 이동 횟수가 반환되는 것을 확인할 수 있습니다.

마치며

지금까지 2022 KAKAO BLIND RECRUITMENT 1차 코딩 테스트 문제와 풀이에 대해 살펴보았습니다.

설명 드린 풀이 외에도 다양한 풀이법이 있기 때문에, 풀이를 암기하기보다는 어떠한 흐름으로 풀이가 진행되는지를 이해하고, 다른 방법으로 풀 수는 없는지에 대해 고민해 보면 큰 도움이 될 것입니다.

또한 이전에 진행했던 KAKAO BLIND RECRUITMENT와 인턴십 코딩 테스트 문제들에 대해서도 해설을 제공하고 있으니 참고하시기 바랍니다.

마지막으로 2022 KAKAO BLIND RECRUITMENT에 많은 관심 가져 주셔서 감사드리며, 5시간이라는 긴 시간동안 테스트 응시하시느라 정말 고생 많으셨습니다!

✔️ 카카오 온라인 코딩 테스트 문제해설 바로가기