kwang2134 님의 블로그

[Grind75-LeetCode] Binary Tree Level Order Traversal - Medium 접근재귀풀이이진트리를 레벨별로 List에 담아 출력하는 문제이다. 이진트리는 TreeNode 형태로 현재 노드의 값, 왼쪽 서브트리, 오른쪽 서브트리를 가지는 객체 형태로 주어진다.예제 1번으로 주어지는 트리의 모습인데 각 레벨별 노드 값을 List> 형태로 반환해야 하는데 현재 트리에선 루트 노드인 레벨 0 [3], 레벨 1 [9, 20], 레벨 2 [15,7]로 [ [3], [9,20], [15,7] ] 형태의 결과를 반환해야 한다. 이 문제 또한 재귀를 이용해 간단하게 풀 수 있는 문제로 리스트의 인덱스와 트리의 레벨을 매칭시켜 각각 해당하는 위치에 넣어주면 된다. public Lis..

[Grind75-LeetCode] 3 Sum - Medium접근투 포인터풀이주어지는 정수 배열에서 각자 다른 3개의 숫자가 더해서 0이 되는 경우를 모두 구하는 문제이다. 숫자가 3개인 만큼 단순한 반복으로 접근하게 되면 성능이 매우 떨어져 통과를 하지 못할 것이다. 그래서 이번 문제는 하나의 숫자를 고정하고 두 개의 포인터를 사용해 체크해 보는 투 포인터를 사용하였다. 정렬된 배열을 순회하며 숫자 하나를 고정해 두고 포인터 하나는 고정된 숫자 바로 다음 그리고 나머지 포인터는 배열의 끝에서 시작하여 세 숫자의 합이 0보다 작으면 왼쪽 포인터를 오른쪽으로 이동하고 0보다 크다면 오른쪽 포인터를 왼쪽으로 이동한다. 이 과정을 반복하여 세 숫자가 0이 되는 경우를 다 찾게 된다.  public List..

[Grind75-LeetCode] Longest Substring Without Repeating Characters - Medium접근Set슬라이딩 윈도우슬라이딩 윈도우 성능 향상풀이문자열 내 부분 문자열 중 가장 긴 부분 문자열의 길이를 구하는 문제이다. 겹치는 문자 없이 부분 문자열을 이루어야 하는 조건이 있고 단순한 Set을 이용한 방법과 Map을 이용한 슬라이딩 윈도우 알고리즘 그리고 Map 대신 배열을 사용하여 성능을 향상 시킨 슬라이딩 윈도우 순서로 진행할 예정이다. 우선 Set을 사용한 방법이다. 가장 직관적이고 쉬운 방법으로 각 인덱스에서 2중으로 반복문을 돌며 Set에 추가해 이미 존재하는 원소라면 반복을 중단하고 길이를 반환하여 최댓값을 구하는 방식이다. 가장 간단하고 쉬운 방법이지만..

[Grind75-LeetCode] K Closest Points to Origin - Medium접근우선순위 큐퀵 셀렉트 (Quick Select)풀이좌표 평면에서 주어진 2차원 배열에 들어있는 좌표를 원점에서 가까운 순서대로 k개만큼 반환하는 문제이다.  문제를 보고 좌표들을 다 원점과 거리 계산을 하고 인덱스와 함께 우선순위 큐에 넣은 뒤 k개만큼 꺼내면 될 거 같아 그렇게 풀었다.  private class Point { double num; int index; public Point(double num, int index) { this.num = num; this.index = index; } }큐..

