xor eax, eax

더해서 target이 만들어지는 부분배열을 구하고 겹치지 않는 부분배열의 최대 개수를 구하는 문제이다. 해당 문제는 Prefix Sum을 통해 문제를 해결할 수 있다. Prefix Sum prefix sum은 Memoization 기법을 이용한 풀이 방법으로 브루트 포스 풀이시 O(n^2) 이상의 시간 복잡도를 O(n)으로 낮출 수 있다. prefix sum의 과정은 아래와 같은 코드로 나타낼 수 있다. [-1,3,5,1,4,2,-9] //prefix sum -1 = -1 -1 + 3 = 2 ... -1 + 3 + ... + 2 + -9 = 5 [-1,2,7,8,12,14,5] 위와 같은 memoization을 마친 상황에서 target = 6을 찾아야 한다고 가정해보자. 이때 sum - target으로..

class Solution { public int balancedString(String s) { //caching var cache = new int[128]; int n = s.length(), result = n, k = n / 4; for (var ch : s.toCharArray()) { cache[ch]++; } //sliding windows var slow = 0; var fast = 0; while (fast < n) { //fast pointer goes while slow pointer condition does not meet. //decrease cache frequency. cache[s.charAt(fast)]--; fast++; //caused by fast pointer a..

이분 탐색을 진행할 때 while 문을 종료시키는 여러가지 방법 중 아래의 3가지를 언제 어떤 것을 사용해야 할지를 알아본다. 세 조건의 차이점 기본적으로 어떤 조건으로 while 문을 종료시키든 차이가 없다. 하지만 본인이 어떤 식으로 구현하고 싶은지, 어떤 내용을 구현하고 싶은지에 따라 달라지므로 세세한 내용을 알아둘 필요가 있다. mid = (low + high) >>> 1로 가정한다. low < high low는 inclusive, high는 exclusive. low == high가 됐을때 while 문이 종료된다. high를 exclusive하므로 high = mid, low = mid + 1로 업데이트한다. loop가 끝난 low 혹은 high를 가지고 로직을 이어나가고 싶을때 low < h..

class Solution { public int coinChange(int[] coins, int amount) { //dp[amount]가 정답이므로 amount + 1의 크기로 초기화 var dp = new int[amount + 1]; //최소값을 찾는 것이므로 무한대에 해당하는 값을 채우기 //점화식 dp[i - coin] + 1으로 인해 overflow를 해결하기 위해 - 1 Arrays.fill(dp, Integer.MAX_VALUE - 1); //0을 만드는데 필요한 경우의 수를 첫번째 값에 초기화 dp[0] = 0; //dp 배열의 2번째부터 돌면서 for (var i = 1; i < dp.length; i++) { //모든 동전 중에 for (var coin : coins) { //해당..

class Solution { public List findAnagrams(String s, String p) { var list = new ArrayList(); if (s == null || p == null || s.length() == 0 || p.length() == 0) return list; //hashing //'a' is equal to 97 and 'z' is equal to 122. //constraints said that letters are always lower case. var hash = new int[128]; for (char ch : p.toCharArray()) { hash[ch]++; } //two pointers and target length int left =..

역순으로 되어있는 자리수마다 나뉘어져 있는 링크드리스트의 노드를 하나씩 순회하며 값을 더하고 그 결과를 반환하는 문제이다. 풀이 class Node { int val; Node next; Node (int val, Node next) { this.val = val; this.next = next; } Node (int val) { this.val = val; } } public class Problem { public Node makeListNode(int[] arr) { Node pointer, dummy = new Node(0); pointer = dummy; for (var i : arr) { pointer.next = new Node(i); pointer = pointer.next; } retur..

TreeNode의 node들이 주어졌을때 오른쪽에서 바라봤을때 보이는 값만 List로 출력하는 문제이다. recursion과 depth를 이용하여 문제를 풀어야겠다는 아이디어는 구했으나 depth를 어떻게 적용할 수 있을지 감을 잡지 못해 다른 사람의 풀이를 참고하였다. 핵심 아이디어 코드는 다음과 같다. if (depth == answer.size()) answer.add(node.val); rightSide(node.right, depth + 1); rightSide(node.left, depth + 1); root 레벨에서부터 값을 차례대로 넣기 때문에 depth == answer.size()라는 조건이 성립한다. 같은 레벨일 때는 항상 최우측부터 체크하여 좌측으로 차례대로 방문을 하고 해당 레벨의..

완전 깡구현 문제. 터진 공간을 찾아 위에서부터 블럭을 끌어와 채우는 방식이 평소에 생각해보지 못 한 방식이라 재밌었다. 이번에도 역시 2차원 배열을 다룰때 인덱스때문에 꽤 애를 먹었는데 0, 0에서 시작하는 순회 이외에 다른 방식으로 순회하는 방법 연습을 더 해야할듯하다. import java.util.*; class Solution { char[][] matrix; List yList = new ArrayList(); List xList = new ArrayList(); void squareFinder(int i, int j) { var pos = matrix[i][j]; if (pos == matrix[i + 1][j] && pos == matrix[i][j + 1] && pos == matrix[..

최대값 구하는 개념과 이중 while loop를 돌며 값을 채워주는 개념까지는 잘 적용하였으나 내부 while loop를 세부적으로 구현할때 문제가 생겨 다른 사람의 풀이를 참고하였다. 해당 풀이에서의 핵심은 이동을 하고 값의 유효성을 확인하는 것이 아니라 이동할 좌표가 이미 값이 채워졌는지 확인(arr[y + 1][x] or arr[y][x + 1]과 같이) 하고 0이 아닌 값으로 이미 채워져있다면 이미 해당 좌표를 들렀다는 의미이므로 해당 좌표로 이동하지 않고 내부 while loop를 break시키는게 핵심이었다. 헷갈리는 while loop + 헷갈리는 array index 문제의 조합이라 매우 헷갈렸다. while loop와 array index에 대해 좀 더 심도있게 공부해야 할 필요를 느낀다..

Comparator를 직접 구현하여 String끼리 값을 비교할 수 있는지를 묻는 문제였다. 기본적으로 주어지는 Collections.reverseOrder()를 이용하여 내림차순을 구현하면 String은 사전순으로 정렬되게 되어있으므로 3과 30을 비교하였을때 "330"이 아닌 "303"으로 값이 나온다. 원하는 결과를 얻기 위해서는 Comparator를 직접 구현해야한다. Comparator의 compareTo a.compareTo(b)는 a의 아스키 코드 값과 b의 아스키 코드를 비교하는 메서드이다. a는 기존에 존재하던 값을 의미하고 b는 새롭게 들어오는 값을 의미한다. 이때 (a - b) > 0라면 양수가 반환되고 그 반대에는 음수가 반환, 값이 같을 때에는 0을 리턴한다. 음수거나 0일 때에는..