2022 하반기 신입 LINER 공개채용 코딩테스트 후기

2022 라인 신입 공채 코딩테스트가 09/24 10:00 - 12:30에 진행되었다.

7시간 30분 코테라니 이게 무슨 소리요
스스로 푼 풀이라 실제 정답과 다를 수 있다는 것에 유의...

Q1
사용된 알고리즘: 단순 구현
예상 난이도 (Solved.ac 기준): S5

하라는 대로 그대로 하면 된다.
size 배열과 현재 값의 수를 담는 cnt 배열을 만들어서 관리하면 쉽게 뚝딱 가능.

Q2
사용된 알고리즘: 재귀함수
예상 난이도 (Solved.ac 기준): S2 - S1
.이 올때, 몇 글자를 처리할지 감이 안 올 수 있으니, 재귀함수를 정의하자.bool is_correct(int k, string a, string b, int a_idx, int b_idx) 꼴의 함수를 만들어서,b[b_idx] 가 .이라면 a에 대해 1~k 글자를 처리하는 재귀함수를 호출해버리는 식으로 짜면 쉽게 끝낼 수 있다.

함수의 구조를 너무 자세히 말하면 사실상 문제를 말하는 꼴이니 말하긴 어렵지만,실제로 하는건- .이 올때 위에서 언급한 대로 처리하기- .이 아니라면 그냥 두 글자 비교하기- 만약에 a_idx와 b_idx가 두 문자열의 정확한 끝 지점을 가리키고 있다면 true 반환처럼 처리하면 된다.

Q3
사용된 알고리즘: 그래프 탐색
예상 난이도 (Solved.ac 기준): G3

어떤 칸과 불꽃/얼음이 있다고 할 때, 이 칸이 불꽃과 얼음의 영향을 어떤 경우에 받을 수 있을까?
(dx: 어떤 칸의 x 좌표와 불꽃의 x 좌표의 차이의 절댓값, dy: 똑같은데 y)

- 불꽃: dx와 dy 중 최댓값이 k 이내인 경우
- 얼음: (dx + dy) 값이 k 이내인 경우

못 믿겠으면 직접 그려보자!

m이 엄청 크다는 점에 주의하자. 즉, 이걸 기준으로 반복문을 돌리면 망한다.
칸의 수가 그렇게 많지 않기 때문에, 각 칸에 대해서 일괄적으로 계산을 돌리고 더하는 방식으로 대응해야 한다.


Q4
사용된 알고리즘: 빡 구현, BFS
예상 난이도 (Solved.ac 기준): G3

BFS로 접근하면 되는 문제인데, 구현해야 할 양이 많다.
그런데 잘 살펴보면 대각선이나 왼쪽/오른쪽으로 2-3칸 이동하는 것은 각각 하나의 반복문으로 묶어서 처리할 수 있다.
그렇게 하면 코드의 길이를 효과적으로 줄일 수 있다.

여기에, 빡구현 과정에서 일일이 경곗값을 넘어갔는지 체크해야 한다면 정말 구현 과정에서 실수가 많이 날 수 있다!
그런데 잘 살펴보면, 막힌 칸이 존재하면 아무것도 못 하고 그냥 탐색을 포기하는 것을 볼 수 있는데, 이를 이용하면 이 문제를 쉽게 해결할 수 있다.
예를 들어, 3*3의 보드가 주어졌다면,
XXXXX
X???X
X???X
X???X
XXXXX

와 같이 칸을 둘러싸는 경계를 만들고, 이를 싹다 막힌 칸으로 채워버리면 된다!

두 방법을 잘 사용하면, 귀찮긴 해도 다소 어렵지 않게 해결할 수 있다.

Q5
사용된 알고리즘: 수학, 이진탐색
예상 난이도 (Solved.ac 기준): G1?

사실 이 풀이는 그냥 내가 오버킬한 것 같다.
그래도 일단 적어보겠다.

결국 요금이 될 수 있는 후보는 요금이 변화하는 값의 "공약수" 라고 할 수 있다.
예를 들어, 주어진 데이터에서 대충 1000원 씩 올라가는 것 같다면, 실제로는 1, 2, 5, 10, ... 원이 모두 후보가 될 수 있다.
그렇다면, 간격은 어떻게 측정할 수 있을까?

간격도 브루트포스로 확인하게 되면, 뭔가 터질 것 같다는 생각이 들었다.
따라서, 다음과 같은 방법으로 접근했다.

1. 이진탐색을 사용했다.
2. lower_bound, upper_bound 를 계산하는 방법을 사용하여, 가능한 시간 구간의 최소 및 최대를 구하려고 시도했다.
3. 이진탐색의 대상은 시간 간격이고, 우리는 앞에서 후보로 정한 요금 간격이 있을텐데, 시간 간격으로 얻을 수 있는 현재 칸의 가중치와, 요금 간격을 통해 얻을 수 있는 현재 칸의 가중치를 비교하여 같다면 넘어가고, 같지 않다면 시간 간격을 줄일지/늘릴지를 확인하여 left, right 값을 조정했다.
4. lower_bound, upper_bound 를 모두 구했다면, 이 값을 기반으로 최솟값 최댓값을 갱신 시도한다.
5. 당연하겠지만, 값이 갱신 안 되었으면 -1 던져주면 끝.

많이 어려웠다...

<총평>
칼을 갈고 나왔나? 생각보다 많이 어려웠다.
시간도 줄었는데, 문제 난이도는 지난번 보다 어려운 느낌.