지난 2021년 9월 11일 토요일 오후 2시부터 7시까지 5시간 동안 2022 KAKAO BLIND RECRUITMENT 1차 코딩 테스트가 진행되었습니다. 테스트에는 총 7개의 문제가 출제되었으며, 개발 언어는 C++, Java, JavaScript, Kotlin, Python, Swift 총 6가지가 제공되었습니다.
문제는 작년과 마찬가지로 쉬운 난이도에서 어려운 난이도 순으로 배치했습니다. 6번 문제를 제외한 나머지 문제는 테스트 케이스를 모두 통과해야 정답으로 인정되었고, 부문 점수는 부여되지 않았습니다. 6번 문제에는 효율적인 풀이를 구현해야 통과되는 효율성 테스트를 추가했고, 효율성 테스트는 정확성 테스트와 별도의 점수가 부여되도록 배점을 설계했습니다.
그럼 각 문제들을 살펴보고 해설을 진행하겠습니다.
문제 1 – 신고 결과 받기
- 정답률 : 80.13%
- 문제 1 풀러가기
문제 설명
신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.
- 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다.
- 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다.
- 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다.
- k번 이상 신고된 유저는 즉시 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다.
- 게시판 이용이 정지된 유저도 불량 이용자를 신고할 수 있습니다.
다음은 전체 유저 목록이 [“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 함수를 완성해 주세요.
제한사항
- 2 ≤
id_list의 길이 ≤ 1,000 - 1 ≤
id_list의 원소 길이 ≤ 10 id_list의 원소는 이용자의 id를 나타내는 문자열이며 알파벳 소문자로만 이루어져 있습니다.- 1 ≤
report의 길이 ≤ 200,000 - 3 ≤
report의 원소 길이 ≤ 21 report의 원소는 “이용자 id 신고 id”형태의 문자열입니다.- 예를 들어 “muzi frodo”의 경우 “muzi”가 “frodo”를 신고했다는 의미입니다.
- id는 알파벳 소문자로만 이루어져 있습니다.
- 이용자 id와 신고 id는 공백(스페이스) 하나로 구분되어 있습니다.
- 자기 자신을 신고하는 경우는 없습니다.
- 1 ≤
k≤ 200,k는 자연수 - return 하는 배열은
id_list에 담긴 id 순서대로 각 유저가 받은 결과 메일 수를 담으면 됩니다.
입출력 예
| id_list | report | k | result |
|---|---|---|---|
["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 진수에서 소수의 개수 구하기
- 정답률 : 55.82%
- 문제 2 풀러가기
문제 설명
양의 정수 n이 주어집니다. 이 숫자를 k 진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.
0P0처럼 소수 양쪽에 0이 있는 경우P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우P처럼 소수 양쪽에 아무것도 없는 경우- 단,
P는 각 자릿수에 0을 포함하지 않는 소수입니다. - 예를 들어, 101은
P가 될 수 없습니다.
예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.
정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 1 ≤
n≤ 1,000,000 - 3 ≤
k≤ 10
입출력 예
| n | k | result |
|---|---|---|
| 437674 | 3 | 3 |
| 110011 | 10 | 2 |
입출력 예 설명
• 입출력 예 #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 – 주차 요금 계산
- 정답률 : 73.10%
- 문제 3 풀러가기
문제 설명
주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 아래는 하나의 예시를 나타냅니다.
- 요금표
| 기본 시간(분) | 기본 요금(원) | 단위 시간(분) | 단위 요금(원) |
|---|---|---|---|
| 180 | 5000 | 10 | 600 |
- 입/출차 기록
| 시각(시:분) | 차량 번호 | 내역 |
|---|---|---|
| 05:34 | 5961 | 입차 |
| 06:00 | 0000 | 입차 |
| 06:34 | 0000 | 출차 |
| 07:59 | 5961 | 출차 |
| 07:59 | 0148 | 입차 |
| 18:59 | 0000 | 입차 |
| 19:09 | 0148 | 출차 |
| 22:59 | 5961 | 입차 |
| 23:00 | 5961 | 출차 |
- 자동차별 주차 요금
| 차량 번호 | 누적 주차 시간(분) | 주차 요금(원) |
|---|---|---|
| 0000 | 34 + 300 = 334 | 5000 + ⌈(334 – 180) / 10⌉ x 600 = 14600 |
| 0148 | 670 | 5000 +⌈(670 – 180) / 10⌉x 600 = 34400 |
| 5961 | 145 + 1 = 146 | 5000 |
- 어떤 차량이 입차된 후에 출차된 내역이 없다면, 23:59에 출차된 것으로 간주합니다.
0000번 차량은 18:59에 입차된 이후, 출차된 내역이 없습니다. 따라서, 23:59에 출차된 것으로 간주합니다.
- 00:00부터 23:59까지의 입/출차 내역을 바탕으로 차량별 누적 주차 시간을 계산하여 요금을 일괄로 정산합니다.
- 누적 주차 시간이
기본 시간이하라면,기본요금을 청구합니다. - 누적 주차 시간이
기본 시간을 초과하면,기본요금에 더해서, 초과한 시간에 대해서단위 시간마다단위 요금을 청구합니다. - 초과한 시간이
단위 시간으로 나누어떨어지지 않으면,올림합니다. ⌈a⌉: a보다 작지 않은 최소의 정수를 의미합니다. 즉,올림을 의미합니다.
주차 요금을 나타내는 정수 배열 fees, 자동차의 입/출차 내역을 나타내는 문자열 배열 records가 매개변수로 주어집니다. 차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 return 하도록 solution 함수를 완성해 주세요.
제한사항
fees의 길이 = 4- fees[0] =
기본 시간(분)- 1 ≤ fees[0] ≤ 1,439
- fees[1] =
기본 요금(원)- 0 ≤ fees[1] ≤ 100,000
- fees[2] =
단위 시간(분)- 1 ≤ fees[2] ≤ 1,439
- fees[3] =
단위 요금(원)- 1 ≤ fees[3] ≤ 10,000
- 1 ≤
records의 길이 ≤ 1,000 - records의 각 원소는
"시각 차량번호 내역"형식의 문자열입니다.시각,차량번호,내역은 하나의 공백으로 구분되어 있습니다.시각은 차량이 입차되거나 출차된 시각을 나타내며,HH:MM형식의 길이 5인 문자열입니다.HH:MM은 00:00부터 23:59까지 주어집니다.- 잘못된 시각(“25:22”, “09:65” 등)은 입력으로 주어지지 않습니다.
차량번호는 자동차를 구분하기 위한,0~9로 구성된 길이 4인 문자열입니다.내역은 길이 2 또는 3인 문자열로,IN또는OUT입니다.IN은 입차를,OUT은 출차를 의미합니다.- records의 원소들은 시각을 기준으로 오름차순으로 정렬되어 주어집니다.
- records는 하루 동안의 입/출차된 기록만 담고 있으며, 입차된 차량이 다음날 출차되는 경우는 입력으로 주어지지 않습니다.
- 같은 시각에, 같은 차량번호의 내역이 2번 이상 입력으로 주어지지 않습니다.
- 마지막 시각(23:59)에 입차되는 경우는 입력으로 주어지지 않습니다.
- 아래의 예를 포함하여, 잘못된 입력은 주어지지 않습니다.
- 주차장에 없는 차량이 출차되는 경우
- 주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우
입출력 예
| fees | records | result |
|---|---|---|
| [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
- 요금표
| 기본 시간(분) | 기본 요금(원) | 단위 시간(분) | 단위 요금(원) |
|---|---|---|---|
| 120 | 0 | 60 | 591 |
- 입/출차 기록
| 시각(시:분) | 차량 번호 | 내역 |
|---|---|---|
| 16:00 | 3961 | 입차 |
| 16:00 | 0202 | 입차 |
| 18:00 | 3961 | 출차 |
| 18:00 | 0202 | 출차 |
| 23:58 | 3961 | 입차 |
- 자동차별 주차 요금
| 차량 번호 | 누적 주차 시간(분) | 주차 요금(원) |
|---|---|---|
| 0202 | 120 | 0 |
| 3961 | 120 + 1 = 121 | 0 +⌈(121 – 120) / 60⌉x 591 = 591 |
3961번 차량은 2번째 입차된 후에는 출차된 내역이 없으므로, 23:59에 출차되었다고 간주합니다.
• 입출력 예 #3
- 요금표
| 기본 시간(분) | 기본 요금(원) | 단위 시간(분) | 단위 요금(원) |
|---|---|---|---|
| 1 | 461 | 1 | 10 |
- 입/출차 기록
| 시각(시:분) | 차량 번호 | 내역 |
|---|---|---|
| 00:00 | 1234 | 입차 |
- 자동차별 주차 요금
| 차량 번호 | 누적 주차 시간(분) | 주차 요금(원) |
|---|---|---|
| 1234 | 1439 | 461 +⌈(1439 – 1) / 1⌉x 10 = 14841 |
1234번 차량은 출차 내역이 없으므로, 23:59에 출차되었다고 간주합니다.
문제 풀이
이 문제는 문자열 처리 능력과, 주어진 주차 요금표를 코드를 통해 정확히 구현할 수 있는지를 확인하는 문제였습니다.
특히, 이 문제는 입/출차 시각과 누적 주차 시간을 모두 ‘분’단위로 환산하여 저장하면 조금 더 쉽게 해결할 수 있습니다.
차량번호의 범위가 0000~9999이므로, 차량의 수는 최대 1만 대입니다. 이를 이용하여 두 배열 in_time, total_time을 다음과 같이 정의합니다.
- in_time[i] = i번 차량이 주차장에 입차 된 시각
- 입차 된 적이 없거나, 출차되었다면
-1을 저장
- 입차 된 적이 없거나, 출차되었다면
- total_time[i] = i번 차량의 누적 주차 시간
그 후 records에 담긴 원소를 순차적으로 처리해 줍니다.
- “IN”을 포함하고 있다면, 시각을 저장합니다.
- in_time[차량번호] = 시각
- “OUT”을 포함하고 있다면, 누적 주차 시간을 갱신합니다.
- total_time[차량번호] += ( 시각 – in_time[차량번호] )
- in_time[차량번호] = -1
records를 모두 처리한 후에도 출차되지 않은 차량이 있다면, 즉, in_time[i] != -1인 모든 i번 차량에 대해서는 23시 59분(1439분)에 출차되었다고 간주하고, total_time[i]를 갱신해 줍니다.
- total_time[i] += ( 1439 – in_time[i] )
위와 같은 방법으로 누적 주차 시간을 계산한 후, total_time[i] > 0 를 만족하는 모든 i번 차량에 대해서, 오름차순으로 주차 요금을 계산해서 배열에 담으면 문제를 해결할 수 있습니다.
문제 4 – 양궁 대회
- 정답률 : 21.16%
- 문제 4 풀러가기
문제 설명
카카오배 양궁대회가 열렸습니다.라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원회는 한 선수의 연속 우승보다는 다양한 선수들이 양궁대회에서 우승하기를 원합니다. 따라서, 양궁대회 운영위원회는 결승전 규칙을 전 대회 우승자인 라이언에게 불리하게 다음과 같이 정했습니다.
1. 어피치가 화살 n발을 다 쏜 후에 라이언이 화살 n발을 쏩니다.
2. 점수를 계산합니다.
- 과녁판은 아래 사진처럼 생겼으며 가장 작은 원의 과녁 점수는 10점이고 가장 큰 원의 바깥쪽은 과녁 점수가 0점입니다.
- 만약, k(k는 1~10사이의 자연수)점을 어피치가 a발을 맞혔고 라이언이 b발을 맞혔을 경우 더 많은 화살을 k점에 맞힌 선수가 k 점을 가져갑니다. 단, a = b일 경우는 어피치가 k점을 가져갑니다. k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져가는 게 아니고 k점만 가져가는 것을 유의하세요. 또한 a = b = 0 인 경우, 즉, 라이언과 어피치 모두 k점에 단 하나의 화살도 맞히지 못한 경우는 어느 누구도 k점을 가져가지 않습니다.
* 예를 들어, 어피치가 10점을 2발 맞혔고 라이언도 10점을 2발 맞혔을 경우 어피치가 10점을 가져갑니다.
* 다른 예로, 어피치가 10점을 0발 맞혔고 라이언이 10점을 2발 맞혔을 경우 라이언이 10점을 가져갑니다.- 모든 과녁 점수에 대하여 각 선수의 최종 점수를 계산합니다.
3. 최종 점수가 더 높은 선수를 우승자로 결정합니다. 단, 최종 점수가 같을 경우 어피치를 우승자로 결정합니다.
현재 상황은 어피치가 화살 n발을 다 쏜 후이고 라이언이 화살을 쏠 차례입니다.
라이언은 어피치를 가장 큰 점수 차이로 이기기 위해서 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 구하려고 합니다.
화살의 개수를 담은 자연수 n, 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열 info가 매개변수로 주어집니다. 이때, 라이언이 가장 큰 점수 차이로 우승하기 위해 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 만약, 라이언이 우승할 수 없는 경우(무조건 지거나 비기는 경우)는 [-1]을 return 해주세요.
제한사항
- 1 ≤
n≤ 10 info의 길이 = 11- 0 ≤
info의 원소 ≤n info의 원소 총합 =ninfo의 i번째 원소는 과녁의10 - i점을 맞힌 화살 개수입니다. ( i는 0~10 사이의 정수입니다.)- 라이언이 우승할 방법이 있는 경우, return 할 정수 배열의 길이는 11입니다.
- 0 ≤ return할 정수 배열의 원소 ≤
n - return할 정수 배열의 원소 총합 =
n(꼭 n발을 다 쏴야 합니다.) - return할 정수 배열의 i번째 원소는 과녁의
10 - i점을 맞힌 화살 개수입니다. ( i는 0~10 사이의 정수입니다.) - 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
- 가장 낮은 점수를 맞힌 개수가 같을 경우 계속해서 그다음으로 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
- 예를 들어,
[2,3,1,0,0,0,0,1,3,0,0]과[2,1,0,2,0,0,0,2,3,0,0]를 비교하면[2,1,0,2,0,0,0,2,3,0,0]를 return 해야 합니다. - 다른 예로,
[0,0,2,3,4,1,0,0,0,0,0]과[9,0,0,0,0,0,0,0,1,0,0]를 비교하면[9,0,0,0,0,0,0,0,1,0,0]를 return 해야 합니다.
- 라이언이 우승할 방법이 없는 경우, return 할 정수 배열의 길이는 1입니다.
- 라이언이 어떻게 화살을 쏘든 라이언의 점수가 어피치의 점수보다 낮거나 같으면
[-1]을 return 해야 합니다.
입출력 예
| n | info | result |
|---|---|---|
| 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
어피치와 라이언이 아래와 같이 화살을 맞힐 경우,
| 과녁 점수 | 어피치가 맞힌 화살 개수 | 라이언이 맞힌 화살 개수 | 결과 |
|---|---|---|---|
| 10 | 2 | 3 | 라이언이 10점 획득 |
| 9 | 1 | 2 | 라이언이 9점 획득 |
| 8 | 1 | 0 | 어피치가 8점 획득 |
| 7 | 1 | 0 | 어피치가 7점 획득 |
| 6 | 0 | 0 | |
| 5 | 0 | 0 | |
| 4 | 0 | 0 | |
| 3 | 0 | 0 | |
| 2 | 0 | 0 | |
| 1 | 0 | 0 | |
| 0 | 0 | 0 |
어피치의 최종 점수는 15점, 라이언의 최종 점수는 19점입니다. 4점 차이로 라이언이 우승합니다.
하지만, 라이언이 아래와 같이 화살을 맞힐 경우 더 큰 점수 차로 우승할 수 있습니다.
| 과녁 점수 | 어피치가 맞힌 화살 개수 | 라이언이 맞힌 화살 개수 | 결과 |
|---|---|---|---|
| 10 | 2 | 0 | 어피치가 10점 획득 |
| 9 | 1 | 2 | 라이언이 9점 획득 |
| 8 | 1 | 2 | 라이언이 8점 획득 |
| 7 | 1 | 0 | 어피치가 7점 획득 |
| 6 | 0 | 1 | 라이언이 6점 획득 |
| 5 | 0 | 0 | |
| 4 | 0 | 0 | |
| 3 | 0 | 0 | |
| 2 | 0 | 0 | |
| 1 | 0 | 0 | |
| 0 | 0 | 0 |
어피치의 최종 점수는 17점, 라이언의 최종 점수는 23점입니다. 6점 차이로 라이언이 우승합니다.
따라서 [0,2,2,0,1,0,0,0,0,0,0]을 return 해야 합니다.
• 입출력 예 #2
라이언이 10점을 맞혀도 어피치가 10점을 가져가게 됩니다.
따라서, 라이언은 우승할 수 없기 때문에 [-1]을 return 해야 합니다.
• 입출력 예 #3
어피치와 라이언이 아래와 같이 화살을 맞힐 경우,
| 과녁 점수 | 어피치가 맞힌 화살 개수 | 라이언이 맞힌 화살 개수 | 결과 |
|---|---|---|---|
| 10 | 0 | 1 | 라이언이 10점 획득 |
| 9 | 0 | 1 | 라이언이 9점 획득 |
| 8 | 1 | 2 | 라이언이 8점 획득 |
| 7 | 2 | 3 | 라이언이 7점 획득 |
| 6 | 0 | 0 | |
| 5 | 1 | 2 | 라이언이 5점 획득 |
| 4 | 1 | 0 | 어피치가 4점 획득 |
| 3 | 1 | 0 | 어피치가 3점 획득 |
| 2 | 1 | 0 | 어피치가 2점 획득 |
| 1 | 1 | 0 | 어피치가 1점 획득 |
| 0 | 1 | 0 | 어피치가 0점 획득 |
어피치의 최종 점수는 10점, 라이언의 최종 점수는 39점입니다. 29점 차이로 라이언이 우승합니다.
하지만 라이언이 아래와 같이 화살을 맞힐 경우,
| 과녁 점수 | 어피치가 맞힌 화살 개수 | 라이언이 맞힌 화살 개수 | 결과 |
|---|---|---|---|
| 10 | 0 | 1 | 라이언이 10점 획득 |
| 9 | 0 | 1 | 라이언이 9점 획득 |
| 8 | 1 | 2 | 라이언이 8점 획득 |
| 7 | 2 | 0 | 어피치가 7점 획득 |
| 6 | 0 | 1 | 라이언이 6점 획득 |
| 5 | 1 | 2 | 라이언이 5점 획득 |
| 4 | 1 | 2 | 라이언이 4점 획득 |
| 3 | 1 | 0 | 어피치가 3점 획득 |
| 2 | 1 | 0 | 어피치가 2점 획득 |
| 1 | 1 | 0 | 어피치가 1점 획득 |
| 0 | 1 | 0 | 어피치가 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 – 양과 늑대
- 정답률 : 7.76%
- 문제 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 함수를 완성해 주세요.
제한사항
- 2 ≤
info의 길이 ≤ 17 info의 원소는 0 또는 1 입니다.- info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.
- 0은 양, 1은 늑대를 의미합니다.
- info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
edges의 세로(행) 길이 =info의 길이 – 1edges의 가로(열) 길이 = 2edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로, 서로 연결된 두 노드를 나타냅니다.- 동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
- 항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
- 0번 노드는 항상 루트 노드입니다.
입출력 예
| info | edges | result |
|---|---|---|
| [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를 수행하는 함수의 파라미터는 다음과 같이 구성할 수 있습니다.
- 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 – 파괴되지 않은 건물
- 정답률 : 정확성 51.11%, 효율성 1.86%
- 문제 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 함수를 완성해 주세요.
제한사항
- 1 ≤
board의 행의 길이 (=N) ≤ 1,000 - 1 ≤
board의 열의 길이 (=M) ≤ 1,000 - 1 ≤
board의 원소 (각 건물의 내구도) ≤ 1,000 - 1 ≤
skill의 행의 길이 ≤ 250,000 skill의 열의 길이 = 6skill의 각 행은[type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.- type은 1 혹은 2입니다.
- type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
- type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
- (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
- 0 ≤ r1 ≤ r2 <
board의 행의 길이 - 0 ≤ c1 ≤ c2 <
board의 열의 길이 - 1 ≤ degree ≤ 500
- type이 1이면 degree 만큼 건물의 내구도를 낮춥니다.
- type이 2이면 degree 만큼 건물의 내구도를 높입니다.
- 0 ≤ r1 ≤ r2 <
- 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1 이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1 이상이면 파괴되지 않은 건물입니다.
정확성 테스트 케이스 제한사항
- 1 ≤
board의 행의 길이 (=N) ≤ 100 - 1 ≤
board의 열의 길이 (=M) ≤ 100 - 1 ≤
board의 원소 (각 건물의 내구도) ≤ 100 - 1 ≤
skill의 행의 길이 ≤ 100 - 1 ≤ degree ≤ 100
효율성 테스트 케이스 제한사항
- 주어진 조건 외 추가 제한사항 없습니다.
입출력 예
| board | skill | result |
|---|---|---|
| [ [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 -42. (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 -43. (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 – 사라지는 발판
- 정답률 : 0.78%
- 문제 7 풀러가기
문제 설명
플레이어 A와 플레이어 B가 서로 게임을 합니다. 당신은 이 게임이 끝날 때까지 양 플레이어가 캐릭터를 몇 번 움직이게 될지 예측하려고 합니다.
각 플레이어는 자신의 캐릭터 하나를 보드 위에 올려놓고 게임을 시작합니다. 게임 보드는 1×1 크기 정사각 격자로 이루어져 있으며, 보드 안에는 발판이 있는 부분과 없는 부분이 있습니다. 발판이 있는 곳에만 캐릭터가 서있을 수 있으며, 처음 캐릭터를 올려놓는 곳은 항상 발판이 있는 곳입니다. 캐릭터는 발판이 있는 곳으로만 이동할 수 있으며, 보드 밖으로 이동할 수 없습니다. 밟고 있던 발판은 그 위에 있던 캐릭터가 다른 곳으로 이동하여 다른 발판을 밟음과 동시에 사라집니다. 양 플레이어는 번갈아가며 자기 차례에 자신의 캐릭터를 상하좌우로 인접한 4개의 칸 중에서 발판이 있는 칸으로 옮겨야 합니다.
다음과 같은 2가지 상황에서 패자와 승자가 정해지며, 게임이 종료됩니다.
- 움직일 차례인데 캐릭터의 상하좌우 주변 4칸이 모두 발판이 없거나 보드 밖이라서 이동할 수 없는 경우, 해당 차례 플레이어는 패배합니다.
- 두 캐릭터가 같은 발판 위에 있을 때, 상대 플레이어의 캐릭터가 다른 발판으로 이동하여 자신의 캐릭터가 서있던 발판이 사라지게 되면 패배합니다.
게임은 항상 플레이어 A가 먼저 시작합니다. 양 플레이어는 최적의 플레이를 합니다. 즉, 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이합니다. ‘이길 수 있는 플레이어’는 실수만 하지 않는다면 항상 이기는 플레이어를 의미하며, ‘질 수밖에 없는 플레이어’는 최선을 다해도 상대가 실수하지 않으면 항상 질 수밖에 없는 플레이어를 의미합니다. 최대한 오래 버틴다는 것은 양 플레이어가 캐릭터를 움직이는 횟수를 최대화한다는 것을 의미합니다.
아래 그림은 초기 보드의 상태와 각 플레이어의 위치를 나타내는 예시입니다.
위와 같은 경우, 플레이어 A는 실수만 하지 않는다면 항상 이길 수 있습니다. 따라서 플레이어 A는 이길 수 있는 플레이어이며, B는 질 수밖에 없는 플레이어입니다. 다음은 A와 B가 최적의 플레이를 하는 과정을 나타냅니다.
- 플레이어 A가 초기 위치 (1, 0)에서 (1, 1)로 이동합니다. 플레이어 A가 (0, 0)이나 (2, 0)으로 이동할 경우 승리를 보장할 수 없습니다. 따라서 무조건 이길 방법이 있는 (1, 1)로 이동합니다.
- 플레이어 B는 (1, 1)로 이동할 경우, 바로 다음 차례에 A가 위 또는 아래 방향으로 이동하면 발판이 없어져 패배하게 됩니다. 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이하기 때문에 (1, 1)로 이동하지 않습니다. (1, 2)에서 위쪽 칸인 (0, 2)로 이동합니다.
- A가 (1, 1)에서 (0, 1)로 이동합니다.
- B에게는 남은 선택지가 (0, 1)밖에 없습니다. 따라서 (0, 2)에서 (0, 1)로 이동합니다.
- A가 (0, 1)에서 (0, 0)으로 이동합니다. 이동을 완료함과 동시에 B가 서있던 (0, 1)의 발판이 사라집니다. B가 패배합니다.
- 만약 과정 2에서 B가 아래쪽 칸인 (2, 2)로 이동하더라도 A가 (2, 1)로 이동하면 됩니다. 이후 B가 (2, 1)로 이동, 다음 차례에 A가 (2, 0)으로 이동하면 B가 패배합니다.
위 예시에서 양 플레이어가 최적의 플레이를 했을 경우, 캐릭터의 이동 횟수 합은 5입니다. 최적의 플레이를 하는 방법은 여러 가지일 수 있으나, 이동한 횟수는 모두 5로 같습니다.
게임 보드의 초기 상태를 나타내는 2차원 정수 배열 board와 플레이어 A의 캐릭터 초기 위치를 나타내는 정수 배열 aloc, 플레이어 B의 캐릭터 초기 위치를 나타내는 정수 배열 bloc이 매개변수로 주어집니다. 양 플레이어가 최적의 플레이를 했을 때, 두 캐릭터가 움직인 횟수의 합을 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 1 ≤
board의 세로 길이 ≤ 5 - 1 ≤
board의 가로 길이 ≤ 5 board의 원소는 0 또는 1입니다.- 0은 발판이 없음을, 1은 발판이 있음을 나타냅니다.
aloc과bloc은 각각 플레이어 A의 캐릭터와 플레이어 B의 캐릭터 초기 위치를 나타내는 좌표값이며 [r, c] 형태입니다.- r은 몇 번째 행인지를 나타냅니다.
- 0 ≤ r <
board의 세로 길이 - c는 몇 번째 열인지를 나타냅니다.
- 0 ≤ c <
board의 가로 길이 - 초기 보드의
aloc과bloc위치는 항상 발판이 있는 곳입니다. aloc과bloc이 같을 수 있습니다.- 상대 플레이어의 캐릭터가 있는 칸으로 이동할 수 있습니다.
입출력 예
| board | aloc | bloc | result |
|---|---|---|---|
| [ [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가 이기는 방법 중 하나입니다.
- A가 (1, 0)에서 (0, 0)으로 이동
- B가 (1, 2)에서 (2, 2)로 이동
- A가 (0, 0)에서 (0, 1)로 이동
- B가 (2, 2)에서 (2, 1)로 이동
- A가 (0, 1)에서 (0, 2)로 이동
- B가 (2, 1)에서 (2, 0)으로 이동
- A는 어디로도 이동할 수가 없어 패배
위와 같이 플레이할 경우 이동 횟수 6번 만에 게임을 B의 승리로 끝낼 수 있습니다.
B가 다음과 같이 플레이할 경우 게임을 더 빨리 끝낼 수 있습니다. 이길 수 있는 플레이어는 최대한 빨리 게임을 끝내려 하기 때문에 위 방법 대신 아래 방법을 선택합니다.
- A가 (1, 0)에서 (0, 0)으로 이동
- B가 (1, 2)에서 (0, 2)로 이동
- A가 (0, 0)에서 (0, 1)로 이동
- B가 (0, 2)에서 (0, 1)로 이동
- 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시간이라는 긴 시간동안 테스트 응시하시느라 정말 고생 많으셨습니다!
✔️ 카카오 온라인 코딩 테스트 문제해설 바로가기
