지난 2020년 9월 12일 토요일 오후 2시부터 7시까지 5시간 동안 2021 카카오 신입 개발자 공채 1차 코딩 테스트가 진행되었습니다. 테스트에는 총 7개의 문제가 출제되었으며, 개발 언어는 C++, Java, JavaScript, Kotlin, Python, Swift 총 6가지가 제공되었습니다.
문제는 난이도가 낮은 것부터 높은 순으로 배치하였으며 모든 문제는 테스트 케이스를 모두 통과해야 풀이한 것으로 인정되고 부문 점수는 부여되지 않았습니다. 또한 작년과 마찬가지로 일부 문제는 정확성 테스트 외에 같은 문제라도 입력 값의 크기에 따라 효율적인 풀이를 구현해야 통과되는 효율성 테스트를 추가하였고, 효율성 테스트는 정확성 테스트와 별도의 점수가 부여되도록 배점을 설계했습니다.
그럼, 지금부터 문제 내용과 간략한 풀이 방법을 살펴보도록 하겠습니다.
문제 1 – 아이디 추천
- 정답률 : 57.50%
- 문제 1 풀러 가기
카카오에 입사한 신입 개발자 네오는 “카카오계정개발팀”에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. “네오”에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해 주는 프로그램을 개발하는 것입니다.
다음은 카카오 아이디의 규칙입니다.
- 아이디의 길이는 3자 이상 15자 이하여야 합니다.
- 아이디는 알파벳 소문자, 숫자, 빼기(
-), 밑줄(_), 마침표(.) 문자만 사용할 수 있습니다. - 단, 마침표(
.)는 처음과 끝에 사용할 수 없으며 또한 연속으로 사용할 수 없습니다.
“네오”는 다음과 같이 7단계의 순차적인 처리 과정을 통해 신규 유저가 입력한 아이디가 카카오 아이디 규칙에 맞는지 검사하고 규칙에 맞지 않은 경우 규칙에 맞는 새로운 아이디를 추천해 주려고 합니다.
신규 유저가 입력한 아이디가 new_id라고 한다면,
1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다.
2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.
3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.
4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.
5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다.
6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다.
만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.
7단계 new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.
예를 들어, new_id 값이 “…!@BaT#*..y.abcdefghijklm” 라면, 위 7단계를 거치고 나면 new_id는 아래와 같이 변경됩니다.
1단계 대문자 ‘B’와 ‘T’가 소문자 ‘b’와 ‘t’로 바뀌었습니다."...!@BaT#*..y.abcdefghijklm" → "...!@bat#*..y.abcdefghijklm"
2단계 ‘!’, ‘@’, ‘#’, ‘*’ 문자가 제거되었습니다."...!@bat#*..y.abcdefghijklm" → "...bat..y.abcdefghijklm"
3단계 ‘…’와 ‘..’ 가 ‘.’로 바뀌었습니다."...bat..y.abcdefghijklm" → ".bat.y.abcdefghijklm"
4단계 아이디의 처음에 위치한 ‘.’가 제거되었습니다.".bat.y.abcdefghijklm" → "bat.y.abcdefghijklm"
5단계 아이디가 빈 문자열이 아니므로 변화가 없습니다."bat.y.abcdefghijklm" → "bat.y.abcdefghijklm"
6단계 아이디의 길이가 16자 이상이므로, 처음 15자를 제외한 나머지 문자들이 제거되었습니다."bat.y.abcdefghijklm" → "bat.y.abcdefghi"
7단계 아이디의 길이가 2자 이하가 아니므로 변화가 없습니다."bat.y.abcdefghi" → "bat.y.abcdefghi"
따라서 신규 유저가 입력한 new_id가 “…!@BaT#*..y.abcdefghijklm”일 때, 네오의 프로그램이 추천하는 새로운 아이디는 “bat.y.abcdefghi” 입니다.
문제
신규 유저가 입력한 아이디를 나타내는 new_id가 매개변수로 주어질 때, “네오”가 설계한 7단계의 처리 과정을 거친 후의 추천 아이디를 return 하도록 solution 함수를 완성해 주세요.
제한사항
new_id는 길이 1 이상 1,000 이하인 문자열입니다.
new_id는 알파벳 대문자, 알파벳 소문자, 숫자, 특수문자로 구성되어 있습니다.
new_id에 나타날 수 있는 특수문자는 -_.~!@#$%^&*()=+[{]}:?,<>/ 로 한정됩니다.
[입출력 예]
| no | new_id | result |
|---|---|---|
| 예1 | "...!@BaT#*..y.abcdefghijklm" |
"bat.y.abcdefghi" |
| 예2 | "z-+.^." |
"z--" |
| 예3 | "=.=" |
"aaa" |
| 예4 | "123_.def" |
"123_.def" |
| 예5 | "abcdefghijklmn.p" |
"abcdefghijklmn" |
입출력 예에 대한 설명
– 입출력 예 #1
문제의 예시와 같습니다.
– 입출력 예 #2
7단계를 거치는 동안 new_id가 변화하는 과정은 아래와 같습니다.
1단계 변화 없습니다.
2단계 "z-+.^." → "z-.."
3단계 "z-.." → "z-."
4단계 "z-." → "z-"
5단계 변화 없습니다.
6단계 변화 없습니다.
7단계 "z-" → "z--"
– 입출력 예 #3
7단계를 거치는 동안 new_id가 변화하는 과정은 아래와 같습니다.
1단계 변화 없습니다.
2단계 "=.=" → "."
3단계 변화 없습니다.
4단계 "." → "" (new_id가 빈 문자열이 되었습니다.)
5단계 "" → "a"
6단계 변화 없습니다.
7단계 "a" → "aaa"
– 입출력 예 #4
1단계에서 7단계까지 거치는 동안 new_id(“123_.def”)는 변하지 않습니다. 즉, new_id가 처음부터 카카오의 아이디 규칙에 맞습니다.
– 입출력 예 #5
1단계 변화 없습니다.
2단계 변화 없습니다.
3단계 변화 없습니다.
4단계 변화 없습니다.
5단계 변화 없습니다.
6단계 "abcdefghijklmn.p" → "abcdefghijklmn." → "abcdefghijklmn"
7단계 변화 없습니다.
문제 풀이
1번 문제는 가장 낮은 난이도에 해당하는 일명 몸풀기 문제입니다. 1단계~7단계에서 지시하는 그대로 구현하면 되기 때문에, 특별한 알고리즘보다는 정확한 구현이 필요한 문제입니다.
본 문제는 new_id의 길이가 1,000으로 매우 작습니다. 따라서, new_id의 길이를 n이라고 할 때, O(n^2) 성능의 알고리즘으로 구현해도 제한 시간 내 답을 구할 수 있습니다.
보다 효율적으로 구현한다면 O(n) 성능의 알고리즘으로 구현을 할 수도 있습니다. new_id에서 필요 없는 문자들을 직접 제거하지 말고, new_id를 앞에서부터 검사하면서 유효한 문자(제거되지 않아야 할 문자)만 추려서 새로운 문자열 변수(new_id_1)에 붙여나가는 방법을 사용하면 됩니다.
문제 2 – 메뉴 리뉴얼
- 정답률 : 25.40%
- 문제 2 풀러 가기
레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.
기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품 메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을지 고민하던 “스카피”는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품 메뉴들을 코스요리 메뉴로 구성하기로 했습니다.
단, 코스요리 메뉴는 최소 2가지 이상의 단품 메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품 메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.
예를 들어, 손님 6명이 주문한 단품 메뉴들의 조합이 다음과 같다면,
(각 손님은 단품 메뉴를 2개 이상 주문해야 하며, 각 단품 메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)
| 손님 번호 | 주문한 단품 메뉴 조합 |
|---|---|
| 1번 손님 | A, B, C, F, G |
| 2번 손님 | A, C |
| 3번 손님 | C, D, E |
| 4번 손님 | A, C, D, E |
| 5번 손님 | B, C, F, G |
| 6번 손님 | A, C, D, E, H |
가장 많이 함께 주문된 단품 메뉴 조합에 따라 “스카피”가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.
| 코스 종류 | 메뉴 구성 | 설명 |
|---|---|---|
| 요리 2개 코스 | A, C | 1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다. |
| 요리 3개 코스 | C, D, E | 3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다. |
| 요리 4개 코스 | B, C, F, G | 1번, 5번 손님으로부터 총 2번 주문됐습니다. |
| 요리 4개 코스 | A, C, D, E | 4번, 6번 손님으로부터 총 2번 주문됐습니다. |
문제
각 손님들이 주문한 단품 메뉴들이 문자열 형식으로 담긴 배열 orders, “스카피”가 추가하고 싶어 하는 코스요리를 구성하는 단품 메뉴들의 개수가 담긴 배열 course가 매개변수로 주어질 때, “스카피”가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
제한사항
- orders 배열의 크기는 2 이상 20 이하입니다.
- orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
- 각 문자열은 알파벳 대문자로만 이루어져 있습니다.
- 각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
- course 배열의 크기는 1 이상 10 이하입니다.
- course 배열의 각 원소는 2 이상 10 이하인 자연수가
오름차순으로 정렬되어 있습니다. - course 배열에는 같은 값이 중복해서 들어있지 않습니다.
- 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로
오름차순정렬해서 return 해주세요. - 배열의 각 원소에 저장된 문자열 또한 알파벳
오름차순으로 정렬되어야 합니다. - 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
- orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.
[입출력 예]
| orders | course | result |
|---|---|---|
["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"] |
[2,3,4] | ["AC", "ACDE", "BCFG", "CDE"] |
["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"] |
[2,3,5] | ["ACD", "AD", "ADE", "CD", "XYZ"] |
["XYZ", "XWY", "WXA"] |
[2,3,4] | ["WX", "XY"] |
입출력 예에 대한 설명
– 입출력 예 #1
문제의 예시와 같습니다.
– 입출력 예 #2
AD가 세 번, CD가 세 번, ACD가 두 번, ADE가 두 번, XYZ 가 두 번 주문됐습니다.
요리 5개를 주문한 손님이 1명 있지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 5개로 구성된 코스요리는 새로 추가하지 않습니다.
– 입출력 예 #3
WX가 두 번, XY가 두 번 주문됐습니다.
3명의 손님 모두 단품 메뉴를 3개씩 주문했지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 3개로 구성된 코스요리는 새로 추가하지 않습니다.
또, 단품 메뉴를 4개 이상 주문한 손님은 없으므로, 요리 4개로 구성된 코스요리 또한 새로 추가하지 않습니다.
문제 풀이
먼저 문제에 대한 해답을 얻기 전에, 각 메뉴별로 가능한 모든 조합을 만들어 봅니다. 예를 들어 “ABCD”의 경우 다음과 같이 11가지 조합이 가능합니다.
- “AB”, “AC”, “AD”, “BC”, “BD”, “CD”, “ABC”, “ABD”, “ACD”, “BCD”, “ABCD”
위와 같이 각 메뉴에서 가능한 모든 조합을 만들었다면, 각 조합의 개수를 세면 됩니다. 이때 “ABC”와 “CBA”를 같은 조합으로 세는 점을 주의해야 합니다. 쉽게 해결하는 방법으로는 처음에 각 문자열을 알파벳 순서로 정렬하거나, 만들어진 조합 문자열을 정렬하는 방법이 있겠습니다.
각 조합별로 개수를 셌다면, 최종적으로 문자열의 길이가 같은 조합 중 가장 많이 나타난 조합은 무엇인지 찾으면 됩니다.
문제 3 – 순위 검색
- 정답률 : 정확성 44.07%, 효율성 4.49%
- 문제 3 풀러 가기
카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩 테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.
- 코딩 테스트 참여 개발 언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
- 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
- 지원 경력 구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
- 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.
인재영입팀에 근무하고 있는 니니즈는 코딩 테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.코딩 테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩 테스트 점수를 50점 이상 받은 지원자는 몇 명인가?
물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.
- 코딩 테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩 테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
- 코딩 테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩 테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
- backend 직군을 선택했고, senior 경력이면서 코딩 테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
- 소울푸드로 chicken을 선택한 사람 중 코딩 테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
- 코딩 테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?
즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.
* [조건]을 만족하는 사람 중 코딩 테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?
문제
지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩 테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의 조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의 조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
제한사항
- info 배열의 크기는 1 이상 50,000 이하입니다.
- info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩 테스트 점수를 합친 “개발 언어 직군 경력 소울푸드 점수” 형식입니다.
- 개발 언어는 cpp, java, python 중 하나입니다.
- 직군은 backend, frontend 중 하나입니다.
- 경력은 junior, senior 중 하나입니다.
- 소울푸드는 chicken, pizza 중 하나입니다.
- 점수는 코딩 테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
- 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
- query 배열의 크기는 1 이상 100,000 이하입니다.
- query의 각 문자열은 “[조건] X” 형식입니다.
- [조건]은 “개발 언어 and 직군 and 경력 and 소울푸드” 형식의 문자열입니다.
- 언어는 cpp, java, python, – 중 하나입니다.
- 직군은 backend, frontend, – 중 하나입니다.
- 경력은 junior, senior, – 중 하나입니다.
- 소울푸드는 chicken, pizza, – 중 하나입니다.
- ‘-‘ 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
- X는 코딩 테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
- 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
- 예를 들면, “cpp and – and senior and pizza 500″은 “cpp로 코딩 테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩 테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?”를 의미합니다.
[입출력 예]
| info | query | result |
|---|---|---|
["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"] |
["java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"] |
[1,1,1,1,2,4] |
입출력 예에 대한 설명
지원자 정보를 표로 나타내면 다음과 같습니다.
| 언어 | 직군 | 경력 | 소울 푸드 | 점수 |
|---|---|---|---|---|
| java | backend | junior | pizza | 150 |
| python | frontend | senior | chicken | 210 |
| python | frontend | senior | chicken | 150 |
| cpp | backend | senior | pizza | 260 |
| java | backend | junior | chicken | 80 |
| python | backend | senior | chicken | 50 |
"java and backend and junior and pizza 100": java로 코딩 테스트를 봤으며, backend 직군을 선택했고 junior 경력이면서 소울푸드로 pizza를 선택한 지원자 중 코딩 테스트 점수를 100점 이상 받은 지원자는 1명 입니다."python and frontend and senior and chicken 200": python으로 코딩 테스트를 봤으며, frontend 직군을 선택했고, senior 경력이면서 소울 푸드로 chicken을 선택한 지원자 중 코딩 테스트 점수를 200점 이상 받은 지원자는 1명 입니다."cpp and - and senior and pizza 250": cpp로 코딩 테스트를 봤으며, senior 경력이면서 소울푸드로 pizza를 선택한 지원자 중 코딩 테스트 점수를 250점 이상 받은 지원자는 1명 입니다."- and backend and senior and - 150": backend 직군을 선택했고, senior 경력인 지원자 중 코딩 테스트 점수를 150점 이상 받은 지원자는 1명 입니다."- and - and - and chicken 100": 소울푸드로 chicken을 선택한 지원자 중 코딩 테스트 점수를 100점 이상을 받은 지원자는 2명 입니다."- and - and - and - 150": 코딩 테스트 점수를 150점 이상 받은 지원자는 4명 입니다.
문제 풀이
본 문제는 정확성 테스트와 효율성 테스트 두 가지 방식으로 검증하는 문제입니다. 효율성 테스트의 경우 주어진 시간 내에 실행이 완료되어야 하므로, 최적화된 구현 방법을 고민할 필요가 있습니다.
우선, 매 문의 조건마다 INFO 배열에서 조건에 해당하는 지원자들을 찾으면서 X점 이상 받은 사람은 몇 명인지 구한다면 정확성 테스트를 통과할 수 있습니다.
그러나 효율성 테스트의 경우에는 위와 같은 방식으로 매번 지원자들을 찾는다면 통과할 수 없습니다. 문제 해결을 위해서, 지원자들을 그룹별로 적절하게 미리 분류해두면 매 문의 조건마다 지원자들을 INFO 배열에서 찾지 않아도 됩니다.
예를 들어, “java backend junior pizza 150” 지원자의 경우 다음과 같이 16가지 그룹에 속하게 됩니다.
| 언어 | 직군 | 경력 | 소울 푸드 | 점수 |
|---|---|---|---|---|
| java | backend | junior | pizza | 150 |
| – | backend | junior | pizza | 150 |
| java | – | junior | pizza | 150 |
| java | backend | – | pizza | 150 |
| java | backend | junior | – | 150 |
| – | – | junior | pizza | 150 |
| – | backend | – | pizza | 150 |
| … (생략) | ||||
| java | – | – | – | 150 |
| – | – | – | – | 150 |
검색 조건이 “java and backend and junior and pizza 100″이라 하면, 위 지원자는 검색 대상에 포함되며, 검색 조건이 “java and – and junior and – 100” 인 경우에도 검색 대상에 포함이 됩니다.
따라서 모든 지원자들을 위와 같은 방식으로 분류한 후 같은 그룹의 지원자끼리 묶어두고, 해당 그룹에서 점수를 기준으로 오름차순 정렬해 둡니다.
이제, 검색 조건이 주어질 경우 INFO 배열에서 지원자들을 찾지 않고, 미리 분류해둔 그룹에서 X점 이상 맞은 지원자 수를 세주기만 하면 됩니다.
이때, X점 이상 맞은 지원자를 찾기 위해 해당 그룹의 최저점, 혹은 최고점부터 순차적으로 검색한다면 여전히 오랜 시간이 걸리게 됩니다. 이때, 숫자가 오름차순으로 정렬된 배열에서 X라는 숫자를 찾는 효율적인 방법으로 binary search를 사용할 수 있습니다. 이때, 배열에 X가 없을 수도 있으므로, 배열에서 X보다 크거나 같은 숫자가 처음 나타나는 위치를 찾아야 하며, 이는 lower bound를 이용하면 됩니다.
문제 4 – 합승 택시 요금
- 정답률 : 정확성 9.60%, 효율성 7.45%
- 문제 4 풀러 가기
밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. “무지”는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. “무지”는 “어피치”와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을지 계산해 보고 “어피치”에게 합승을 제안해 보려고 합니다.
위 예시 그림은 택시가 이동 가능한 반경에 있는 6개 지점 사이의 이동 가능한 택시 노선과 예상요금을 보여주고 있습니다.
그림에서 A와 B 두 사람은 출발 지점인 4번 지점에서 출발해서 택시를 타고 귀가하려고 합니다. A의 집은 6번 지점에 있으며 B의 집은 2번 지점에 있고 두 사람이 모두 귀가하는 데 소요되는 예상 최저 택시요금이 얼마인 지 계산하려고 합니다.
- 그림의 원은 지점을 나타내며 원 안의 숫자는 지점 번호를 나타냅니다.
- 지점이 n개일 때, 지점 번호는 1부터 n까지 사용됩니다.
- 지점 간에 택시가 이동할 수 있는 경로를 간선이라 하며, 간선에 표시된 숫자는 두 지점 사이의 예상 택시요금을 나타냅니다.
- 간선은 편의 상 직선으로 표시되어 있습니다.
- 위 그림 예시에서, 4번 지점에서 1번 지점으로(4→1) 가거나, 1번 지점에서 4번 지점으로(1→4) 갈 때 예상 택시요금은
10원으로 동일하며 이동 방향에 따라 달라지지 않습니다. - 예상되는 최저 택시요금은 다음과 같이 계산됩니다.
- 4→1→5 :
A,B가 합승하여 택시를 이용합니다. 예상 택시요금은10 + 24 = 34원입니다. - 5→6 :
A가 혼자 택시를 이용합니다. 예상 택시요금은2원입니다. - 5→3→2 :
B가 혼자 택시를 이용합니다. 예상 택시요금은24 + 22 = 46원입니다. A,B모두 귀가 완료까지 예상되는 최저 택시요금은34 + 2 + 46 = 82원입니다.
문제
지점의 개수 n, 출발 지점을 나타내는 s, A의 도착지점을 나타내는 a, B의 도착지점을 나타내는 b, 지점 사이의 예상 택시요금을 나타내는 fares가 매개변수로 주어집니다. 이때, A, B 두 사람이 s에서 출발해서 각각의 도착 지점까지 택시를 타고 간다고 가정할 때, 최저 예상 택시요금을 계산해서 return 하도록 solution 함수를 완성해 주세요.
만약, 아예 합승을 하지 않고 각자 이동하는 경우의 예상 택시요금이 더 낮다면, 합승을 하지 않아도 됩니다.
제한사항
- 지점 개수 n은 3 이상 200 이하인 자연수입니다.
- 지점 s, a, b는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값입니다.
- 즉, 출발 지점,
A의 도착지점,B의 도착지점은 서로 겹치지 않습니다. - fares는 2차원 정수 배열입니다.
- fares 배열의 크기는 2 이상
n x (n-1) / 2이하입니다. - 예를 들어, n = 6이라면 fares 배열의 크기는 2 이상 15 이하입니다. (
6 x 5 / 2 = 15) - fares 배열의 각 행은 [c, d, f] 형태입니다.
- c 지점과 d 지점 사이의 예상 택시요금이
f원이라는 뜻입니다. - 지점 c, d는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값입니다.
- 요금 f는 1 이상 100,000 이하인 자연수입니다.
- fares 배열에 두 지점 간 예상 택시요금은 1개만 주어집니다. 즉, [c, d, f]가 있다면 [d, c, f]는 주어지지 않습니다.
- 출발 지점 s에서 도착지점 a와 b로 가는 경로가 존재하는 경우만 입력으로 주어집니다.
[입출력 예]
| n | s | a | b | fares | result |
|---|---|---|---|---|---|
| 6 | 4 | 6 | 2 | [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] | 82 |
| 7 | 3 | 4 | 1 | [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] | 14 |
| 6 | 4 | 5 | 6 | [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4,8], [4,3,9]] | 18 |
입출력 예에 대한 설명
– 입출력 예 #1
문제 예시와 같습니다.
– 입출력 예 #2
- 합승을 하지 않고,
B는3→2→1,A는3→6→4경로로 각자 택시를 타고 가는 것이 최저 예상 택시요금입니다. - 따라서 최저 예상 택시요금은
(3 + 6) + (1 + 4) = 14원입니다.
– 입출력 예 #3
A와B가4→6구간을 합승하고B가 6번 지점에서 내린 후,A가6→5` 구간을 혼자 타고 가는 것이 최저 예상 택시요금입니다.- 따라서 최저 예상 택시요금은
7 + 11 = 18원입니다.
문제 풀이
그래프에서 최단 경로를 구하는 “dijkstra 알고리즘”, 또는 “Floyd-Warshal 알고리즘”을 사용하면 풀 수 있는 문제입니다.
이중 플로이드 알고리즘을 사용하여서 문제를 푼다고 가정하면, 다음과 같이 모든 지점 사이의 최저 예상 택시요금을 구할 수 있습니다.
d[i][j] = i번 지점에서 j번 지점까지 갈 때의 최저 예상 택시요금
그 다음, 다음과 같이 루프를 돌면서 최솟값을 찾아주면 됩니다.
문제에서 요구하는 답 = min(d[s][k] + d[k][a] + d[k][b]) (단, k = 1 ~ n)
문제 5 – 광고 삽입
- 정답률 : 1.23%
- 문제 5 풀러 가기
카카오TV에서 유명한 크리에이터로 활동 중인 죠르디는 환경 단체로부터 자신의 가장 인기 있는 동영상에 지구온난화의 심각성을 알리기 위한 공익광고를 넣어 달라는 요청을 받았습니다. 평소에 환경 문제에 관심을 가지고 있던 “죠르디”는 요청을 받아들였고 광고효과를 높이기 위해 시청자들이 가장 많이 보는 구간에 공익광고를 넣으려고 합니다. “죠르디”는 시청자들이 해당 동영상의 어떤 구간을 재생했는지 알 수 있는 재생 구간 기록을 구했고, 해당 기록을 바탕으로 공익광고가 삽입될 최적의 위치를 고를 수 있었습니다.
참고로 광고는 재생 중인 동영상의 오른쪽 아래에서 원래 영상과 동시에 재생되는 PIP(Picture in Picture) 형태로 제공됩니다.
다음은 “죠르디”가 공익광고가 삽입될 최적의 위치를 고르는 과정을 그림으로 설명한 것입니다.
- 그림의 파란색 선은 광고를 검토 중인 “죠르디” 동영상의 전체 재생 구간을 나타냅니다.
- 위 그림에서, “죠르디” 동영상의 총 재생시간은
02시간 03분 55초입니다.
- 위 그림에서, “죠르디” 동영상의 총 재생시간은
- 그림의 검은색 선들은 각 시청자들이 “죠르디”의 동영상을 재생한 구간의 위치를 표시하고 있습니다.
- 검은색 선의 가운데 숫자는 각 재생 기록을 구분하는 ID를 나타냅니다.
- 검은색 선에 표기된 왼쪽 끝 숫자와 오른쪽 끝 숫자는 시청자들이 재생한 동영상 구간의 시작 시각과 종료 시각을 나타냅니다.
- 위 그림에서, 3번 재생 기록은
00시 25분 50초부터00시 48분 29초까지 총00시간 22분 39초동안 죠르디의 동영상을 재생했습니다. [^1] - 위 그림에서, 1번 재생 기록은
01시 20분 15초부터01시 45분 14초까지 총00시간 24분 59초동안 죠르디의 동영상을 재생했습니다.
- 위 그림에서, 3번 재생 기록은
- 그림의 빨간색 선은 “죠르디”가 선택한 최적의 공익광고 위치를 나타냅니다.
- 만약 공익광고의 재생시간이
00시간 14분 15초라면, 위의 그림처럼01시 30분 59초부터01시 45분 14초까지 공익광고를 삽입하는 것이 가장 좋습니다. 이 구간을 시청한 시청자들의 누적 재생시간이 가장 크기 때문입니다. 01시 30분 59초부터01시 45분 14초까지의 누적 재생시간은 다음과 같이 계산됩니다.01시 30분 59초부터01시 37분 44초까지 : 4번, 1번 재생 기록이 두 차례 있으므로 재생시간의 합은00시간 06분 45초X 2 =00시간 13분 30초01시 37분 44초부터01시 45분 14초까지 : 4번, 1번, 5번 재생 기록이 세 차례 있으므로 재생시간의 합은00시간 07분 30초X 3 =00시간 22분 30초- 따라서, 이 구간 시청자들의 누적 재생시간은
00시간 13분 30초+00시간 22분 30초=00시간 36분 00초입니다.
- 만약 공익광고의 재생시간이
문제
“죠르디”의 동영상 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보 logs가 매개변수로 주어질 때, 시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 합니다. 이때, 공익광고가 들어갈 시작 시각을 구해서 return 하도록 solution 함수를 완성해 주세요. 만약, 시청자들의 누적 재생시간이 가장 많은 곳이 여러 곳이라면, 그중에서 가장 빠른 시작 시각을 return 하도록 합니다.
제한사항
- play_time, adv_time은 길이 8로 고정된 문자열입니다.
- play_time, adv_time은
HH:MM:SS형식이며,00:00:01이상99:59:59이하입니다. - 즉, 동영상 재생시간과 공익광고 재생시간은
00시간 00분 01초이상99시간 59분 59초이하입니다. - 공익광고 재생시간은 동영상 재생시간보다 짧거나 같게 주어집니다.
- play_time, adv_time은
- logs는 크기가 1 이상 300,000 이하인 문자열 배열입니다.
- logs 배열의 각 원소는 시청자의 재생 구간을 나타냅니다.
- logs 배열의 각 원소는 길이가 17로 고정된 문자열입니다.
- logs 배열의 각 원소는
H1:M1:S1-H2:M2:S2형식입니다.H1:M1:S1은 동영상이 시작된 시각,H2:M2:S2는 동영상이 종료된 시각을 나타냅니다.H1:M1:S1은H2:M2:S2보다 1초 이상 이전 시각으로 주어집니다.H1:M1:S1과H2:M2:S2는 play_time 이내의 시각입니다.
- 시간을 나타내는
HH, H1, H2의 범위는 00~99, 분을 나타내는MM, M1, M2의 범위는 00~59, 초를 나타내는SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예:04:60:24,11:12:78,123:12:45등) - return 값의 형식
- 공익광고를 삽입할 시각을
HH:MM:SS형식의 8자리 문자열로 반환합니다.
- 공익광고를 삽입할 시각을
[입출력 예]
| play_time | adv_time | logs | result |
|---|---|---|---|
"02:03:55" |
"00:14:15" |
["01:20:15-01:45:14", "00:40:31-01:00:00", "00:25:50-00:48:29", "01:30:59-01:53:29", "01:37:44-02:02:30"] |
"01:30:59" |
"99:59:59" |
"25:00:00" |
["69:59:59-89:59:59", "01:00:00-21:00:00", "79:59:59-99:59:59", "11:00:00-31:00:00"] |
"01:00:00" |
"50:00:00" |
"50:00:00" |
["15:36:51-38:21:49", "10:14:18-15:36:51", "38:21:49-42:51:45"] |
"00:00:00" |
입출력 예에 대한 설명
– 입출력 예 #1
문제 예시와 같습니다.
– 입출력 예 #2
01:00:00에 공익광고를 삽입하면 26:00:00까지 재생되며, 이곳이 가장 좋은 위치입니다. 이 구간의 시청자 누적 재생시간은 다음과 같습니다.
01:00:00-11:00:00: 해당 구간이 1회(2번 기록) 재생되었으므로 누적 재생시간은10시간 00분 00초입니다.11:00:00-21:00:00: 해당 구간이 2회(2번, 4번 기록) 재생되었으므로 누적 재생시간은20시간 00분 00초입니다.21:00:00-26:00:00: 해당 구간이 1회(4번 기록) 재생되었으므로 누적 재생시간은05시간 00분 00초입니다.- 따라서, 이 구간의 시청자 누적 재생시간은
10시간 00분 00초+20시간 00분 00초+05시간 00분 00초=35시간 00분 00초입니다. - 초록색으로 표시된 구간(
69:59:59-94:59:59)에 광고를 삽입해도 동일한 결과를 얻을 수 있으나,01:00:00이69:59:59보다 빠른 시각이므로,"01:00:00"을 return 합니다.
– 입출력 예 #3
동영상 재생시간과 공익광고 재생시간이 같으므로, 삽입할 수 있는 위치는 맨 처음(00:00:00)이 유일합니다.
[^1]: 동영상 재생시간 = 재생이 종료된 시각 - 재생이 시작된 시각(예를 들어, 00시 00분 01초부터 00시 00분 10초까지 동영상이 재생되었다면, 동영상 재생시간은 9초입니다.)
문제 풀이
문제를 쉽게 해결하려면, 등장하는 모든 시각을 초로 환산하여 접근하는 것이 필요합니다. play_time이 99시 59분 59초이하가 되므로, 문제에서 나올 수 있는 모든 시각의 개수는 100 * 60 * 60 = 360000개를 넘지 않습니다.
STEP 1.
매개변수로 주어진 play_time, adv_time, logs에 대해서, 시각을 초로 환산하여 아래와 같이 저장합니다.
logs_start_sec[i] = logs[i]의 시작 시각을 초로 환산한 값
logs_end_sec[i] = logs[i]의 종료 시각을 초로 환산한 값
play_time_sec = play_time을 초로 환산한 값
adv_time_sec = adv_time을 초로 환산한 값
STEP 2.
다음과 같이 total_time 배열을 정의합니다.
total_time[x] = x 시각에 시작된 재생 구간의 개수 – x 시각에 종료된 재생구간의 개수
이렇게 정의한 total_time 배열은 STEP 1.에서 만든 logs_start_sec과 logs_end_sec 배열을 사용하여 구해줄 수 있습니다.
for i = 0 ~ logs의 마지막 인덱스
total_time[logs_start_sec[i]] = total_time[logs_start_sec[i]] + 1
total_time[logs_end_sec[i]] = total_time[logs_end_sec[i]] - 1
STEP 3.
다음과 같이 total_time 배열을 재정의합니다.
total_time[x] = 시각 x부터 x+1까지 1초 간의 구간을 포함하는 재생 구간의 개수
재정의된 total_time 배열은 STEP 2.에서 만든 기존의 total_time 배열을 이용하여 계산할 수 있습니다.
for i = 1 ~ (play_time_sec - 1)
total_time[i] = total_time[i] + total_time[i - 1]
STEP 4.
다음과 같이 total_time 배열을 재정의합니다.
total_time[x] = 시각 0부터 x+1까지 x+1초 간의 구간을 포함하는 누적 재생시간
재정의된 total_time 배열은 STEP 3.에서 만든 기존의 total_time 배열을 이용하고, 완전히 똑같은 반복문을 한 번 더 실행하면 구해줄 수 있습니다.
for i = 1 ~ (play_time_sec - 1)
total_time[i] = total_time[i] + total_time[i - 1]
STEP 5.
마지막으로 정답을 구하는 과정입니다.
for i = (adv_time_sec - 1) ~ (play_time_sec - 1)
if ( i >= at)
max_time = max(max_time, total_time[i] - total_time[i - at] )
else
max_time = max(max_time, total_time[i])위 코드는 반복문을 돌며 시각 i - at + 1에 광고를 넣을 때의 누적 재생 시간을 구하여, 그중에서 가장 긴 시간을 max_time에 넣어주고 있습니다. max_time 값이 마지막으로 업데이트될 때의 시각 i - at + 1을 HH:MM:SS 형태로 변환한 값이 문제에서 요구하는 정답입니다.
문제 6 – 카드 짝 맞추기
- 정답률 : 0.95%
- 문제 6 풀러 가기
게임 개발자인 베로니는 개발 연습을 위해 다음과 같은 간단한 카드 짝 맞추기 보드게임을 개발해 보려고 합니다.
게임이 시작되면 화면에는 카드 16장이 뒷면을 위로하여 4 x 4 크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오 프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다.
유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원래 상태로 뒷면이 보이도록 뒤집힙니다. 이와 같은 방법으로 모든 카드를 화면에서 사라지게 하면 게임이 종료됩니다.
게임에서 카드를 선택하는 방법은 다음과 같습니다.
- 카드는
커서를 이용해서 선택할 수 있습니다. - 커서는 4 x 4 화면에서 유저가 선택한 현재 위치를 표시하는 “굵고 빨간 테두리 상자”를 의미합니다.
- 커서는 [Ctrl] 키와 방향 키에 의해 이동되며 키 조작법은 다음과 같습니다.
- 방향키 ←, ↑, ↓, → 중 하나를 누르면, 커서가 누른 키 방향으로 1칸 이동합니다.
- [Ctrl] 키를 누른 상태에서 방향키 ←, ↑, ↓, → 중 하나를 누르면, 누른 키 방향에 있는 가장 가까운 카드로 한 번에 이동합니다.
- 만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다.
- 만약, 누른 키 방향으로 이동 가능한 카드 또는 빈 공간이 없어 이동할 수 없다면 커서는 움직이지 않습니다.
- 커서가 위치한 카드를 뒤집기 위해서는 [Enter] 키를 입력합니다.
- [Enter] 키를 입력해서 카드를 뒤집었을 때
- 앞면이 보이는 카드가 1장뿐이라면 그림을 맞출 수 없으므로 두 번째 카드를 뒤집을 때까지 앞면을 유지합니다.
- 앞면이 보이는 카드가 2장이 된 경우, 두 개의 카드에 그려진 그림이 같으면 해당 카드들이 화면에서 사라지며, 그림이 다르다면 두 카드 모두 뒷면이 보이도록 다시 뒤집힙니다.
“베로니”는 게임 진행 중 카드의 짝을 맞춰 몇 장 제거된 상태에서 카드 앞면의 그림을 알고 있다면, 남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값을 구해 보려고 합니다. 키 조작 횟수는 방향 키와 [Enter] 키를 누르는 동작을 각각 조작 횟수 1로 계산하며, [Ctrl] 키와 방향 키를 함께 누르는 동작 또한 조작 횟수 1로 계산합니다.
다음은 카드가 몇 장 제거된 상태의 게임 화면에서 커서를 이동하는 예시입니다.
아래 그림에서 빈칸은 이미 카드가 제거되어 없어진 칸을 의미하며, 그림이 그려진 칸은 카드 앞 면에 그려진 그림을 나타냅니다.
예시에서 커서는 두 번째 행, 첫 번째 열 위치에서 시작하였습니다.
[Enter] 입력, ↓ 이동, [Ctrl]+→ 이동, [Enter] 입력 = 키 조작 4회
[Ctrl]+↑ 이동, [Enter] 입력, [Ctrl]+← 이동, [Ctrl]+↓ 이동, [Enter] 입력 = 키 조작 5회
[Ctrl]+→ 이동, [Enter] 입력, [Ctrl]+↑ 이동, [Ctrl]+← 이동, [Enter] 입력 = 키 조작 5회
위와 같은 방법으로 커서를 이동하여 카드를 선택하고 그림을 맞추어 카드를 모두 제거하기 위해서는 총 14번(방향 이동 8번, [Enter] 키 입력 6번)의 키 조작 횟수가 필요합니다.
문제
현재 카드가 놓인 상태를 나타내는 2차원 배열 board와 커서의 처음 위치 r, c가 매개변수로 주어질 때, 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
제한사항
- board는 4 x 4 크기의 2차원 배열입니다.
- board 배열의 각 원소는 0 이상 6 이하인 자연수입니다.
- 0은 카드가 제거된 빈칸을 나타냅니다.
- 1부터 6까지의 자연수는 2개씩 들어있으며 같은 숫자는 같은 그림의 카드를 의미합니다.
- 뒤집을 카드가 없는 경우(board의 모든 원소가 0인 경우)는 입력으로 주어지지 않습니다.
- r은 커서의 최초 세로(행) 위치를 의미합니다.
- c는 커서의 최초 가로(열) 위치를 의미합니다.
- r과 c는 0 이상 3 이하인 정수입니다.
- 게임 화면의 좌측 상단이 (0, 0), 우측 하단이 (3, 3)입니다.
[입출력 예]
| board | r | c | result |
|---|---|---|---|
| [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] | 1 | 0 | 14 |
| [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] | 0 | 1 | 16 |
입출력 예에 대한 설명
– 입출력 예 #1
문제의 예시와 같습니다.
– 입출력 예 #2
입력으로 주어진 게임 화면은 아래 그림과 같습니다.
위 게임 화면에서 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값은 16번입니다.
문제 풀이
카드 종류가 최대 6개이므로, 어떤 카드부터 제거해 나갈지 정하는 방법은 6! 가지입니다. 예를 들어 카드가 3종류인 경우, 3종류 카드를 제거하는 순서는 다음과 같이 6가지입니다.
- 1, 2, 3
- 1, 3, 2
- 2, 1, 3
- 2, 3, 1
- 3, 1, 2
- 3, 2, 1
위와 같이 카드를 제거하는 모든 순서에 대해서 각각 카드를 제거해 보고, 그중 키 조작 횟수가 가장 적은 방법을 찾으면 됩니다. 이때, 각 카드는 종류별로 2장씩이므로, 두 카드를 제거하는 순서에 따라 키 조작 횟수가 달라질 수 있음을 주의합니다. 즉, 현재 제거해야 되는 카드 번호 X에 대해서, 카드 하나를 XA, 다른 카드 하나를 XB라고 했을 때 다음 두 가지 경우에 대해 고려해 주면 됩니다.
- 현재 커서 위치 → XA 카드를 제거 → XB 카드를 제거
- 현재 커서 위치 → XB 카드를 제거 → XA 카드를 제거
만약 XB 카드를 나중에 제거했고, X 카드 다음으로 Y 카드를 제거해야 한다면 이번에는 다음과 같이 두 가지 경우를 고려합니다.
- 현재 커서 위치(XB 카드 위치) → YA 카드를 제거 → YB 카드를 제거
- 현재 커서 위치(XB 카드 위치) → YB 카드를 제거 → YA 카드를 제거
따라서 위와 같은 방법으로 카드를 제거하는 가능한 모든 방법을 고려해 주면 되며, “현재 커서 위치 → XA 카드를 제거”와 같이 커서를 이동시키는 최소 조작 횟수는 BFS 탐색을 이용하여 최단거리를 구하면 됩니다.
문제 7 – 매출 하락 최소화
- 정답률 : 0.57%
- 문제 7 풀러 가기
유통 전문 회사 카카오상사의 오너인 제이지는 새로운 사업 아이템을 구상하기 위해 전문경영인(CEO)인 프로도에게 회사의 경영을 부탁하였습니다.
“카카오 상사”는 직원들을 여러 개의 팀 단위로 조직을 구성하고 있으며 아래 그림은 CEO를 포함하여 10명의 직원과 4개의 팀으로 구성되어 있는 회사 조직도를 보여주고 있습니다.
그림의 조직도는 다음과 같이 설명할 수 있습니다.
- 그림의 각 원들은 각각의 직원 1명을 표시하고 있으며, CEO를 포함하여 총 10명의 직원을 표시하고 있습니다.
- 원 안에 적힌 두 개의 숫자는 직원의 정보를 담고 있습니다. 왼쪽 숫자는
직원 번호이며 직원을 식별할 수 있도록 1번부터 순서대로 발급되는 일련번호이며, 오른쪽 숫자는해당 직원의 하루 평균 매출액을 나타냅니다. 위 그림에서1번직원은 14원을,9번직원은 28원의 하루 평균 매출액을 기록하고 있습니다. - CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 쪽의 직원은 팀원을 의미합니다.
3-1. 직원 번호1번은 회사의 CEO로 고정되어 있으며, CEO는 항상 팀장이고 팀원일 수 없어 화살표를 받는 쪽이 될 수 없습니다.
3-2. 반면에 CEO를 제외한 나머지 모든 직원들은 다른 누군가로부터 정확히 1개의 화살표를 받게 됩니다.
3-3. 한 직원은 최대 2개의 팀에 소속될 수 있습니다. 만약 어떤 직원이 두 개의 팀에 소속되어 있다면, 반드시 하나의 팀에서는 팀장, 나머지 팀에서는 팀원이어야 합니다. 팀장을 겸임하거나, 두 개의 팀에서 팀원이 될 수는 없습니다. 예를 들어10번직원은D팀의 팀장이면서 동시에5번직원이 팀장으로 있는C팀에 속한 팀원입니다.
3-4.5번, 9번, 10번직원은 받는 쪽의 화살표와 시작하는 화살표가 모두 있으므로 팀장인 동시에 팀원입니다.
3-5.2번, 3번, 4번, 6번, 7번, 8번직원은 시작하는 화살표가 없고 받는 쪽의 화살표만 있으므로 팀장이 아니며 오직 팀원입니다.
3-6.1번직원인 CEO는 받는 쪽의 화살표가 없고 시작하는 화살표만 있으며 항상 팀원이 아닌 팀장입니다.
3-7. 그림의 조직도에는A, B, C, D총 4개의 팀이 존재하며, 각각1번, 9번, 5번, 10번직원이 팀장 직위를 담당하게 됩니다.
“제이지”는 자신이 구상한 새로운 사업 아이템에 대해 직원들에게 설명하고자 하루 일정으로 워크숍을 계획하고 있습니다. 단, 모든 직원을 참석시킬 수 없어 아래와 같은 기준으로 워크숍에 참석할 직원들을 선발하려고 합니다.
- 워크숍에서 교육받은 내용은 전 직원들에게 공유되어야 하므로
모든 팀은 최소 1명 이상의 직원을 워크숍에 참석시켜야 합니다. - 워크숍 기간 동안, 회사의 매출 손실을 최소화하는 것이 중요하므로 워크숍에 참석하는 직원들의 하루 평균 매출액의 합이 최소가 되어야 합니다.
위 그림의 조직도에서 회색으로 색칠된 1번, 7번, 10번 직원을 워크숍에 참석시키면 모든 팀에서 최소 한 명 이상의 직원을 참석시킨 것이 되며, 해당 직원들의 하루 평균 매출액의 합은 44(14+13+17)원입니다. 10번 직원은 C팀과 D팀 모두에 속해 있으므로, 두 팀에서 모두 참석한 것으로 인정됩니다.
문제
직원들의 하루 평균 매출액 값을 담은 배열 sales, 직원들의 팀장-팀원의 관계를 나타내는 2차원 배열 links가 매개변수로 주어집니다. 이때, 모든 팀에서 최소 한 명 이상 워크숍에 참석하면서, 참석하는 직원들의 하루 평균 매출액의 합을 최소로 하려고 합니다. 그렇게 최소화된 매출액의 합을 구해서 return 하도록 solution 함수를 완성해 주세요.
제한사항
- sales 배열의 크기는 2 이상 300,000 이하입니다. sales 배열의 크기는 CEO를 포함한 전체 직원 수와 같습니다.
- sales 배열은 각 직원들의 하루 평균 매출액을 담고 있으며,
1번직원부터 직원 번호 순서대로 주어집니다. - sales 배열의 각 원소의 값은 0 이상 10,000 이하인 정수입니다.
- links 배열의 크기는
sales 배열의 크기 - 1입니다. 즉, 전체 직원 수보다 1이 작습니다. - links 배열의 각 원소는 [a, b] 형식입니다.
- a는 팀장의 직원 번호, b는 a 팀장이 관리하는 팀원의 직원 번호이며, a와 b는 서로 다른 자연수입니다.
- 1 ≤
a≤sales 배열의 크기입니다. - 2 ≤
b≤sales 배열의 크기입니다. - 직원 번호 1은 CEO로 정해져 있고 CEO는 항상 팀장이므로 b ≠ 1 입니다.
- links 배열로 만들어지는 조직도는 하나의 트리 구조 형태입니다.
- 정답으로 return 되는 값은 2^31 – 1 이하인 자연수임이 보장됩니다.
[입출력 예]
| sales | links | result |
|---|---|---|
| [14, 17, 15, 18, 19, 14, 13, 16, 28, 17] | [[10, 8], [1, 9], [9, 7], [5, 4], [1, 5], [5, 10], [10, 6], [1, 3], [10, 2]] | 44 |
| [5, 6, 5, 3, 4] | [[2,3], [1,4], [2,5], [1,2]] | 6 |
| [5, 6, 5, 1, 4] | [[2,3], [1,4], [2,5], [1,2]] | 5 |
| [10, 10, 1, 1] | [[3,2], [4,3], [1,4]] | 2 |
입출력 예에 대한 설명
– 입출력 예 #1
입출력 예 #1
문제 예시와 같습니다.
– 입출력 예 #2
직원 번호가 2인 직원 한 명을 워크숍에 참석시키는 것이 최선이며, 2번 직원의 하루 평균 매출액은 6원입니다. 따라서 6을 return 해주어야 합니다.
– 입출력 예 #3
직원 번호가 4, 5인 직원 두 명을 워크숍에 참석시키는 것이 최선이며, 4번, 5번 직원의 하루 평균 매출액의 합은 5(1+4)원입니다. 따라서 5를 return 해주어야 합니다.
– 입출력 예 #4
직원 번호가 3, 4인 직원 두 명을 워크숍에 참석시키는 것이 최선이며, 3번, 4번 직원의 하루 평균 매출액의 합은 2(1+1)원입니다. 따라서 2를 return 해주어야 합니다.
문제 풀이
트리 자료구조를 잘 이해하고, 다이나믹 프로그래밍을 활용할 수 있어야 풀 수 있는 문제입니다.
1번 루트 노드(CEO)가 워크숍에 참석할 경우, 불참할 경우 각각에 대한 최적해를 구하고 싶다면, 그 자식 노드들이 루트가 되는 각각의 서브트리 대한 최적해가 구해져 있어야 합니다. 즉, 루트 노드부터 DFS로 내려오면서, 각각의 노드가 루트가 되는 서브트리에 대한 최적해를 구하는 과정을 수행하면 됩니다. 최적의 해는 DFS로 방문한 순서의 역방향으로 차례대로 결정이 되며, 리프 노드에 대한 최적해가 처음에 정해지고, 마지막에야 비로소 1번 루트 노드에 대한 최적해를 구할 수 있습니다.
다이나믹 배열을 아래와 같이 정의합니다.
d[i][0] : i번 노드가 루트인 서브트리에서, i번 노드가 워크숍에 불참하는 경우의 최적해
d[i][1] : i번 노드가 루트인 서브트리에서, i번 노드가 워크숍에 참석하는 경우의 최적해
이렇게 배열 d를 정의했다면, 이 문제에서 요구하는 답은 min(d[1][0], d[1][1])입니다.
그러면 다이나믹 배열 d를 어떻게 구할 수 있는지 알아보겠습니다. 편의를 위해, 보조 배열 sum_child를 다음과 같이 구해놓습니다.
sum_child[i] = sum(min(d[k][0] , d[k][1])) {i의 모든 자식 노드 k에 대해서}보조 배열 sum_child를 이용하면, d를 구할 수 있습니다.
d[i][1] = sales[i] + sum_childi의 모든 자식 노드 k에 대해서, d[k][0] > d[k][1] 를 만족하는 k개가 한 개라도 있다면:
d[i][0] = sum_child
i의 모든 자식 노드 k에 대해서, d[k][0] > d[k][1] 를 만족하는 k개가 한 개도 없다면:
d[i][0] = sum_child + min(d[k][1] - d[k][0])d[i][1]을 계산하는 방법은 간단합니다. i가 워크숍에 참석을 했으므로, 자식들이 워크숍에 참석하든 말든, 최소 한 팀에서 한 명 이상 워크숍 참석의 조건을 만족하게 됩니다.
d[i][0]는 경우를 2가지로 나누어서 생각해야 합니다.
d[k][0] > d[k][1] 를 만족하는 k개가 한 개라도 있다면 : sum_child[i]를 구하는 과정에서 d[k][1]가 적어도 한 번은 더해졌다는 의미가 됩니다. 즉, i의 자식 노드 중에서 워크숍에 참석한 노드가 있으므로, 문제의 조건을 만족합니다.
d[k][0] > d[k][1] 를 만족하는 k개가 한 개도 없다면 : sum_child[i]를 구하는 과정에서 d[k][1]가 한 번도 더해지지 않았다는 의미가 됩니다. 즉, i의 자식 노드 중에서 워크숍에 참석한 노드가 없으므로, 강제로 하나의 노드를 참석시켜야 합니다. 이때, 가능하면 d[k][1] - d[k][0]의 값이 최소인 k를 참석시키는 것이 좋습니다. 즉, 매출 손해가 가장 작게 발생하도록 k를 선택해서, 워크숍에 참석시키면 문제에서 요구하는 답을 얻을 수 있습니다.
마치며
지금까지 2021 카카오 신입 개발자 공채 1차 코딩 테스트 문제를 살펴보았습니다. 문제의 풀이 방법은 항상 하나만 존재하는 것이 아니므로, 다양한 방법을 시도해보시기를 권해드리며, 이러한 과정이 개인의 개발 역량 증대에 큰 도움이 될 것입니다.
테스트에 응시하신 분들 모두 감사의 말씀을 드리며, 앞으로의 희망찬 앞날을 기원하겠습니다.
✔️ 카카오 온라인 코딩 테스트 문제해설 바로가기
- 2019 카카오 신입 공채 1차 코딩 테스트 문제해설
- 2019 카카오 겨울 인턴십 코딩 테스트 문제해설
- 2020 카카오 신입 공채 1차 코딩 테스트 문제해설
- 2020 카카오 여름 인턴십 코딩 테스트 문제해설
