2023 토스 넥스트 챌린지 Server 직군 코딩테스트 후기

2023 토스 넥스트 챌린지 코딩테스트가 07/08 14:00 - 16:20에 진행되었다.
 
늘 재밌는 서술형 문제라서 즐겁게 응시했다.
다만, 이제 회사 다니는 입장에서 남의 자리 빼앗긴 좀 그래서... 코드 다 빼고 제출했다.
스스로 푼 풀이라 실제 정답과 다를 수 있다는 것에 주의...
 
Q1
사용된 알고리즘: 구현
예상 난이도 (Solved.ac 기준): S5
 
반복문 돌리면 끝나는데, 약간의 추가 구현이 필요하다.
(숫자가 다 있는지 확인해야 하니까.)
그런데, 파이썬 기준으로는 그냥 (자른 문자열을 정렬한 결과) == (range(1, N + 1)을 합친 결과) 로 비교하면 한방에 끝난다.
구현 짧게 하고 건강 찾자...
 
Q2
사용된 알고리즘: 그래프 탐색
예상 난이도 (Solved.ac 기준): S2
 
최단 거리 구하면 끝난다...
최단거리가 1이면 5 더하고, 2 이상 limit 이하이면 10 더하고 카운트 하면 된다.
이외의 이슈는 그냥 구현 문제라 큰 이슈는 없는듯
 
Q3
사용된 알고리즘: 정렬, 문자열
예상 난이도 (Solved.ac 기준): G4
 
이게 뭐야? 싶을텐데, 차근차근 접근하면 풀린다.
- 어차피 문자열은 맨 끝만 제거되거나, 특수문자만 제거된다.
- 따라서, 같은 문자열들을 모두 묶어주면 일차적으로 해결된다.
- 맨 끝만 제거되니 문자열을 정렬하게 되면 어차피 비슷비슷한 문자열은 한 덩어리에 몰린다.
- 그렇게 되면, 반복문으로 문자열을 탐색하면서 같은 그룹인지 확인한다. (공백과 특수문자를 제거하면 같은 문자열인지 쉽게 판단할 수 있다.)
- 이렇게 그룹을 묶어주면, 각 그룹에서 대표 문자열을 선택할 수 있다.
- 각 그룹의 대표문자열은, (길이) -> (특수문자 존재여부) -> (먼저 들어온 순서)로 찾을 수 있다.
- 먼저 들어온 순서는 미리 Hash로 기록해두자.
 
3번에 있을 문제가 아닌데 말이지...
 
Q4
사용된 알고리즘: 구현 + 잔꾀 (?)
예상 난이도 (Solved.ac 기준): G5
 
구현 자체는 쉽다.하지만 최근 방문한 페이지 목록을 구하는게 다소 어려울 것이라 생각한다.
 
그런데 문제를 잘 읽어보면... 이전에 방문한 페이지를 다시 방문하게 되면 목록에서 빼고 다시 넣는데, 이건 너무 구현이 복잡하고 비효율적이기도 하다.
그러니, 빼지 말고 넣자!
그리고 마지막에 최대 maxPage 개만큼의 데이터를 뽑을 때, set을 사용해서 이전에 넣은 값을 안 넣는 방식으로 퉁치면 끝난다.
오히려 정직하게 구현하려면 피보는 문제
 
Q5
사용된 알고리즘: 그리디 + 부분합
예상 난이도 (Solved.ac 기준): G4
 
사실 바로 떠오른 풀이가 이거고, 완탐으로 뚫리는지를 몰라서 그냥 이걸로 적는다.
비슷한 그리디 문제를 풀어봤으면, 실제로 데이터가 존재하는 곳을 시작점으로 해서 스캔하면 된다.
다만 사각형이 직사각형이니 이걸 가로로 한 번, 세로로 한 번 스캔해서 거기 안에서 초콜릿이 몇 개 포함되어 있는지 세면 된다.
 
문제는... 이걸 세는데에서 시간 효율 문제가 발생할 수 있을 것이라는 생각이 들었다.
그런데 어차피 1000 * 1000 칸이니, 이걸 기반으로 각 칸에 몇 개의 초콜릿이 있는지 셀 수 있다면, 우린 이걸 2차원 부분합 테이블을 세워서 해결할 수 있다.
따라서 현재 초콜릿의 개수를 미리 세고 이걸 기반으로 부분합 테이블을 설계한 다음에, 그리디하게 각 칸을 기준으로 개수를 세면 된다.
 
Q6
사용된 알고리즘: 부분합
예상 난이도 (Solved.ac 기준): G4
 
풀다가 박수친 (?) 문제.
완탐으로 풀까 했는데, 효율성이 있길래 이건 다른 방법으로 풀어야 할 것 같아서 방법을 바꿨다.
잘 생각해보면, 어차피 이후 k일 동안은 딱 1개씩만 매도한다.
그렇다면, 매도해서 버는 금액의 총합은 길이가 k인 부분 수열의 합이라고 할 수 있다.
그리고, 너무나도 당연히 매수하는 금액은 해당 날짜의 금액 * k 이다.
맞다. 이건 그냥 부분합 배열 만들어서 밀어버리면 원큐에 끝나는 문제이다.
 
길이가 짧아서 간과했기에, 풀이를 떠올리고 박수를 쳤다.

(근데 사실 완탐으로 뚫린다고 한다.... 뭐지?)
 
Q7
사용된 알고리즘: DP
예상 난이도 (Solved.ac 기준): G5
 
작년에도 DP인데, 올해도 DP가 나왔다.
결국 그냥 연속적인거 선택 못 할 때 정수의 합의 최댓값을 구하는 문제이기 때문에 간단한 DP로 치환된다.
 
기존 선택 여부와 현재 위치만 갖고 있으면 되기 때문에, 큰 문제 없이 2차원 DP 테이블을 설계할 수 있고, 간단하게 밀어주면 된다.

오히려 앞 문제가 더 어려웠다는 생각이...
 
<2교시 8 ~ 12번>
대놓고 ChatGPT 엿먹이는 문제가 나왔다. 만세!
요즘 멘토링 해주는 분들에게 계속해서 CS를 활용한 시스템 설계의 중요성을 강조했는데, 마침 연습한거랑 비슷하게 (하지만 훨씬 더 어렵게... ㅠㅠ) 나왔기에 스스로 만족한다.
 
<총평>
- 작년엔 1시간 30분동안 열심히 풀면 7솔 나오게 만들었지만, 이번엔 어림도 없게 나왔네?