본문 바로가기

코딩테스트42

거리두기 확인하기(Lv.2) 문제 설명 입출력 예시 요약 대기실별로 맨해튼 거리가 2 이하인 응시자가 있는지 확인(단, 파티션이 막고 있는 경우 제외) 풀이 접근 방식 1. 응시자들의 맨해튼 거리가 1인 경우 → false 리턴 2. 응시자들의 맨해튼 거리가 2인 경우 → 같은 방향으로 두 칸 떨어져 있는 경우 응시자들 사이에 빈 공간(O)이 있다면 false → 대각선으로 떨어져 있는 경우 응시자의 (위쪽, 왼쪽) / (위쪽, 오른쪽) / (아래쪽, 왼쪽) / (아래쪽, 오른쪽) 위치에 빈 공간(O)이 있다면 false 코드리뷰 import java.util.*; class Solution { int N, M; String[][] maps; // 상하좌우 한 칸씩 탐색을 위한 배열 int[] dirY1 = {-1, 1, 0, 0}.. 2024. 4. 16.
리코쳇 로봇(Lv.2) 문제 설명 입출력 예시 요약 출발점(R)에서 부터 동서남북 각 방향에 대해 벽(D)에 도달하기 전까지 이동하면서 도착점(G)까지의 최단 거리 구하기 풀이 접근 방식 1. 맵 정보를 이차원 배열에 담는다. → 출발점(R)과 도착점(G)의 좌표를 변수에 저장 2. bfs를 통한 최단 거리 구하기 → 출발점에서 bfs 시작. 도착점까지 최단 거리 구하기 3. 도착하지 못하는 상황 → 미끄러지는 그림을 상상했을 때, 도착점(R)의 상하좌우 어느 한 곳에는 반드시 벽(D)이 있어야 도달 가능 코드리뷰 import java.util.*; // 위치 정보를 담을 객체 클래스 class Position { int row; int col; int cnt;// 거리가 아닌 움직인 횟수를 기록한다. public Positi.. 2024. 4. 16.
미로 탈출(Lv.2) 문제 설명 입출력 예시 요약 레버로 이동한 후 도착지점으로 이동하는 최단 거리 구하기 풀이 접근 방식 1. 맵을 구성하는 이차원 배열 만들기 → 출발지(S), 레버(L), 도착지(E)가 있는 좌표를 따로 저장 2. bfs를 활용한 최단 거리 구하기 → 출발지(S)에서 레버(L)까지 bfs시작 → 레버에 도달했다면 레버에서 도착지(E)까지 bfs 시작 → 도착지에 도달했다면 S~L 거리와 L~E 거리 합 리턴 코드리뷰 import java.util.*; // 현재 위치와 거리를 저장할 객체 클래스 class Position { int row;// y좌표 int col;// x좌표 int dist;// 거리 public Position(int row, int col, int dist) { this.row =.. 2024. 4. 16.
줄 서는 방법(Lv.2) 문제 설명 입출력 예시 요약 n명의 사람을 n!(factorial)만큼 가지수로 나열했을 경우 k번째 나열 순서 리턴 풀이 접근 방식 1. 각 인덱스의 숫자가 얼마의 반복 주기를 갖는지 확인 → n = 4의 경우 {1, 2, 3, 4} / {1, 2, 4, 3} / {1, 3, 2, 4} / {1, 3, 4, 2} / {1, 4, 2, 3} / {1, 4, 3, 2} / {2, 1, 3, 4} / ... → 첫 번째 숫자의 경우 6개, 두 번째 숫자의 경우 2개, 세 번째와 네 번째는 각각 1개의 반복 사이클을 갖는다. → n = 4의 경우 반복되는 사이클을을 배열로 나타내면 {(n-1)!, (n-2)!, (n-3)!, (n-4)!} 임을 확인 할 수 있다. 2. k를 통해 각 인덱스에 해당하는 숫자 구.. 2024. 4. 15.
배달(Lv.2) 문제 설명 입출력 예시 요약 1번 마을에서 출발해서 K 이하의 시간으로 배달 가능한 모든 마을의 개수 구하기 풀이 접근 방식 1. 방문 가능한 모든 경로 찾기 → 간선의 가중치(소요 시간)와 도착 마을의 번호를 담는 객체 클래스(Node) 생성 → graph라는 배열에 특정 마을의 인접한 마을의 Node리스트를 저장 → 마을을 잇는 간선은 방향이 없기 때문에 반대의 경우도 함께 저장 2. 최소 비용으로 마을 방문하기 → 다익스트라(dijkstra) 알고리즘을 통해 최소비용으로 방문하는 경우를 구한다. 3. 배달 가능한 마을의 개수 구하기 → K 이하의 비용이 드는 마을의 개수를 카운팅해서 리턴 코드 리뷰 import java.util.*; // 도착 지점의 번호와 간선의 가중치를 담는 Node 객체 클래.. 2024. 4. 11.
대충 만든 자판(Lv.1) 문제 설명 입출력 예시 요약 주어진 keymap의 문자열에 들어있는 문자들을 최대한 적게 눌러서 targets에 있는 단어 만들기 풀이 접근 방식 1. targets의 문자열을 이루고 있는 문자를 하나씩 keymap에서 조사 → .indexOf() 메소드로 주어진 keymap을 모두 조사해 최소값을 찾는다. 2. keymap에 없는 문자를 포함하는 경우 -1을 return → 스트림의 최종 처리 기능인 .orElse() 메소드를 통해 -1을 리턴 코드리뷰 import java.util.*; public class Solution { public int[] solution(String[] keymap, String[] targets) { List list = new ArrayList(); for(int i.. 2024. 4. 11.

티스토리툴바