[Algorithm] - 2021 카카오 신입 1차 온라인 코딩 테스트 (Kakao Newbie Primary Online Coding Test) for Tech Developers 문제 풀이

지난 주, 2021년 카카오 신입 온라인 코딩 테스트 문제 풀이가 카카오 공식 블로그에 올라오게 되면서 풀이를 해보게 되었습니다. 개인적으로 인턴십 문제나 이런 문제들도 많이 봤었는데, 신입 문제를 풀이한 것은 거의 없었는데요.

 

먼저 짤막하게 요점을 말씀드리자면 인턴십 코딩 테스트와 신입 코딩 테스트의 문제 난이도가 조금 차이가 있었습니다. DFS나 BFS 문제들이 가끔 한 문제 정도 나오는 인턴십 코딩 테스트에 비해 신입 코딩 테스트에서는 백트래킹이나 다익스트라 알고리즘과 같은 Computer Science의 기본 알고리즘 구현 문제도 같이 있어서 이러한 부분도 조금 준비를 해두는 게 좋을 것 같다라는 생각을 했습니다.

 

그럼 문제 풀이를 시작해보도록 하죠.

 

 

 

 

Question 01. 아이디 추천

문제 원문: (https://programmers.co.kr/learn/courses/30/lessons/72410)

 

카카오에 입사한 신입 개발자 네오는 “카카오계정개발팀”에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었고, “네오”에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해 주는 프로그램을 개발하는 문제였습니다.

(이전 글과 마찬가지로 문제에 대한 상세 사항은 생략하겠습니다. 자세한 문제는 문제 원문을 참고해주세요.)

 

 

Solution for Question 01

1번 문제는 문제만 잘 읽어보셨다면 따로 문제를 파악할 필요도 없이 정해진 지침사항대로 알고리즘을 구현하면 쉽게 풀 수 있는 문제였습니다. 정답률이 무려 57%가 넘는 쉬운 문제였습니다.

 

주어진 조건을 정규식으로 풀어낸다면 좀 더 깔끔한 코드로 풀어볼 수 있습니다. 정규식은 대부분 모든 프로그래밍 언어에서 제공하며 정규식이 아니더라도 조금 메소드를 복잡하게 구현해서도 풀 수 있는 방법 등 여러 방법이 있습니다.

 

심지어 주어진 조건의 입력 문자열 길이가 1,000자도 되지 않기 때문에 자유롭게 풀 수 있는 문제기도 했습니다.

 

 

 

 

Question 02. 메뉴 리뉴얼

문제 원문; (https://programmers.co.kr/learn/courses/30/lessons/72411)

 

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품 메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을지 고민하던 “스카피”는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품 메뉴들을 코스요리 메뉴로 구성하기로 했습니다.

 

단, 코스요리 메뉴는 최소 2가지 이상의 단품 메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품 메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했으며 주문한 메뉴 조합을 토대로 가장 많이 주문한 메뉴를 골리 코스요리 메뉴 후보 리스트를 뽑을 수 있도록 알고리즘을 구현하는 문제입니다.

 

 

 

Solution for Question 02

2번 문제를 풀 때 조금 헷갈렸던 점이 있었는데, 주어진 배열에서 메뉴가 있을 때 모든 메뉴에 대해서 중복 주문된 메뉴를 토대로 코스 요리를 선정했다면 문제를 풀지 못했을 가능성이 매우 높습니다.

 

먼저 주어지는 메뉴에서 나올 수 있는 조합을 재귀 함수를 통하여 구해줍니다. 이 때 조합을 구할 때는 A, B 주문과 B, A 주문이 중복되지 않도록 주의해야 하며. 이 조합을 구하고나서 각 조합의 갯수를 세고, 정렬하면 됩니다.

 

Java를 사용한다면 TreeSet을 이용하여 별도의 정렬 알고리즘을 사용하지 않고 알파벳 순서를 보장 받을 수 있는 메소드를 사용하는 것도 좋은 방법일 수 있습니다. 그러나 중복의 여부를 확인하기 위해서 각 주문 조합을 정렬할 필요는 있습니다.

 

각 조합별로 갯수를 세고, 원하는 조합의 갯수를 수집한 다음, 조합의 갯수 모음에서 가장 많이 나온 주문 건으로 출력해주면 쉽게 풀 수 있습니다.

 

 

 

 

Question 03. 순위 검색

문제 원문: (https://programmers.co.kr/learn/courses/30/lessons/72412)

 

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

 

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩 테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.

 

• 코딩 테스트 참여 개발 언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
• 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
• 지원 경력 구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
• 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.

 

인재영입팀에 근무하고 있는 니니즈는 코딩 테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다 예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.

코딩 테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩 테스트 점수를 50점 이상 받은 지원자는 몇 명인가?

 

위와 같은 조건을 바탕으로 any 언어, any 직군, any 경력, any 소울 푸드의 조건 등으로 케이스를 구분한다고 했을 때 이에 해당하는 사람들의 숫자를 순서대로 배열에 담아 반환하는 알고리즘을 구현하는 문제였습니다.

 

 

 

Solution for Question 03

드디어 나왔습니다. 카카오 문제의 벽, 효율성 테스트 문제,

저도 이 문제를 처음 접했을 때는 각 쿼리를 파싱하여 해당하는 데이터와 일치하는 부분이 있다면 이를 반환하도록 알고리즘을 구현했지만 호락호락하게 넘어가지 않았습니다. 그래서 해설을 조금 참고해 Query에 해당하는 모든 조합을 구하여 그 조합에 포함되는 데이터가 있는지를 본 다음 구현하여 작성해봤습니다.

 

그러나 길이로만 봤을 때 주어지는 길이가 100,000이 넘는 상황에서 해당 조합을 구하고, 모든 Query를 비교하니 Java에서는 이 문제의 효율성 테스트를 통과하지 못했습니다.

 

비슷한 해설로 Python에서 문제 풀이를 시도하였을 때는 잘 통과가 되었지만 Java에서 문제 풀이를 진행할 때만 유독 같은 해설 풀이로 문제를 통과하지 못했던 것은 카카오 코딩 테스트 문제 풀이를 하면서 처음 겪는 일이었습니다. 

 

결국 Java에서 문제풀이가 잘 진행되지 않아 코드가 조금 지저분하더라도 Java에서 그나마 빠른 자료구조인 Map을 사용하여 문제 풀이를 진행해봤습니다.

 

Map을 이용하여 언어를 맨 위의 루트로 삼고, 언어 -> 직군 -> 경력 -> 소울 푸드라는 트리의 구조를 그리고, 아까 위에서 만든 조합을 4중 Map을 이용하여 하드 코딩한 구현체입니다. 풀이하고 나서 이런 풀이를 올리는 게 개인적으로 민망한 부분도 없지 않아 있었지만 효율성 테스트를 완벽하게 통과할 수 있는 방법으로 이 방법 밖에는 도저히 생각해내지 못했습니다. 개인적으로 아쉬웠던 문제이기도 했습니다.

 

 

 

 

Question 04. 합승 택시 요금

문제 원문: (https://programmers.co.kr/learn/courses/30/lessons/72413)

 

밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. “무지”는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. “무지”는 “어피치”와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을지 계산해 보고 “어피치”에게 합승을 제안해 보려고 합니다.

 

이러한 택시 노선과 예상 요금을 주어줄 때 최저 예상 택시 요금을 계산해 반환하는 알고리즘을 작성하는 문제였습니다.

 

 

 

Solution for Question 04

나름 재미있게 풀었던 문제라고 생각합니다. 가끔 차없이 여행을 하거나 누구와 동행을 했을 때 이런 경로로 중간에 세워주고, 택시 요금을 어떻게 최소로 줄일 수 있을지 알려준다면 정말 좋겠다고 생각을 했기도 한 문제였네요.

 

이렇게 택시의 최저 요금을 구하는 문제는 최소 경로를 구해서 빠르게 이동하는 것과 같기 때문에 이런 종류의 문제는 다익스트라(Dijkstra) 알고리즘을 이용하여 쉽게 구할 수 있습니다. 만약 다익스트라 알고리즘에 대해 어려우셨던 분들이라면 이번 기회에 배워보고 잘 사용해보시면 좋을 것 같네요.

 

두 사람이 도착하는 지점을 각각 주어지고, 그것에 해당하는 요금이 주어집니다. 따라서 A 지점에 도착했을 때 최소 비용과 B 지점에서 도착했을 때의 최소 비용을 그래프를 구현하여 저장한 다음, 우선 순위 큐를 이용합니다.

 

이 때 우선 순위 큐를 이용할 때는 비용이 최소인 부분을 우선으로 돌게합니다. 지점이 두 곳이 있기 때문에 A 지점에서 최소일 때 B 지점을 순회, B 지점에서 최소일 때 A 지점 순회를 하여 최소 비용을 구하면 쉽게 풀 수 있는 문제입니다.

 

공식 해설에서는 Floyd-Warshal 알고리즘을 사용해서도 풀 수 있다고 나와 있는데, 저도 이 알고리즘에 대해서는 잘 모르겠어서 개인적으로 공부해보고 기회가 된다면 이 알고리즘으로 한 번 재풀이해보는 것도 좋을 것 같네요.

 

 

 

 

Question 05. 광고 삽입

문제 원문: (https://programmers.co.kr/learn/courses/30/lessons/72414)

 

카카오TV에서 유명한 크리에이터로 활동 중인 죠르디는 환경 단체로부터 자신의 가장 인기있는 동영상에 지구온난화의 심각성을 알리기 위한 공익광고를 넣어 달라는 요청을 받았습니다. 평소에 환경 문제에 관심을 가지고 있던 죠르디는 요청을 받아들였고 광고효과를 높이기 위해 시청자들이 가장 많이 보는 구간에 공익광고를 넣으려고 합니다. 죠르디는 시청자들이 해당 동영상의 어떤 구간을 재생했는 지 알 수 있는 재생구간 기록을 구했고, 해당 기록을 바탕으로 공익광고가 삽입될 최적의 위치를 고를 수 있었는데요. 우리는 죠르디가 주어주는 동영상 재생 구간 기록과 광고 재생 시간을 가지고, 사용자가 광고를 많이 볼 수 있는 최적의 위치를 골라주는 알고리즘을 구현해 죠르디에게 알려주는 문제였습니다.

 

 

 

 

Solution for Question 05

이 문제도 나름 특이한 문제였지만 YouTube를 즐겨보는 저의 입장에서 그들이 광고를 이렇게도 삽입할 수 있겠구나 라는 생각을 하며 흥미를 가지고 도전해본 문제였습니다. 처음 접근했을 때는 시간 데이터를 Date 객체에 맞춰 바꾸어 이들의 중간 시간을 체크하면 된다고 생각했지만 해당 알고리즘은 생각보다 정확하지 못했습니다.

 

문제의 해설에서 주어진 시간의 최대 길이를 보고 약간의 힌트를 얻을 수 있었습니다. 최대 100시간으로 촬영된 동영상이기 때문에 이를 초로 바꿔서 계산하면 100 * 60 * 60 = 360000초이며 이는 배열로도 충분히 그 공간을 할당해서 풀 수 있는 문제라고 생각했습니다. 

 

간단히 얘기하자면 전체의 길이에서 특정 길이의 구간합이 가장 큰 걸 구하면 되는 문제인데, 가령 전체 플레이 시간에서 광고의 시간을 전부 완전 탐색해도 되지만 그렇게만 푼다면 일부 테스트 케이스에서 시간 초과가 날 것입니다.

 

따라서 시작구간부터 광고 시간까지 들어갈 수 있는 구간을 큐로 잡아서 묶어두고, 그 광고가 들어갈 수 없는 구간을 제외시킵니다. 예를 들어 광고 시간이 14시간이고 전체 플레이 시간이 28시간이라면 동영상이 끝나는 14시간 이후 지점부터는 광고가 들어갈 수 없다는 점을 감안하여 구하는 것입니다.

 

그러고 난 뒤 배열에 해당하는 인덱스 구간을 시간대로 바꿔주면 문제를 풀 수 있습니다.

 

 

 

 

Question 06. 카드 짝 맞추기

문제 원문: (https://programmers.co.kr/learn/courses/30/lessons/72415)

 

게임 개발자인 베로니는 개발 연습을 위해 다음과 같은 간단한 카드 짝맞추기 보드 게임을 개발해 보려고 합니다.
게임이 시작되면 화면에는 카드 16장이 뒷면을 위로하여 4 x 4 크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다.
유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원래 상태로 뒷면이 보이도록 뒤집힙니다. 이와 같은 방법으로 모든 카드를 화면에서 사라지게 하면 게임이 종료됩니다.

 

이러한 게임에서 게임 한판이 주어질 때 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값을 구하는 알고리즘을 구현하는 문제였습니다.

 

 

 

Solution for Question 06

카카오 게임 내지 보드 게임에서 흔히 볼 수 있는 기능을 구현하는 문제인데, 가령 빅쥬엘이나 애니팡 등의 게임을 해보셨다면 그에 해당하는 최소 움직임 횟수를 사용자게에 주어주고, 그만큼 못움직이면 게임을 종료시키는 아주 잔인한 알고리즘이기도 한데요. 개인적으로 이 문제가 정말 어려웠습니다.

 

Board의 좌표 지점을 이용하는데, 게다가 여기에 해당하는 최소 움직이는 횟수를 구하는 것이기 때문에 위의 4번 문제처럼 우선 순위 큐를 이용하여 이동 횟수가 가장 적은 것을 기록해서 풀 수 있는 방법이 있습니다. 우선 순위 큐에서 가장 중요한 것은 어떤 변수를 기준으로 우선 순위를 매기냐는 것인데요. 이 때는 C++의 operator나 Java의 Comparable 인터페이스를 잘 다루는 것이 중요하겠습니다.

 

보드판의 카드를 뒤집어 그 방향을 최소한으로 잡을 수 있도록 Backtracking 알고리즘을 이용해 그 데이터를 만들어줍니다. 이 부분이 조금 어려웠죠. 위에서의 문제에서는 어떤 방향에서 어디로 가면 이 비용입니다.를 입력 데이터로 주어졌지만 이 문제는 이걸 직접 데이터화를 해야한다는 것입니다.

 

여기서 중요한 점은 여러 조건이 있다는 것인데, 카드가 근처에 있지 않더라도 조합키(Ctrl)를 이용하여 이동이 가능하다는 점을 고려해야합니다. 

 

 

 

 

Question 07. 매출 최소화

문제 원문: (https://programmers.co.kr/learn/courses/30/lessons/72416)

 

유통전문회사 카카오상사의 오너인 제이지는 새로운 사업 아이템을 구상하기 위해 전문경영인(CEO)인 프로도에게 회사의 경영을 부탁하였습니다. 카카오상사는 직원들을 여러 개의 팀 단위로 조직을 구성하고 있으며 아래 그림은 CEO를 포함하여 10명의 직원과 4개의 팀으로 구성되어 있는 회사 조직도를 보여주고 있습니다.

 

이러한 회사 조직도에서 검정색 숫자는 사원번호, 빨간색 숫자는 매출액을 나타냅니다. 직원들은 워크샵을 나가면서 매출액을 기록하는데, 이러한 데이터가 주어졌을 때 워크샵에 참석하는 직원들의 하루 평균 매출액의 합을 최소로 만들어주는 알고리즘을 구현하는 문제입니다.

 

 

 

 

Solution for Question 07

이 문제는 다이나믹 프로그래밍의 개념을 필요로 하는 문제입니다. 먼저 직원들의 구조는 자료 구조 트리를 떠올린다면 쉽게 그 구조를 나타낼 수 있을 것이라고 봅니다. 따라서 이들 트리를 먼저 데이터화 시켜 구현한 다음, 다이나믹 프로그래밍 기법을 이용하여 매출을 기록하고 그 합이 최소인 것을 찾으면 됩니다.

 

자료를 구성할 때 직원 번호와 해당 직원의 매출액을 기록해놓고, 그 하위 직원들은 배열이나 리스트를 이용하여 같은 클래스로 맞춰주면서 다이나믹 프로그래밍 기법을 이용하면 쉽게 풀 수 있습니다.

 

 

 

 

 

마치며...

여기까지 2021 카카오 신입 코딩테스트 문제 풀이를 진행해 봤습니다. 

 

특이한 문제도 한 문제 있었고, 무엇보다 최근 들어 알고리즘 문제 풀이를 꾸준히 안한 탓인지 평소보다 문제 풀이하는 데 난이도도 시간도 2~3배 정도 뺏긴 듯한 기분이었습니다. 좀 더 알고리즘에 대한 문제 풀이에 노력을 기울여야겠다는 생각이 들었습니다.

 

좋은 점이 있었다면 이번 알고리즘 문제 풀이에서 실생활에서 자주 사용하고 있는 문제들에 대한 해결 경험을 가질 수 있었다는 것에 만족을 했던 것 같습니다. 그 구현 과정이나 풀이가 생각보다 고통스러웠지만 개발자라는 직업을 하면서 평소 고민했던 문제들이나 사용하는 기능들에 대해 좀 더 탐구해보고 연구하는 기회가 생겼다는 점은 정말 좋았던 것 같네요.

 

앞으로도 계속 문제 풀이를 해볼 계획이지만 점점 문제의 난이도를 보며 한숨이 나오는 것은 왜 일까요? ㅠㅠ..

 

 

 

 

 

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

(https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/)