Hello backEnd

[백준 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..

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

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

문제 설명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..

문제 설명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..

문제 설명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

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

문제 설명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]; ..

문제 설명1. 문자열이 주어진다.2. 지그재그 이동할 숫자가 주어진다.3. 지그재그 하고 문자열 변경하면 된다.풀이 과정 - 지그재그보다는 위아래? 라고 생각하면 쉽다.P A H NA P L S I I GY I R1. 보면 만들어지는 순서가 1 2 3 2 1 2 3 2 1 2 3 ... 이렇게 된다.2. 그러면 Queue 배열을 만들어서 q1(PAHN) q2(APLSIIG) q3(YIR) 이렇게 두고 합쳐주면 바로 풀린다.3. 위아래 슉 슈슉 슉코드class Solution { public String convert(String s, int numRows) { // 위의 경우에는 지그재그가 애초에 안나온다. if(numRows == 1 || numRows..

문제 설명1. 건물의 개수 N이 주어진다.2. 건물의 높이가 N개 주어진다.3. 각 건물은 자신의 높이보다 높은 건물들을 볼 수 있다.4. 보고있는 방향으로는 앞에 있는 건물보다 높은 건물을만 볼 수 있다.5. 오른쪽, 왼쪽 기준 볼 수 있는 모든 건물의 숫자랑 가장 가까운 건물 위치를 한줄씩 출력하면 된다.풀이 과정1. 구현2. Stack을 사용해 주면 된다. 투포인터 비슷한가 싶었는데 전혀 아니었다.3. 왼->오, 오->왼 하면서 Stack에 점점 높이가 낮아지면서 건물들을 저장한다.4. 그러면서 현재 건물보다 높은것들만 있으면 그게 size, 그 중 가장 가까운 위치를 확인해주면 된다.5. 모노토닉 스택에 대해서 알고 있으면 쉬울 수 있지만.. 나는 알고 있는데도 떠올리는데 시간이 오래 걸렸다.코드..