본문 바로가기

PS109

[Programmers-Java] 양과 늑대 https://school.programmers.co.kr/learn/courses/30/lessons/92343 접근 트리를 bfs 탐색한다. 비트마스킹으로 중복 경로 탐색을 제거한다. 경로에 포함된 노드의 왼쪽, 오른쪽 자식 노드를 추가해 나간다. 풀이 import java.util.*; class Solution { private int n; private int[] info; private int[] left = new int[17]; private int[] right = new int[17]; private boolean[] visited = new boolean[1 2024. 4. 12.
[Programmers-Java] 산 모양 타일링 https://school.programmers.co.kr/learn/courses/30/lessons/258705 접근 n = 1일 때 n = 2일 때 마름모 타일로 끝나지 않은 경우의 수는 마름모 타일로 끝나는 경우의 수는 n - 1번째의 모든 경우의 수에서 오른쪽으로 마름모 타일을 붙이면 된다. 마름모 타일로 끝나지 않은 경우의 수를 dp[n][0], 마름모 타일로 끝나는 경우의 수를 dp[n][1]이라고 할 때 dp[n][0] = dp[n - 1][0] * 2 + dp[n - 1][1] dp[n][1] = dp[n - 1][0] + dp[n - 1][1] n번째에 tops가 있으면 dp[n][0] = dp[n - 1][0] * 3 + dp[n - 1][1] * 2가 된다. 풀이 class Solu.. 2024. 4. 10.
[Programmers-Java] 지형 이동 https://school.programmers.co.kr/learn/courses/30/lessons/62050 접근 높이 갭으로 비용을 계산하고 우선순위 큐에 삽입한다. 높이 갭이 height보다 작거나 같으면 비용은 0이다. 사다리없이 이동할 수 있는 모든 격자를 탐색한 후 가장 비용이 낮은 다음 노드를 꺼내게 된다. 풀이 import java.util.*; class Solution { public int solution(int[][] land, int height) { int n = land.length; int[] directions = { 1, 0, -1, 0 }; PriorityQueue pq = new PriorityQueue((o1, o2) -> o1.cost - o2.cost); //.. 2024. 4. 9.
[Programmers-Java] 혼자서 하는 틱택토 https://school.programmers.co.kr/learn/courses/30/lessons/160585 접근 행, 열, 대각선의 o와 x의 개수를 센다. 각각의 개수 중 3이 있으면 해당 표시가 승리한다. 게임이 불가능한 경우 o, x 둘 다 승리 o가 승리했지만 o 개수가 x 개수보다 한 개 더 많지 않음 x가 승리했지만 x 개수가 o 개수와 같지 않음 o 개수와 x 개수의 차이가 0 또는 1이 아님 풀이 class Solution { public int solution(String[] board) { int[] o = new int[8]; // (1) int[] x = new int[8]; int oCnt = 0; int xCnt = 0; for (int i = 0; i < board.l.. 2024. 1. 29.
[Programmers-Java] 무인도 여행 https://school.programmers.co.kr/learn/courses/30/lessons/154540 접근 무인도를 bfs 탐색한다. 탐색할 때 무인도 칸에 적힌 숫자를 합한다. 합을 리스트에 추가한 후 오름차순 정렬한다. 풀이 import java.util.*; class Solution { private List date = new ArrayList(); private int[] direction = {1, 0, -1, 0}; private int n; private int m; private boolean[][] visited; public int[] solution(String[] maps) { this.n = maps.length; this.m = maps[0].length(); .. 2024. 1. 28.
[Programmers-Java] 과제 진행하기 https://school.programmers.co.kr/learn/courses/30/lessons/176962 접근 중간에 멈춘 과제는 가장 최근에 멈춘 과제부터 다시 시작하기 때문에 스택에 저장한다. 과제를 시작 시간 순으로 오름차순 정렬한다. 과제를 하나 꺼내서 시작 시간과 소요 시간을 더한 후 다음 과제의 시작 시간과 비교한다. 현재 과제를 다음 과제 시작 전에 마치지 못할 경우 남은 소요 시간을 변경하고 멈춘 과제에 저장한다. 마칠 수 있으면 끝낸 과제에 저장하고 마지막에 멈춘 과제를 꺼낸다. 멈춘 과제를 이어서 진행할 경우 이전 과제를 마친 시간부터 진행한다. 풀이 import java.util.*; class Solution { public String[] solution(String[].. 2024. 1. 26.
[Programmers-Java] 두 원 사이의 정수 쌍 https://school.programmers.co.kr/learn/courses/30/lessons/181187 접근 하나의 사분면에서 점의 개수를 구해서 4를 곱한다. 원의 중심이 (0, 0)이기 때문에 원의 방정식은 x2 + y2 = r2이다. 따라서 x = (r2 - y2)1/2로 x값을 구할 수 있다. x2의 소수점을 내림, x1의 소수점을 올림하고 x2 - x1 + 1 연산하면 임의의 y 좌표에서 두 원 사이에 있는 정수 x 좌표의 개수가 된다. 풀이 class Solution { public long solution(int r1, int r2) { long answer = 0; for (int y = 1; y 2024. 1. 26.
[Programmers-Java] 광물 캐기 https://school.programmers.co.kr/learn/courses/30/lessons/172927 접근 돌 곡괭이로 광물을 5개씩 캐서 피로도를 구하고 우선순위 큐에 삽입한다. 피로도가 큰 것부터 꺼내면서 다이아몬드 -> 철 -> 돌 곡괭이 순으로 광물을 캔다. 풀이 import java.util.*; class Solution { private static final int[][] PICK_FATIGUE = { { 1, 1, 1 }, { 5, 1, 1 }, { 25, 5, 1 } }; // (1) public int solution(int[] picks, String[] minerals) { int pickCnt = Arrays.stream(picks).sum() * 5; if (pi.. 2024. 1. 26.
[Programmers-Java] 주사위 고르기 https://school.programmers.co.kr/learn/courses/30/lessons/258709 접근 n은 최대 10이다. n개의 주사위 중 n / 2개를 뽑는 조합 nCn/2 = 252 뽑은 n / 2개의 주사위로 얻을 수 있는 점수의 개수 6n/2 = 7,776 A와 B의 점수를 비교하여 나올 수 있는 승패 결과의 개수 7,7762 = 6n = 60,466,176 252 * 60,466,176 = 약 152억이기 때문에 시간복잡도를 줄여야 한다. A가 몇 번 이기는지를 이분 탐색으로 구하면 252 * 7,776 * log7,776 = 약 25,474,176으로 시간 내에 해결할 수 있다. 풀이 import java.util.*; class Solution { private int .. 2024. 1. 25.
[Programmers-Java] 가장 많이 받은 선물 https://school.programmers.co.kr/learn/courses/30/lessons/258712 접근 친구마다 인덱스를 부여한다. 2차원 배열에 선물을 주고 받은 기록을 저장한다. 각각의 선물 지수는 선물을 줄 때 마다 +1, 받을 때마다 -1한다. 풀이 import java.util.*; class Solution { public int solution(String[] friends, String[] gifts) { int n = friends.length; Map friendIdx = new HashMap(); for (int i = 0; i < n; i++) { friendIdx.put(friends[i], i); // (1) } int[][] giftLog = new int[n.. 2024. 1. 25.

티스토리툴바