Algorithm (51) 썸네일형 리스트형 [Java] 2021 위클리 챌린지 12주차 - 피로도 던전의 개수가 8개로 수가 많지 않다. 던전을 탐험하는 경우의 수는 8! 인데, 이는 작은 숫자이므로 Brute force로 해결이 가능하다. 순열을 찾는 알고리즘은 back tracking을 사용할 수 있는데, 던전을 방문하고 함수를 탐색을 하고 탐색이 끝나면 방문 내역에서 지워주면 된다. import java.util.HashSet; import java.util.Set; class Solution { Set visited = new HashSet(); int answer = 0; public String makeKey(int[] d){ return d[0] + "&" + d[1]; } public void solve(int k, int[][] dungeons, int depth){ int n = d.. [Java] 2021 위클리 챌린지 11주차 - 아이템 줍기 테두리와 안쪽을 구분해야 한다. 단순하게 좌표의 길이를 2배로 키우면 테두리와 안쪽을 구분하기가 쉬워진다. 1. (짝수, 짝수) 는 점 2. (짝수, 홀수) 와 (홀수, 짝수)는 선분 위 3. (홀수, 홀수)는 내부가 된다. 먼저 모든 사각형을 1로 채워준 다음, 내부를 0으로 채워주면 제일 바깥쪽 테두리만 남게 된다. 이 이후에는 BFS를 통해서 얼마나 걸리는지 확인해주면 된다. 2배로 키워놨기 때문에 정답은 2로 나눈 값이 된다. class Point{ int x; int y; int depth; public Point(int x, int y, int depth){ this.x = x; this.y = y; this.depth = depth; } } class Solution { public int .. [Java] 2021 위클리 챌린지 10주차 - 교점에 별 만들기 직선의 교점 중 정수가 되는 교점에 * 모양으로 표시하고, 이 별들을 포함하는 최소한의 사각형을 만들어서 출력하는 것이 문제이다. 먼저 정수가 되는 교점을 찾아야된다. 문제에서 친절하게 교점을 구하는 식을 알려주었다. $$Ax + By + E = 0$$ $$Cx + Dy + F = 0$$ $$ x = {BF - ED \over AD -BC}, y = {EC - AF \over AD -BC}$$ 이 식을 이용해서 교점을 구하면 된다. 단, AD-BC가 0인 경우에는 두직선이 평행하는 경우로 제외해준다. 그리고 나머지 연산을 이용해서 딱 나누어 떨어지는지를 체크하고, 정수의 교점만 찾는 것이기 때문에 딱 나누어 떨어지지 않으면 마찬가지로 제외해준다. 이렇게 구한 교점들을 배열에 넣어서 저장하고, 각각의 x와.. [Java] LeetCode 46번 permutation class Solution { public void solve(List answer, int[] nums, List cur) { if (cur.size() == nums.length) { answer.add(new ArrayList(cur)); return; } for (int i = 0; i < nums.length; i++) { int num = nums[i]; if (cur.contains(num)) { continue; } cur.add(num); solve(answer, nums, cur); cur.remove((Integer) num); } } public List permute(int[] nums) { List answer = new ArrayList(); solve(answer, nums,.. [Java] 2021 위클리 챌린지 9주차 - 전력망을 둘로 나누기 Node라는 클래스를 만들어서 wire로 연결된 송전탑들을 연결을 시켜준다. 이후 어떤 wire를 제거하였을 때, 차가 최소가 되는지 모르기 때문에 각 wire들을 순회하면서 제거한다. 그리고 bfs를 이용해서 각 송전탑들이 몇개가 연결이 되었는지 구하고, 두 그룹의 차이를 출력하면 된다. class Node { int id; List children; public Node(int id) { this.id = id; children = new ArrayList(); } } class Solution { public int solution(int n, int[][] wires) { int answer = n; Node[] nodeArr = new Node[n + 1]; for (int i = 0; i [Java] LeetCode 39번 Combination Sum DP를 이용해서 해결하였다. map에 key는 숫자, value에는 더해서 key를 만들 수 있는 리스트를 저장하였다. 0부터 target까지 만들 수 있는 숫자의 조합을 계속 더해가면서 문제를 해결하엿다. class Solution { public List combinationSum(int[] candidates, int target) { Map map = new HashMap(); for (int i = 0; i = 0) { List beforeList = map.get(idx); if (beforeList != null) { List curList = map.getOrDefault(i, new ArrayList()); for (int k = 0; k < beforeList.size(); k++) {.. [Java] LeetCode 34번 Find First and Last Position of Element in Sorted Array 정렬된 배열에서 target이 위치하는 첫번째 위치와 마지막 위치를 구하는 문제이다. 정렬이 되어있으므로 이분 탐색을 사용할 수 있다. 일반적인 이분탐색으로 찾되, 타겟보다 크거나 같은 부분에서 일치하는 것을 찾게 되면 시작점이 되고, 타겟보다 작거나 같은 부분에서 일치하는 부분을 찾게되면 마지막점이 된다. class Solution { public int[] searchRange(int[] nums, int target) { int n = nums.length; int l = 0; int r = n - 1; int[] answer = { -1, -1 }; while (l [Java] LeetCode 33번 Search in Rotated Sorted Array 로테이션이 되어있으면 숫자를 오름차순의 구역 두개의 구역으로 나누어서 생각할 수 있다. 왼쪽의 첫번째가 무조건 첫번째의 숫자가 오른쪽 구역의 첫번째 숫자보다 크게된다. 이 지점을 binary search로 찾는다. 오른쪽 구역의 시작 점을 turnPoint라는 변수에 저장하였다. 이제 왼쪽과 오른쪽 구역에서 각각 일치하는 숫자의 index를 찾고 이것을 return 해주면 된다. class Solution { public int search(int[] nums, int target) { int first = nums[0]; int n = nums.length; int l = 1; int r = n - 1; int turnPoint = 0; int answer = -1; while (l 이전 1 2 3 4 5 ··· 7 다음