프로그래머스 2022 데브매칭 웹 백엔드 개발자(상반기) 코딩 테스트 후기 & 접근방법

2022.04.02에 진행된 프로그래머스 데브매칭 코딩 테스트 후기와 풀이

코테 후기

2시간에 4문제 (알고리즘 3, SQL 1) 라기에 시간이 빡빡하다고 느껴졌는데, SQL은 생각보다 너무 간단하게 나와서 5분도 걸리지 않았고 사실상 나머지 3개의 구현 문제가 핵심이었던 듯.

특정 대회용 알고리즘을 알아야만 풀 수 있는 애드혹 문제가 없었던 것은 매우 좋았던 것 같다. 기본적인 알고리즘 이해와 약간의 구현 실력을 테스트하는 듯.

짧은 시간을 고려하더라도 난이도 자체는 매우 쉬워서 한시간 가까이 남았다 … 프로그래머스 레벨 3, 백준 골드 3 정도를 무난히 풀 실력이면 충분히 올솔 가능할 것 같다.

코테 풀이 (Python, MySQL)

아직 문제가 프로그래머스 문제집에 공개되지 않은 상태라 문제 개요, 대략적인 난이도(백준 기준)와 함께 문제 접근 방법을 공유함

1번

체감 난이도 : 골드 4 (BOJ 기준)

문제

1차원 직선좌표 위의 점들 간 거리가 주어졌을 때, 놓일 수 있는 방법(순서) 의 개수 구하기

접근

요구하는 답은 좌표가 아닌 순서(permutation)의 개수임. 따라서 한 점을 기준으로 잡고 다른 점들을 ‘이미 놓인 점과의 거리가 주어진 조건을 만족하도록’ 놓으며 전수조사를 하면 됨

단순하게는 0번 점을 직선좌표계 상의 0 위치로 정해두고, N번 점에 대해서 0~N-1번 점까지의 거리가 주어진 조건에 부합하도록 배치.

다만 문제에서 제시한 조건 중, 점의 위치의 범위는 매우 넓기 때문에 점을 놓을 때 좌표값 자체를 배열의 인덱스로 사용하면 탐색 도중 시간초과가 나옴.

점의 개수 N이 매우 작기 때문에 모든 점을 하나의 리스트 내에 보관하여 시간복잡도 O(N^2) 로 해결하더라도 충분함.

코드

문제가 프로그래머스의 문제집에 추가되고 나면 업로드 예정

2번

체감 난이도 : 골드 3 (BOJ 기준)

문제

‘a’, ‘b’, ‘c’, ‘?’ 로 이루어진 2차원 보드에서, ‘?’ 대신 ‘a’, ‘b’, ‘c’를 추가해서 모든 ‘a’, ‘b’, ‘c’가 각각 같은 알파벳끼리 모두 인접해 있는 경우의 수 구하기

접근

모든 경우의 수는 당연히 전수조사 해야 함.

나의 경우는 입력을 받을 때 ‘a’, ‘b’, ‘c’, ‘?’ 를 1, 2, 3, 0 으로 치환했음.

코딩 테스트에서 파이썬이 정말 유리하다고 생각하는 이유 중 하나는 굉장히 강력한 라이브러리인데, itertools.product 를 이용하면 0 대신 1,2,3이 들어가는 경우의 수를 모두 구할 수 있다.

1 2 3 4 5 6

import itertools combinations = list(itertools.product([1, 2, 3], repeat=9)) print(combinations) print(len(combinations))

1 2	>> [(1, 1, 1, 1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 1, 1, 1, 2), (1, 1, 1, 1, 1, 1, 1, 1, 3), (1, 1, 1, 1, 1, 1, 1, 2, 1), (1, 1, 1, 1, 1, 1, 1, 2, 2), (1, 1, 1, 1, 1, 1, 1, 2, 3), (1, 1, 1, 1, 1, 1, 1, 3, 1), (1, 1, 1, 1, 1, 1, 1, 3, 2), (1, 1, 1, 1, 1, 1, 1, 3, 3) ... >> 19683

문제 조건에서 ‘?’의 개수가 최대 9개로 주어졌던 것으로 기억하는데, 스트레스 케이스의 완전탐색 시에도 20000번 이하로 시도하면 되는 것을 알 수 있다.

이제 위 combinations 리스트의 각 항목을 ‘보드의 0 자리에 들어갈 숫자(1, 2, 3) 목록’으로 해석해서 새로운 보드를 생성하고, 아무 1, 2, 3 숫자 하나에 대해 DFS를 이용해서 인접한 같은 수를 탐색하며 방문한 노드를 체크해주면 문제 조건을 만족하는 보드와 그렇지 못한 보드를 가려낼 수 있게 된다.

코드

문제가 프로그래머스의 문제집에 추가되고 나면 업로드 예정

3번

체감 난이도 : 골드 3 (BOJ 기준)

문제

가중치가 없는 그래프가 주어지고 출발지와 도착지가 주어졌을 때, 특정 횟수(K) 이하의 움직임 내에 출발지에서 도착지까지 도달하는 경로의 목록에 ‘한 번도 포함되지 않은’ 경로의 개수 구하기

접근

문제를 분할해서 생각할 필요가 있음.

출발지에서 DFS로 K 번 이내에 도착하는 경로를 구하고, 그 과정에서 경로가 완성될 때마다 경로에 포함된 노드를 체크해주면 끝.

코드

문제가 프로그래머스의 문제집에 추가되고 나면 업로드 예정

4

체감 난이도 : 레벨 3 (프로그래머스 기준)

문제

장바구니에 담긴 물건 테이블, 쿠폰 사용 내역 테이블이 다음 형태로 주어짐.

장바구니에 담긴 물건 테이블

• id
• 장바구니 id
• 물건
• 가격

쿠폰 사용 내역 테이블

• id
• 장바구니 id
• 최소 사용 가능 금액

이 상황에서 ‘최소 사용 가능 금액’을 넘기지 못했는데 사용된 쿠폰의 목록 구하기

접근

우선 가지고 있는 ‘장바구니에 담긴 물건 테이블’ 은 그 자체로 쓸모가 전혀 없고, 이를 장바구니 단위로 금액이 합산된 테이블로 바꿔야 함.

GROUP BY를 통해 바꿔준 뒤 이를 서브쿼리로 활용하고 ‘쿠폰 사용 내역 테이블’과 장바구니 id를 key로 JOIN한 뒤, 가격의 합이 최소 사용 가능 금액보다 적은 경우를 출력하면 끝.

코드

문제가 프로그래머스의 문제집에 추가되고 나면 업로드 예정