2025/02 8

[백준 14500번] 테트로미노 - java

문제 설명1. 4개 정사각형을 이어붙이는 도형들이 있다. (변을 붙이는 모든 형태)2. 지도가 주어진다.3. 위의 도형으로 숫자를 더해서 최대값을 구하면 된다.풀이 과정1. 구현2. 삼전 문제는 매번 느끼는건데 뭔가 구현 위주로 코드를 길게 만드는걸 선호하는 것 같다. 개인적으로 취향은 아님3. DFS + 엣지케이스 처리.4. depth 4 까지 찾아가면서 DFS 해주면 되고, ㅓ ㅏ ㅗ ㅜ 같은 중간에 가지가 뻗어나가는것은 이로 처리하기가 쉽지 않다(뒤로 돌아와서 check를 다시 해야하기 때문) 이는 그냥 따로 엣지케이스로 처리해준다.5. 성능이 될까? 했는데 이게 되네..코드import java.util.*;public class Main { private static int[][] map; p..

알고리즘 공부 2025.02.20

[leetcode - 148. Sort List] java

문제 설명1. 지금 값, 다음 노드가 들어있는 노드가 있다.2. 이거 정렬하면 된다. 풀이 과정 1. 분할 정복, 진짜 오래 헤맸고 혼자 못풀어서 해설을 보고 풀었다. 뭔가 알고리즘 실력에 점점 자신이 없어진다...2. 결국은 이것도 반으로 나눠서 이거를 정렬해주면 되는 문제이다.3. 반으로 나누기 : 보법이 다른 두개를 두고(한칸씩, 두칸씩) 두칸씩 가는 친구가 마지막까지 가면 한칸씩 가는 친구는 중간값이 된다.4. 그리고 위의 (3) 과정에서 얻은 반에서 다음꺼로 가지 못하게 이동을 끊어버림5. 구해진 반반을 계속 반복하면서 구하고6. (5)의 과정에서 구해진 애를 크기 비교해서 node 를 구해주고7. (6)으로 구한 애를 다시 (5)로 return 한 뒤 그거를 다시 (6) 해주는걸 반복하면 분할..

알고리즘 공부 2025.02.16

[leetcode - 30. Substring with Concatenation of All Words] java

문제 설명1. 문장 s 와 단어들이 배열로 주어진다.2. 단어들을 붙여서 s의 내부 문장을 만들 수 있으면 그 시작점을 구하면 된다.3. 순서는 상관없지만 단어들은 딱 붙어 있어야 한다. 풀이 과정 1. 슬라이딩 윈도우 + 해시맵2. 진짜 오래 헤맸다. 그리고 풀이 방법을 생각해내기는 했는데 솔직히 좀 더럽게 푼 느낌이다.3. 중요한 점은, words 의 내부 단어들의 길이는 같다는 것4. 만들어진 단어들을 앞에는 빼고 뒤에는 더하면서 비교하면 구할 수 있다.5. 그래서 words 배열의 길이만큼 시작점을 가진 슬라이딩 윈도우 풀이를 만들어주면 된다.코드class Solution { public List findSubstring(String s, String[] words) { int ..

알고리즘 공부 2025.02.12

[leetcode - 3. Longest Substring Without Repeating Characters] java

문제 설명1. 문자열이 주어진다.2. 그 문자열에서 중복되지 않은 최대 서브문자열 길이를 구하면 된다. 풀이 과정 1. 슬라이딩 윈도우 문제이다.2. 왼 -> 오 로 가면서 문자들을 HashSet 에 저장하고 중복이 있다면 그 전까지 저장한 Set을 지운다.3. 그리고 현재 위치까지의 값을 더하면 쉽게 구할 수 있다.4. (2) 과정을 하기 위해서는 이전에 저장한 값들을 index 로 지우면 된다.코드class Solution { public int lengthOfLongestSubstring(String s) { int ans = 0; // 최종 답 int remover = 0; // hashSet 삭제를 위한 index HashSet hs = new Hash..

알고리즘 공부 2025.02.09

[leetcode - 209. Minimum Size Subarray Sum] java

문제 설명1. 배열이 주어진다.2.target이 주어진다.3. 배열을 순서대로 더해서 target 보다 크거나 같은 숫자가 되면 그 숫자를 구하는 가장 적은 배열 요소의 갯수를 구하면 된다. 풀이 과정 1. 투포인터 문제이다.2. 투포인터 시작점을 저장시켜 두고 요소 크기, 더한 값을 구한다.3. for문 돌리면서 매번 요소를 더해준다.4. 그리고 만들어진 값이 target보다 커지면 슬라이딩 앞에서부터 줄여가면서 크기를 비교하면 된다.코드class Solution { public int minSubArrayLen(int target, int[] nums) { int start = 0; // 슬라이딩 윈도우 시작점 int sum = 0; // 총합 int cnt..

알고리즘 공부 2025.02.07

[leetcode - 15. 3Sum] java

문제 설명1. 배열이 주어진다.2.배열에서 3개 숫자를 더해서 0이 되는 것들을 찾는다.3. 근데 그 대상 숫자들이 중복되면 안된다. 풀이 과정 1. 투포인터 문제인데, 해결 방법이 생각이 잘 안나서 많이 헤맸다.2. 앞에서부터 뒤로 가면서 기준 인덱스의 뒤에를 투포인터로 찾으면 된다.3. 그리고 중복되는 값들을 제거해주면서 구하면 된다.코드class Solution { public List> threeSum(int[] nums) { List> ans = new ArrayList(); // 투포인터 실행을 위한 list 정렬 Arrays.sort(nums); // 3개 찾아야 하니까 2개 남겨놓음 for(int i=0; i

알고리즘 공부 2025.02.07

[leetcode - 11. Container With Most Water] java

문제 설명1. 배열이 주어진다.2. 안에 물이 담긴다. (오른쪽 왼쪽 중 더 높은 것의 높이 * 둘의 거리만큼)3. 가장 많은 물을 구하면 된다.  풀이 과정 1. 간단한 투포인터 문제이다.2. 처음, 마지막 위치를 구한다.3. 부피를 구한 뒤에 최대 부피를 갱신한다.4. 둘 중 더 낮은 위치를 상대쪽으로 이동시키면 된다.+) 나는 생각을 못했던 건데, 4번 과정에서 길이가 계속 더 작다면 더 긴 위치가 될 때까지 계속 갱신해 줘도 된다.(이러면 앞의 과정을 스킵할 수 있어서 시간 이득)코드class Solution { public int maxArea(int[] height) { int maxWater = 0; int start = 0; int end = he..

알고리즘 공부 2025.02.05

[leetcode - 167. Two Sum II - Input Array Is Sorted] java

문제 설명1. 배열이랑 만들어야 하는 숫자가 주어진다.2. 배열은 순서대로 (작은거부터 큰거까지) 주어진다. 풀이 과정 1. 간단한 투포인터 문제이다.2. 맨 처음 숫자 + 맨 뒤 숫자3. (2)에서 만들어진 숫자가 타겟보다 크면 맨 뒤보다 한칸 앞, 작으면 맨 앞에서 한칸 앞으로 움직이면서 풀면 된다.4. 같은거면 return코드class Solution { public int[] twoSum(int[] numbers, int target) { int start = 0; int end = numbers.length - 1; while(true) { int now = numbers[start] + numbers[end]; ..

알고리즘 공부 2025.02.05