Hello backEnd

문제 설명1. 정렬되지 않은 배열이 주어진다.2. 숫자가 이어지는(1, 2, 3, 4 ... 이렇게) 길이 중 최대값을 구하면 된다.3. O(n) 으로만 가능풀이 과정1. 참고로 O(n) 이라는게 배수까지는 인정(그니까 제곱이나 로그가 아니라 걍 O(2n) 이런거는 어차피 시간 차이가 적기 때문에 O(n) 으로 통일)2. 그래서 정렬하고 차이 구하면 굉장히 간단하다.3. 먼저 배열을 정렬하고4. 다시 한번 돌면서5. 이전보다 지금것이 1만큼 크면 이어지는 숫자이고6. 이전이랑 지금이 같으면 상관 없고(이거는 같은거라 영향 X)7. 2이상 차이가 나면 끊어짐(초기화)8. 하면 끝. 간단하다.코드class Solution { public int longestConsecutive(int[] nums) {..

문제 설명1. 전체 사람 수 N, 친구간 거리 K가 주어진다.2. 사람들 이름이 순서대로 주어진다.3. 이름의 길이가 같고 거리가 K 사이인 쌍을 모두 구해서 숫자를 구하면 된다.풀이 과정1. 슬라이딩 윈도우2. 백준은 다 좋은데 난이도가 애매할때가 있다. 이거는 골드4라고 하기에는 좀 쉬운 느낌3. 서로 친구라는거는 어차피 위로보나 아래로보나 기준이 같다.4. 그래서 그냥 위에서 아래로만 확인하면 쌍을 다 구하는 것과 같다.5. 위에서부터 아래로 K만큼 슬라이딩 윈도우 하고, 그 숫자는 HashMap으로 하면 된다.코드import java.util.*;public class Main{ public static void main(String[] args) { // 30000 개의 입력...

문제 설명1. 이미 존재하는 interval 들이 있다. 이것들은 서로 겹치지 않고 오름차순으로 있다.2. 여기에 새로운 interval 이 추가된다.3. 새로운 interval 이 기존 interval 사이로 잘 녹아들게 하면 된다.4. 녹아든다는건 오름차순으로 들어가고 혹시 겹치는 부분이 있으면 그걸 덥어주게 하면 됨풀이 과정1. 한번의 for문으로 구하는 방법은 잘 모르겠다.2. 3개의 for문으로 나눈다. (indexing으로 진행)3. (1) 새로운 interval보다 앞서는 부분 -> 도착점이 새 interval 앞부분보다 작은 애들은 신규 interval이랑 관계 없음4. (2) 새로운 interval이 들어가는 부분 -> 시작점이 새 interval 뒷부분보다 크면 안겹친다.5. 그리고, ..

문제 설명1. 문자열의 배열이 주어진다.2. 아나그램(문자를 섞어서 같은 것들)을 묶으면 됨3. 순서는 상관 없음풀이 과정(느린풀이)1. 처음에는 간단하게 이중 map으로 구했다.2. 빈도수를 가진 map 을 만들고, 그 map을 다시 key로 가지면서 value 에 String 들을 List로3. 딱봐도 느릴것같았는데 최저속도로 통과했다ㅋㅋ코드class Solution { public int[][] merge(int[][] intervals) { // 정렬에 대한 얘기가 처음에 없음. 근데 시작점만 정렬해주면 될듯? Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); // 최초 배열 만..

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