2020년 카카오의 여름 인턴십이 시작 되었습니다.

여름 인턴십의 첫번째 관문인 코딩 테스트가 2020년 5월 9일 오후 2시부터 6시까지 진행되었는데요, 온라인으로 진행되었기 때문에 코로나19로부터 안전하게 응시할 수 있었습니다.

코딩 테스트 항목은 점진적인 난이도 배치를 통해 지원자의 부담은 최소화하되 능력은 최대한 이끌어 낼 수 있도록 구성되었습니다. 기본적으로 모든 문제들은 정확성을 요구하기 때문에 정확성 TC를 통과하면 기본 점수를 얻게 되고, 특정 문제들은 효율성 TC가 추가되어 있으므로 기본 점수 외에 추가적인 점수를 얻을 수 있습니다.

효율성이란 단어를 접하면 살짝 두려운 느낌을 받을 수도 있었을 텐데요, 학교 수업 내용을 잘 되새겨보면 충분히 해결할 수 있는 것들로 구성하였으니, 효율성을 통과하면 본인이 더욱 만족감을 가질 수 있어 도전해 볼 가치가 있었을 것입니다.

각 문제에 대한 해설을 살펴보기 전에 문제를 풀어볼 수 있는 링크를 제공하니, 해설을 먼저 보기 전에 자신만의 방법으로 도전해 볼 것을 권해 드립니다. 문제를 해결하는 방법은 한가지만 있는 것이 아니기 때문입니다.

그럼 지금부터 문제에 대한 풀이 방법을 살펴보겠습니다.

문제 1

문제 1 풀러가기

스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다.

이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.

엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인지 오른손인지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해 주세요.

[제한사항]

numbers 배열의 크기는 1 이상 1,000 이하입니다.
numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.
hand는

  "left"

또는

  "right"

입니다.

"left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.
왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.

입출력 예

numbers	hand	result
[1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5]	`"right"`	`"LRLLLRLLRRL"`
[7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2]	`"left"`	`"LRLLRRLLLRR"`
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]	`"right"`	`"LLRLLRLLRL"`

입출력 예에 대한 설명

■ 입출력 예 #1

순서대로 눌러야 할 번호가 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5]이고, 오른손잡이입니다.

왼손 위치	오른손 위치	눌러야 할 숫자	사용한 손	설명
*	#	1	L	1은 왼손으로 누릅니다.
1	#	3	R	3은 오른손으로 누릅니다.
1	3	4	L	4는 왼손으로 누릅니다.
4	3	5	L	왼손 거리는 1, 오른손 거리는 2이므로 왼손으로 5를 누릅니다.
5	3	8	L	왼손 거리는 1, 오른손 거리는 3이므로 왼손으로 8을 누릅니다.
8	3	2	R	왼손 거리는 2, 오른손 거리는 1이므로 오른손으로 2를 누릅니다.
8	2	1	L	1은 왼손으로 누릅니다.
1	2	4	L	4는 왼손으로 누릅니다.
4	2	5	R	왼손 거리와 오른손 거리가 1로 같으므로, 오른손으로 5를 누릅니다.
4	5	9	R	9는 오른손으로 누릅니다.
4	9	5	L	왼손 거리는 1, 오른손 거리는 2이므로 왼손으로 5를 누릅니다.
5	9	-	-

따라서 "LRLLLRLLRRL"를 return 합니다.

■ 입출력 예 #2

왼손잡이가 [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2]를 순서대로 누르면 사용한 손은 "LRLLRRLLLRR"이 됩니다.

■ 입출력 예 #3

오른손잡이가 [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]를 순서대로 누르면 사용한 손은 "LLRLLRLLRL"이 됩니다.

문제 해설

문제의 조건을 확인하고 두 점 사이의 거리를 이용하여 구현하면 되는 문제입니다. 다음과 같이 2차원 배열 형태로 좌표를 미리 만들어 둔다면 숫자별로 눌러야 하는 위치를 간단히 알아낼 수 있습니다.

