상반기 데브매칭을 응시하면서 얻은 경험을 아래와 같이 기록합니다.
응시 기간은 2022.07.03 (일) 10:00 - 12:00 였으며, 2시간 내 4문제 (알고리즘 3, SQL 1) 를 해결해야 한다.
올해 상반기 1차 데브매칭 때는 1문제 해결하였고, 지난 번 nhn 게임개발자 챌린지에서는 2문제를 해결했었는데 모두 탈락을 경험하였어서 이번에는 최소 3문제를 해결하는 것을 목표로 응시하였다.
결과적으로는 4문제 모두 해결하였으며, SQL 이 생각보다 까다로워서 고생을 했었습니다.
문제 내용은 정확히 기억나지 않아, 각 문제 별로 코드를 살펴보면서 문제를 유추하면서 설명하는 점 양해 부탁 드립니다.
1번 문제
1번 문제 코드는 아래와 같은데, 특정 배열이 주어지고 특정 배열 왼쪽이 작은값, 오른쪽이 큰값을 유지하기 위한 최소 비용을 구하는 문제라고 할 수 있다. 알고리즘은 삽입 정렬와 상당히 유사한데 실제로 값을 삽입하지는 않는것에 차이가 있다.
예시는 2,1,3 순으로 되어 있으면 1,1,3 으로 만들어야 되고, 이러한 배열을 만드는데 필요한 비용은 1 이다.
1번 예제 코드
public static int solution(int[] grade) {
int answer = 0;
for (int i = 0; i < grade.length; i++) {
int min = grade[i];
for (int j = i+1; j < grade.length; j++) {
min = grade[j] < min ? grade[j] : min;
}
answer += grade[i] - min;
}
return answer;
}
2번 문제
2번 문제 코드는 아래와 같은데, 처음에는 문제 해결 방법에 대해서 생각이 안나서 고민했는데 영역을 설정한 bfs 로 생각하니 생각보다 쉽게 해결이 되었다.
문제 파라미터에 n = 4, horizontal = true 로 들어갈 경우 아래와 같은 표로 리턴이 되는 방식이다.
| 1 | 2 | 9 | 10 |
| 4 | 3 | 8 | 11 |
| 5 | 6 | 7 | 12 |
| 16 | 15 | 14 | 13 |
반면에, horizontal = false 로 들어갈 경우 아래와 같은 표로 리턴이 된다.
| 1 | 4 | 5 | 16 |
| 2 | 3 | 6 | 15 |
| 9 | 8 | 7 | 14 |
| 10 | 11 | 12 | 13 |
해결 방법으로는 숫자의 제곱이 되는 임계치를 넘기 전까지의 영역을 설정한 후에 bfs 를 적용하는 방식으로 해결하였다.
관련 코드는 아래와 같습니다.
2번 예제 코드
public class Main {
public static int[] dy = {0,1,0,-1};
public static int[] dx = {1,0,-1,0};
public static boolean[][] visited;
public static boolean check(int n, int row, int col) {
return row >= 0 && row < n && col >= 0 && col < n;
}
public static int[][] solution(int n, boolean horizontal) {
int[][] answer = new int[n][n];
int[] boundary = new int[n];
visited = new boolean[n][n];
int row = 0;
int col = 0;
int dir = horizontal == true ? 0 : 1;
int bIndex = 2;
for (int i = 0; i < n; i++)
boundary[i] = (i+1)*(i+1);
answer[row][col] = 1;
visited[row][col] = true;
for (int i = 2; i <= n*n; i++) {
if (i > boundary[bIndex-1]) {
bIndex++;
}
for (int j = 0; j < 4; j++) {
int nRow = row + dy[(dir+j) % 4];
int nCol = col + dx[(dir+j) % 4];
if (check(bIndex, nRow, nCol) && visited[nRow][nCol] == false) {
answer[nRow][nCol] = i;
visited[nRow][nCol] = true;
row = nRow;
col = nCol;
dir = (dir + j) % 4;
break;
}
}
}
return answer;
}
public static void main(String[] args) throws IOException {
System.out.println(solution(4, false));
}
}
3번 문제
bfs 를 활용하여 우물의 영역을 계산한 후, 최소 영역의 우물과 최대 영역의 우물을 배열로 리턴하면 되는 단순한 문제다.
다만 유의할 점으로는 외곽의 영역은 모두 우물이 아닌 방문하면 안되는 영역이라는 점이다.
그리고 우물이 없는 경우에는 {-1,-1} 로 리턴해야 되는 것도 유의해야 한다.
문제를 해결할 때 bfs 를 여러번 사용하기 때문에, bfs 는 따로 함수로 구현하는 것이 좋다.
3번 예제 코드
import java.io.IOException;
import java.util.*;
class Point {
int row;
int col;
public Point(int row, int col) {
this.row = row;
this.col = col;
}
}
public class Main {
public static int[] dy = {0,1,0,-1};
public static int[] dx = {1,0,-1,0};
public static boolean[][] visited;
public static int[] solution(int rows, int columns, int[][] lands) {
int[] answer = {};
visited = new boolean[rows][columns];
for (int i = 0; i < lands.length; i++) {
int row = lands[i][0] - 1;
int col = lands[i][1] - 1;
visited[row][col] = true;
}
bfs(rows, columns, 0,0, visited);
// 호수 탐색
List<Integer> areaList = new ArrayList<>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (!visited[i][j]) {
int area = bfs(rows, columns, i, j, visited);
areaList.add(area);
}
}
}
areaList.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
});
if (areaList.size() == 0) {
areaList.add(-1);
areaList.add(-1);
return areaList.stream().mapToInt(e -> e).toArray();
}
List<Integer> answerList = new ArrayList<>();
answerList.add(areaList.get(0));
answerList.add(areaList.get(areaList.size()-1));
return answerList.stream().mapToInt(e -> e).toArray();
}
public static int bfs(int rows, int columns, int row, int col, boolean[][] visited) {
int area = 0;
Queue<Point> bfs = new LinkedList<>();
bfs.add(new Point(row,col));
visited[row][col] = true;
area++;
while(!bfs.isEmpty()) {
Point p = bfs.poll();
for (int d = 0; d < 4; d++) {
int ny = p.row + dy[d];
int nx = p.col + dx[d];
if (ny >= 0 && ny < rows && nx >= 0 && nx < columns && visited[ny][nx] == false) {
bfs.add(new Point(ny,nx));
visited[ny][nx] = true;
area++;
}
}
}
return area;
}
public static void main(String[] args) throws IOException {
int[][] lands = {{2,2},{2,3},{2,5},{3,2},{3,4},{3,5},{3,6},{4,3},{4,6},{5,2},{5,5},{6,2},{6,3},{6,4},{6,6},{7,2},{7,6},{8,3},{8,4},{8,5}};
int[][] lands_2 = {{2,2},{2,3},{2,4},{3,2},{3,5},{4,3},{4,4}};
int[][] lands_3 = {{2,5},{3,3},{3,4},{3,5},{4,3}};
System.out.println(solution(9,7,lands));
System.out.println(solution(5,6,lands_2));
System.out.println(solution(5,7,lands_3));
}
}
4번 문제
4번 문제는 SQL 문제인데, 특정 기간 동안에 월별 최대 카운트를 계산하여 월별로 리뷰 카운트가 가장 많은 장소에 대한 테이블 정보를 출력하는 것이 핵심이다. 다만 최대 카운트가 동일한 경우에도 모두 출력해야 된다는 점이 유의사항이다.
월별, 장소별 리뷰 카운트를 출력하고, 월별, 장소별 리뷰카운트의 max count 와 비교하여 일치하는 경우에 대한 join 을 수행하고 결과적으로 카운트가 동일한 경우에는 월 오름차순, 이름 오름차순으로 출력하면 된다.
4번 예제 코드
SELECT summary.MONTH, places.NAME, summary.COUNT FROM places,
(
SELECT m1.MONTH, m1.PLACE_ID, m1.COUNT FROM
(
SELECT MONTH(CREATED_AT) AS MONTH, PLACE_ID, COUNT(1) FROM place_review
GROUP BY MONTH(CREATED_AT), PLACE_ID
) m1,
(
SELECT MONTH, MAX(COUNT) FROM (
SELECT MONTH(CREATED_AT) AS MONTH, PLACE_ID, COUNT(1) FROM place_review
GROUP BY MONTH(CREATED_AT), PLACE_ID
) GROUP BY MONTH, PLACE_ID
) m2
) SUMMARY
WHERE places.ID = SUMMARY.PLACE_ID
ORDER BY summary.MONTH ASC, places.NAME ASC;
결론
역량이 향상된것인지 문제가 풀만했던 것인지는 잘 모르겠으나, 상대적으로 난이도가 나쁘지는 않았던 거 같다. SQL 문제가 생각보다 쉽게 풀리지 않아서 약간 고생하기는 했지만 나머지 코딩 문제들은 연습 문제 난이도와 비교해서는 괜찮은 난이도였다고 생각된다.
'코딩테스트' 카테고리의 다른 글
| [프로그래머스] 파괴되지 않은 건물 (0) | 2022.07.27 |
|---|---|
| [프로그래머스] 빛의 경로 사이클 (0) | 2022.07.25 |
| [프로그래머스] 최소값 구하기 (0) | 2022.06.20 |
| [프로그래머스] 후보키 (0) | 2022.06.10 |
| [프로그래머스] 합승 택시 요금 (0) | 2022.06.01 |