[Grind75-LeetCode] 01 Matrix - Medium접근bfsdp풀이0과 1로 이루어진 2차원 배열을 통해 각 인덱스에서 제일 가까운 0까지의 거리가 얼마나 되는지 구하는 문제이다. 문제를 보니 늘 사용하던 bfs를 통해 풀면 될 거 같은 문제였다.    private static final int[] dx = {0, 0, -1, 1};    private static final int[] dy = {1, -1, 0, 0};    public int[][] updateMatrix(int[][] mat) {        int[][] res = new int[mat.length][mat[0].length];        Queue que = new LinkedList();        for..

[Grind75-LeetCode] Insert Interval - Medium접근구현풀이2차원 배열로 각 구간이 주어지고 새로운 구간이 주어질 때 병합된 최종 구간은 어떻게 되는지 구하는 문제이다. 새로운 구간과 기존 구간이 겹치는 곳만 조작을 해주면 되는 문제이다. 예제2 번을 예시로 설명하겠다.Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]Output: [[1,2],[3,10],[12,16]]기존 구간1~2, 3~5, 6~7, 8~10, 12~16새로운 구간4~8겹치는 구간3~5, 6~7, 8~10겹치는 구간을 연결3~10결과1~2, 3~10, 12~16이렇게 새로운 구간을 삽입하며 기존 구간과 겹치는 부분을 병합하..

[Grind75-LeetCode] Maximum Subarray - Medium 접근카데인 알고리즘 (Kadane's Algorithm)풀이Grind75의 2주 차 마지막 문제로 LeetCode에서 풀어보는 첫 Medium 난이도 문제이다. 이 문제는 주어진 트리 내 서브트리의 합 중 최댓값을 구하는 문제이다. 주어지는 트리가 int 배열의 형태이기 때문에 사실상 배열 내 연속되는 부분의 최댓값을 구하는 것과 동일하다. 보통 연속되는 부분의 최댓값을 구할 때 브루트 포스를 사용해 구해주면 간단하긴 하지만 아래의 추가 내용으로 "만약 이 문제를 O(n) 성능으로 해결하는 법을 찾았다면 분할 정복 방법으로 도전해 봐라"라는 문구가 있기에 이 문제는 O(n) 성능으로 해결이 가능하다는 말인 거 같다. 그렇다면..

[Grind75-LeetCode] Middle of the Linked List - Easy접근구현풀이노드로 주어지는 리스트에서 가운데 노드를 구하는 문제이다. 만약 가운데 노드가 두 개라면 두 번째 노드를 선택한다. 짝수일 경우 가운데 노드가 두 개이기 때문에 뒤쪽을 선택하는 것이다. 문제 자체는 정말 간단하다. 배열로 주어졌다면 배열의 길이를 반으로 나눠 해당 인덱스를 반환하면 되겠지만 노드로 주어져 잠깐 생각을 하게 만드는 거지 큰 차이는 없다. head 노드로부터 next를 계속 탐색하여 총길이를 구한 뒤 중간 값 노드까지 포인터를 옮겨주는 방식으로 문제를 풀었다.    public class ListNode {        int val;        ListNode next;        Li..

[Grind75-LeetCode] Diameter of Binary Tree - Easy Diameter of Binary Tree - LeetCode접근재귀풀이주어지는 이진트리의 최대 지름을 구하는 문제이다. 지름이란 양쪽 서브트리 노드 깊이를 더한 것과 같다고 보면 되는데 문제에서 최대 지름은 루트 노드를 지날 수도 있고 지나지 않을 수 도 있다고 나와있다. 루트 노드를 지나지 않고 최대 지름이 어떻게 되는지 잘 이해가 가지 않지만 아무튼 구하면 된다. LeetCode의 문제는 배열의 형태로 값이 주어지는 타 사이트와 다르게 객체 참조 형태로 주어지기 때문에 재귀나 반복을 사용해야 하는 문제가 대부분이다. 이번 문제 또한 재귀를 통해 풀어진다. private int diameter = 0; ..

[Grind75-LeetCode] Add Binary - Easy접근진수 변환정석 덧셈 구현(?)풀이문자열로 주어지는 이진수를 덧셈 연산을 수행한 뒤 이진수 값을 다시 문자열로 반환하는 문제이다. 자바의 경우 문자열로 이루어진 각 진수 변환 메서드를 기본적으로 제공하다 보니 사실 통과 자체는 굉장히 쉬운 문제이다. 그런데 주어지는 이진수의 최대 길이가 10000자리로 long 타입을 사용해도 오버플로우가 발생한다. 자바의 BigInteger 라이브러리를 사용해 주면 푸는데 문제는 없으나 처참한 성능을 자랑했다.//BigInteger 사용 코드import java.math.BigInteger;class Solution { public String addBinary(String a, String b) ..