[[3,1],[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]

예를 들면 0은 (3, 1) 지점을 누르면 되며, 1은 (0,0) 위치를 누르면 된다는 의미입니다. 다음으로 숫자를 누를 때마다 다음과 같이 조건을 확인합니다.

1,4,7을 누를때는 왼손 엄지손가락 위치를 갱신합니다.
3,6,9를 누를때는 오른손 엄지손가락 위치를 갱신합니다.
2,5,8,0을 누를때는 왼손과 오른손중 더 가까운 손가락의 위치를 갱신합니다.
만약, 거리가 같다면 오른손 잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락 위치를 갱신합니다.

오른손 엄지손가락 위치를 (right_x, right_y), 다음으로 눌러야 하는 숫자의 위치를 (next_x, next_y)라고 할 때, 이동 거리는 다음과 같습니다.

|right_x - next_x| + |right_y - next_y|

왼손 엄지손가락 위치를 (left_x, left_y)라고 한다면, 마찬가지로 다음과 같이 이동거리를 구하면 됩니다.

|left_x - next_x| + |left_y - next_y|

이제 둘 중 더 가까운 손가락 위치를 갱신하면 되며 거리가 같은 경우에는 오른손잡이, 왼손잡이에 따라 위치를 갱신해 주면 됩니다.

문제 2

문제 2 풀러가기

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 같은 방식으로 결정하려고 합니다.

해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산 문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 '미션’은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다.

단, 연산자의 우선순위를 새로 정의할 때 같은 순위의 연산자는 없어야 합니다. 즉, + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,-처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다. 수식에 포함된 연산자가 2개라면 정의할 수 있는 연산자 우선순위 조합은 2! = 2가지이며, 연산자가 3개라면 3! = 6가지 조합이 가능합니다.

만약 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출하며 제출한 숫자가 가장 큰 참가자를 우승자로 선정하며, 우승자가 제출한 숫자를 우승상금으로 지급하게 됩니다.

예를 들어 참가자 중 네오가 아래와 같은 수식을 전달받았다고 가정합니다.

"100-200*300-500+20"

일반적으로 수학 및 전산학에서 약속된 연산자 우선순위에 따르면 더하기와 빼기는 서로 동등하며 곱하기는 더하기, 빼기에 비해 우선순위가 높아 * > +,- 로 우선순위가 정의되어 있습니다.

대회 규칙에 따라 + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,-처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.

수식에 연산자가 3개 주어졌으므로 가능한 연산자 우선순위 조합은 3! = 6가지이며, 그 중 + > - > * 로 연산자 우선순위를 정한다면 결괏값은 22,000원이 됩니다.
반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60,420 이지만, 규칙에 따라 우승 시 상금은 절댓값인 60,420원이 됩니다.

참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해 주세요.

[제한사항]

expression은 길이가 3 이상 100 이하인 문자열입니다.
expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(

  +, -, *

)만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.

즉, "402+-561*"처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.
expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
즉, "100-2145*458+12"처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
"-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.
연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 263 - 1 이하가 되도록 입력이 주어집니다.
같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.

입출력 예

expression	result
`"100-200*300-500+20"`	60420
`"506-32"`	300

입출력 예에 대한 설명

■ 입출력 예 #1

* > + > - 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.

100-200*300-500+20
= 100-(200*300)-500+20
= 100-60000-(500+20)
= (100-60000)-520
= (-59900-520)
= -60420

따라서, 우승 시 받을 수 있는 상금은 |-60420| = 60420 입니다.

■ 입출력 예 #2

- > * 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.(expression에서 + 연산자는 나타나지 않았으므로, 고려할 필요가 없습니다.)

50*6-3*2
= 50*(6-3)*2
= (50*3)*2
= 150*2
= 300

따라서, 우승 시 받을 수 있는 상금은 300입니다.

문제 해설

연산자의 종류가 최대 3개이므로 연산자 우선순위는 최대 6개까지 나올 수 있습니다. (3! = 6) 연산자 우선순위가 정해지면, 문자열의 앞에서부터 차례대로 우선순위가 빠른 연산자부터 찾아서 그 연산자와 양 옆의 숫자(피연산자) 2개를 제거하고 계산된 결괏값을 대입하는 과정을 반복하면 됩니다.

이때 미리 입력으로 주어진 문자열에서 숫자와 연산자를 분리하여 각각의 배열에 보관해 놓으면 보다 편하게 문제를 해결할 수 있습니다.

숫자에 대한 배열을 준비하고, 연산자에 대한 배열을 준비한 다음, 우선순위에 맞는 연산자의 인덱스를 연산자 배열에서 찾은 후 기억 합니다. 그 후 숫자 배열에서 해당 인덱스와 다음 인덱스를 계산하는 방식을 이용하면 됩니다.

문제 3

문제 3 풀러 가기

개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다. 어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다.

어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.
진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다.

진열대 번호	1	2	3	4	5	6	7	8
보석 이름	DIA	RUBY	RUBY	DIA	DIA	EMERALD	SAPPHIRE	DIA

진열대의 3번부터 7번까지 5개의 보석을 구매하면 모든 종류의 보석을 적어도 하나 이상씩 포함하게 됩니다. 진열대의 3, 4, 6, 7번의 보석만 구매하는 것은 중간에 특정 구간(5번)이 빠지게 되므로 어피치의 쇼핑 습관에 맞지 않습니다.

진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.

가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

[제한사항]

gems 배열의 크기는 1 이상 100,000 이하입니다.
gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.

입출력 예

gems	result
`["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]`	[3, 7]
`["AA", "AB", "AC", "AA", "AC"]`	[1, 3]
`["XYZ", "XYZ", "XYZ"]`	[1, 1]
`["ZZZ", "YYY", "NNNN", "YYY", "BBB"]`	[1, 5]

입출력 예에 대한 설명

■ 입출력 예 #1
문제 예시와 같습니다.

■ 입출력 예 #2
3종류의 보석(AA, AB, AC)을 모두 포함하는 가장 짧은 구간은 [1, 3], [2, 4]가 있습니다.
시작 진열대 번호가 더 작은 [1, 3]을 return 해주어야 합니다.

■ 입출력 예 #3
1종류의 보석(XYZ)을 포함하는 가장 짧은 구간은 [1, 1], [2, 2], [3, 3]이 있습니다.
시작 진열대 번호가 가장 작은 [1, 1]을 return 해주어야 합니다.

■ 입출력 예 #4
4종류의 보석(ZZZ, YYY, NNNN, BBB)을 모두 포함하는 구간은 [1, 5]가 유일합니다.
그러므로 [1, 5]를 return 해주어야 합니다.

문제 해설

맵 자료구조에서, 'map[보석 이름] = 빈도수’로 정의를 합니다.
왼쪽 포인터 l과 오른쪽 포인터 r을 모두 1번 진열대에 위치시킵니다.
양 포인터 중, 둘 중 하나라도 진열대의 범위를 벗어나면 알고리즘을 종료합니다.
양 포인터가 가리키는 범위 안에 포함된 보석 종류의 개수를 세어 봅니다.(map의 사이즈를 체크합니다)
5-1. 범위 안에 보석 종류가 전체 보석 종류와 일치하면 더 좋은 답인지 체크한 후 l를 증가시킵니다. 그리고 2로 갑니다.
5-2. 범위 안에 보석 종류가 전체 보석 종류보다 작다면 r를 증가시킵니다. 그리고 3으로 갑니다.

즉, 왼쪽을 가리키는 포인터 l과 오른쪽을 가리키는 포인터 r을 이용하여 보석의 종류가 모자라면 r을 증가시키고, 보석의 종류가 충분하면 l을 증가시키는 과정을 반복하면서, 정답을 갱신시켜나갑니다. 이때 l을 증가시키기 이전, map자료구조에서 l번 진열대에 있던 보석의 빈도수를 감소시켜주어야 하며 특히 빈도수가 1에서 0이 될 때에는 map에서 완전히 제거하여야 합니다. r을 증가시킬 때는 map자료구조에서 증가된 r번 진열대에 있는 보석의 빈도수를 증가시켜줍니다.

문제 4

문제 4 풀러가기

건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다. 제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다. 설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다.

경주로의 출발점은 (0, 0) 칸(좌측 상단)이며, 도착점은 (N-1, N-1) 칸(우측 하단)입니다. 죠르디는 출발점인 (0, 0) 칸에서 출발한 자동차가 도착점인 (N-1, N-1) 칸까지 무사히 도달할 수 있게 중간에 끊기지 않도록 경주로를 건설해야 합니다. 경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있으며, 벽이 있는 칸에는 경주로를 건설할 수 없습니다.

이때, 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로 라고 합니다.
또한 두 직선 도로가 서로 직각으로 만나는 지점을 코너 라고 부릅니다.
건설 비용을 계산해 보니 직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500원이 추가로 듭니다. 죠르디는 견적서 작성을 위해 경주로를 건설하는 데 필요한 최소 비용을 계산해야 합니다.

예를 들어 아래 그림은 직선 도로 6개와 코너 4개로 구성된 임의의 경주로 예시이며, 건설 비용은 6 x 100 + 4 x 500 = 2600원 입니다.

또 다른 예로, 아래 그림은 직선 도로 4개와 코너 1개로 구성된 경주로이며, 건설 비용은 4 x 100 + 1 x 500 = 900원 입니다.

도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board가 매개변수로 주어질 때, 경주로를 건설하는데 필요한 최소 비용을 return 하도록 solution 함수를 완성해주세요.

[제한사항]

board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
board 배열의 각 원소의 값은 0 또는 1 입니다.
도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1) 입니다.
원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.

입출력 예

board	result
[[0,0,0],[0,0,0],[0,0,0]]	900
[[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]]	3800
[[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]]	2100
[[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[0,1,0,0,0,1],[0,0,0,0,0,0]]	3200

입출력 예에 대한 설명

■ 입출력 예 #1

본문의 예시와 같습니다.

■ 입출력 예 #2

위와 같이 경주로를 건설하면 직선 도로 18개, 코너 4개로 총 3800원이 듭니다.

■ 입출력 예 #3

위와 같이 경주로를 건설하면 직선 도로 6개, 코너 3개로 총 2100원이 듭니다.

■ 입출력 예 #4

붉은색 경로와 같이 경주로를 건설하면 직선 도로 12개, 코너 4개로 총 3200원이 듭니다.
만약, 파란색 경로와 같이 경주로를 건설한다면 직선 도로 10개, 코너 5개로 총 3500원이 들며, 더 많은 비용이 듭니다.

문제 해설

최단 경로를 구하기 위해 BFS를 이용하여 살펴 보겠습니다. 먼저 출발지 → 도착지로 이동하는 [코너가 1개인 경로, 코너가 2개인 경로, 코너가 3개인 경로, …, 코너가 K개인 경로] 중 가장 적은 비용이 드는 경로를 찾습니다. 예를 들어 예제 1번 [[0,0,0],[0,0,0],[0,0,0]]의 경우 코너가 1개이면서 가장 적은 비용이 드는 경로는 다음과 같이 2 가지입니다.

(0,0) → (0,1) → (0,2) → (1,2) → (2,2)
(0,0) → (1,0) → (2,0) → (2,1) → (2,2)

코너가 2개이면서 가장 적은 비용이 드는 경로 중 하나는 다음과 같습니다.

(0,0) → (0,1) → (1,1) → (2,1) → (2,2)

이 외에도 다양한 경로가 있으며, 코너가 K개일 때 가장 적은 비용이 들려면 직선 도로 개수를 최대한 줄이면 됩니다. 이는 코너를 K개 만들면서 출발지에서 도착지까지 가는 최단 경로를 찾으면 됩니다.

이제 다음과 같이 상태 공간 S를 정의합니다.

S = [세로 좌표 R][가로 좌표 C][코너 개수 K][바라보는 방향 D] → 코너 K개를 만들면서 (R, C) 위치에 도착했고, D방향을 바라보고 있을 때의 최단 거리

이때 한 칸 이동하는데 드는 비용은 1, 코너를 하나 만드는 비용도 1이라고 가정합니다. 이제 출발지 → 도착지로 이동하는 최단 경로를 모든 K에 대해서 찾아줍니다. BFS 탐색 코드는 다음과 같이 작성합니다.

마지막으로 바라본 방향을 기준으로 왼쪽 회전, 오른쪽 회전, 직진 하는 3가지 경우에 대해 탐색합니다.
왼쪽 회전, 오른쪽 회전의 경우 코너를 하나 추가하고, 바라보는 방향을 바꿔줍니다.
직진의 경우 바라보는 방향으로 1칸 전진합니다.

위와 같이 BFS 탐색을 한 후, 마지막으로 (N - 1, N - 1) 위치에서 K = 1, 2, 3, … 인 경우에 대해 최단 거리를 찾아주면 됩니다. 이때, 주의 할 점은 여기서 구한 최단 거리는 코너 개수가 포함된 값이라는 것입니다. 따라서 코너가 K개인 최단 거리에서 건설 비용은 다음과 같이 계산하면 됩니다.

(최단 거리 - K) x 100 + K * 500

그렇다면 여기서 K값은 얼마나 커질 수 있을까요? 각 격자칸 하나에는 코너가 최대 1개 생길 수 있습니다. 그렇다면 N x N 크기 격자에서 코너 개수는 격자칸 개수보다는 작아야 합니다. 따라서 코너 개수 K는 최대 N x N이면 됩니다.

문제 5

문제 5 풀러가기

오지 탐험가인 프로도는 탐험 도중 n개의 방으로 이루어진 지하 동굴을 탐험하게 되었습니다. 모든 방에는 0부터 n - 1 까지 번호가 붙어있고, 이 동굴에 들어갈 수 있는 유일한 입구는 0번 방과 연결되어 있습니다. 각 방들은 양방향으로 통행이 가능한 통로로 서로 연결되어 있는데, 서로 다른 두 방을 직접 연결하는 통로는 오직 하나입니다. 임의의 서로 다른 두 방 사이의 최단경로는 딱 한 가지만 있으며, 또한 임의의 두 방 사이에 이동이 불가능한 경우는 없습니다.

탐험에 앞서 이 지하 동굴의 지도를 손에 넣은 프로도는 다음과 같이 탐험 계획을 세웠습니다.

모든 방을 적어도 한 번은 방문해야 합니다.
특정 방은 방문하기 전에 반드시 먼저 방문할 방이 정해져 있습니다.
2-1. 이는 A번 방은 방문하기 전에 반드시 B번 방을 먼저 방문해야 한다는 의미입니다.
2-2. 어떤 방을 방문하기 위해 반드시 먼저 방문해야 하는 방은 없거나 또는 1개 입니다.
2-3. 서로 다른 두 개 이상의 방에 대해 먼저 방문해야 하는 방이 같은 경우는 없습니다.
2-4. 어떤 방이 먼저 방문해야 하는 방이면서 동시에 나중에 방문해야 되는 방인 경우는 없습니다.

위 계획 중 2-2, 2-3, 2-4는 순서를 지켜 방문해야 하는 두 방의 쌍이 A → B(A를 먼저 방문하고 B를 방문함) 형태로 유일함을 의미합니다. 즉, 프로도는 아래와 같은 형태로 방문순서가 잡히지 않도록 방문 계획을 세웠습니다.

A → B, A → C (방문순서 배열 order = […,[A,B],…,[A,C],…]) 형태로 A를 방문 후에 방문해야 할 방이 B와 C로 두 개 또는 그 이상인 경우
X → A, Z → A (방문순서 배열 order = […,[X,A],…,[Z,A],…]) 형태로 A를 방문하기 전에 방문해야 할 방이 X와 Z로 두 개 또는 그 이상인 경우
A → B → C (방문순서 배열 order = […,[A,B],…,[B,C],…) 형태로 B처럼 A 방문 후이면서 동시에 C 방문 전인 경우

그리고 먼저 방문해야 할 방과 나중에 방문할 방을 반드시 연속해서 방문해야 할 필요는 없어 A방을 방문한 후 다른 방을 방문한 후 B방을 방문해도 좋습니다.

방 개수 n, 동굴의 각 통로들이 연결하는 두 방의 번호가 담긴 2차원 배열 path, 프로도가 정한 방문 순서가 담긴 2차원 배열 order가 매개변수로 주어질 때, 프로도가 규칙에 맞게 모든 방을 탐험할 수 있을 지 return 하도록 solution 함수를 완성해주세요.

[제한사항]

n은 2 이상 200,000 이하입니다.
path 배열의 세로(행) 길이는 n - 1 입니다.
path 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.
두 방 A, B사이를 연결하는 통로를 나타냅니다.
통로가 연결하는 두 방 번호가 순서없이 들어있음에 주의하세요.
order 배열의 세로(행) 길이는 1 이상 (n / 2) 이하입니다.
order 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.
A번 방을 먼저 방문한 후 B번 방을 방문해야 함을 나타냅니다.

입출력 예

n	path	order	result
9	[[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]]	[[8,5],[6,7],[4,1]]	true
9	[[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]]	[[4,1],[5,2]]	true
9	[[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]]	[[4,1],[8,7],[6,5]]	false

입출력 예에 대한 설명

■ 입출력 예 #1

동굴 그림은 아래와 같습니다.

방문 순서를 지켜야 하는 방 번호는 다음과 같습니다.

6번 → 7번
4번 → 1번
8번 → 5번

따라서 모든 방을 방문할 수 있는 방법 중 하나는 다음과 같습니다.

0번 → 3번 → 6번 → 3번 → 0번 → 7번 → 4번 → 7번 → 0번 → 1번 → 8번 → 1번 → 2번 → 1번 → 0번 → 7번 → 5번

■ 입출력 예 #2

다음 순서로 각 방을 방문하면 됩니다.

0번 → 7번 → 4번 → 7번 → 5번 → 7번 → 0번 → 3번 → 6번 → 3번 → 0번 → 1번 → 8번 → 1번 → 2번

■ 입출력 예 #3

규칙에 맞게 모든 방을 방문할 수 있는 방법이 없습니다.

문제 해설

먼저 예시 테스트 케이스 1번 그림을 살펴보면 다음과 같습니다.

여기서 5번 노드를 방문하기 위해 반드시 먼저 방문해야 하는 노드를 화살표로 표시했습니다. 예를 들면 5번 노드를 방문하기 위해서는 7번 노드를 반드시 먼저 방문해야 하며, 7번 노드를 방문하기 위해서는 6번 노드를 반드시 먼저 방문해야 합니다. 따라서 6번 노드는 5번 노드를 방문하기 전에 반드시 먼저 방문해야 하는 노드입니다. 이와 비슷한 방식으로 2번 노드를 제외한 나머지 노드들 또한 5번 노드를 방문하기 전에 반드시 먼저 방문해야 하는 노드입니다.

물론 5번 노드 뿐 아니라 모든 노드에 대해서 이런식으로 반드시 먼저 방문해야 하는 노드를 표시할 수 있습니다. 이를 조금더 일반적으로 표현하면 아래 그림과 같습니다.

위 그림은 루트노드 A에서 리프노드 D까지 최단 경로로 이동할 때 방문하는 노드들을 나타내고 있습니다. A - B 노드 사이의 (…) 은 중간에 방문하는 다른 노드들을 표현한 부분입니다. 위 그림에서 D 노드를 방문하기 위해 반드시 먼저 방문해야 하는 노드들을 화살표로 표시했습니다. 예를 들어 D를 방문하려면 반드시 C, B, … , A노드를 먼저 방문 해야만 합니다. 이는 문제에 주어진 order 배열과 관계 없이, D노드를 방문하려면 반드시 거쳐가야하는 노드들입니다.

이제 C 노드에 대해서 살펴보면 C 노드를 방문하기 위해서는 B, …, A 노드를 반드시 방문해야 합니다. 이때, C가 반드시 방문해야 하는 노드는 C 자기 자신을 제외하면 D가 반드시 방문해야 되는 노드와 중복됩니다.

따라서 위와 같이 반드시 먼저 방문해야 되는 노드 중에서 중복되는 부분을 제거할 수 있으며, 다음과 같이 정리할 수 있습니다.

노드 X를 방문하기 위해 반드시 먼저 방문해야 되는 노드 = 노드 X의 부모 노드를 방문하기 위해 반드시 먼저 방문해야 하는 노드 + 노드 X의 부모노드

즉, 위 그림과 같이 노드 D를 방문하기 위해서는 반드시 노드 C를 먼저 방문한다고만 하면 되며 나머지 부분은 노드 C에 맡겨도 된다는 의미입니다.

이제 order배열에 대해서도 살펴보면 위와 마찬가지로 단순히 특정 노드를 방문하기 전에 반드시 먼저 방문해야 되는 노드에 대한 정보만 입력해주면 됩니다. 이를 예시 1번에 그림으로 표현해보면 다음과 같습니다.

5번 노드에 대해서 살펴보면 처음 그림과 다르게 단순히 “7번, 8번 노드를 반드시 먼저 방문해야 한다” 라고 표현해주고 있습니다. 7번, 8번 노드를 방문하기 위해 반드시 먼저 방문해야 하는 노드들을 따라가보면 0번, 3번, 4번, 6번 노드들을 반드시 먼저 방문해야 함을 쉽게 알 수 있습니다. 마찬가지로 1번, 7번 노드에 대해서도 부모노드를 반드시 먼저 방문해야 하며, 각각 4번, 6번 노드를 반드시 먼저 방문해야 한다고 표시하고 있습니다.

이제 어떤 노드 X에서 출발해 반드시 먼저 방문해야 하는 노드를 순서대로 따라가다 보니 다시 자기 자신 노드 X가 나오는 경우 규칙에 맞게 모든 방을 탐험하는것이 불가능하다는 사실을 쉽게 알 수 있습니다. 이는 자기 자신을 방문하기 위해 반드시 자기 자신을 먼저 방문해야 한다는 의미이며, 해당 노드에 진입하는 것이 불가능함을 나타내기 때문입니다. 따라서 위와 같이 방향그래프를 만들고, 그래프에 사이클(cycle)이 없는지 확인하면 됩니다.

마치며

지금까지 2020 카카오 여름 인턴십 코딩 테스트의 모든 문제에 대한 해설을 살펴보았습니다. 생각했던 해결법과 비슷할 수도 혹은 더 나은 방법을 생각하신 분들도 있었을 것입니다. 혹시 어렵게 느껴졌다면 이번 코딩 테스트를 통해 더 발전할 수 있는 계기가 되셨으면 좋겠습니다.

문제를 해결하는 방법은 한 가지만 있는 것이 아니므로 해설을 통해 암기를 하기보단 사용된 알고리즘이 무엇이고 왜/언제 사용했는지 되뇌는 시간이 되셨기를 바랍니다. 또한 테크블로그의 다른 문제들도 살펴보면 어느 순간 점점 더 발전되어 있는 자신을 발견할 수 있을 것입니다.

2020년 카카오에서는 하반기에 한 번 더 신입 개발자 공개채용이 있을 예정입니다. 입사를 희망하신다면 도전하시길 바랍니다. 조급해 하지 말고 차근히 준비하시면 좋은 결과를 얻으실 수 있을 것입니다.

코로나19가 좀처럼 종식되지 않고 있습니다. 항상 건강에 유의하시고 카카오에서 뵙기를 희망하겠습니다

2020 카카오 인턴십 for Tech developers 문제해설