뒤죽박죽 코딩 이야기

2022년 04월 14일 목요일 - 오늘은 할말이 엄서영

오늘 올려볼 문제는 700번 Search in a Binary Search Tree 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

너무 쉽자너

입력

사진에서도 볼 수 있듯이 Binary Search Tree의 root Node와 int값 1개가 입력으로 들어온다.

풀이 및 코드

Binary Search Tree 에 val가 있는지 찾아서 해당 노드를 리턴하는 문제다.

오늘은 처음부터 정답을 생각해냈다.

그냥 bst를 주어준 것 부터가 문제가 이미 풀려있던 것이나 마찬가지였다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root != null && root.val != val) root = root.val < val ? root.right : root.left;

        return root;
    }
}

제출 화면

오늘 문제는 너무 쉬웠다.

내일 문제는 좀 재밌었으면 좋겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.

2022년 04월 13일 수요일 - 아우 졸려

오늘 올려볼 문제는 59번 Spiral Matrix II 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

편함을 위해 속도를 희생했다

입력

사진에서도 볼 수 있듯이 int 값 1개가 입력으로 들어온다.

풀이 및 코드

n * n 크기의 2차원 배열에 오른쪽으로 회전하면서 값을 채우고 리턴하는 문제다.

오늘은 처음부터 정답을 생각해냈다.

가는 방향에 대한 값을 미리 정의해두고 try catch를 써서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];

        int[] x = {1, 0, -1, 0};
        int[] y = {0, 1, 0, -1};
        int index = 0, yIndex = 0, xIndex = 0;
        int i = 1;

        while(i <= n * n)
        {
            try
            {
                if(result[yIndex][xIndex] > 0) throw new Exception("");

                result[yIndex][xIndex] = i++;

                xIndex += x[index];
                yIndex += y[index];
            }
            catch(Exception e)
            {
                xIndex -= x[index];
                yIndex -= y[index];

                index++;
                index %= 4;

                xIndex += x[index];
                yIndex += y[index];
            }
        }

        return result;
    }
}

제출 화면

오늘은 문제 풀기가 좀 귀찮아서 속도를 희생했다.

내일은 좀 덜 귀찮은 문제가 나왔으면 좋겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.

2022년 04월 12일 화요일 - 치킨 마시따

오늘 올려볼 문제는 289번 Game of Life 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

맞왜틀 2번 시전했다

입력

사진에서도 볼 수 있듯이 2차원 int배열 1개가 입력으로 들어온다.

풀이 및 코드

문제를 참고해주길 바란다.

오늘은 처음부터 정답을 생각해냈다.

처리를 편하게 하기위해 board보다 길이가 2씩 큰 2차원 배열(arr)을 만든다.

각각 board의 값을 8방향에다가 더해준다.

그러면 arr에는 각 cell에 주변에 1이 몇개있는지 저장하고 있게된다.

이렇게 구한 arr과 board의 관계를 규칙에 맞게끔 바꿔주는걸로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public void gameOfLife(int[][] board) {
        int[][] arr = new int[board.length + 2][board[0].length + 2];

        int[] xDir = {-1, 0, 1};
        int[] yDir = {-1, 0, 1};

        for(int i = 1; i <= board.length; i++)
           for(int j = 1; j <= board[0].length; j++)
           {
               arr[i][j] -= board[i - 1][j -1];         // 현재 cell에도 더해주는 구문이 있기 때문에 미리 빼두는 작업
               for(int y : yDir)
                   for(int x : xDir)
                       arr[i + y][j + x] += board[i - 1][j -1];
           }

        for(int i = 1; i <= board.length; i++)
        {
           for(int j = 1; j <= board[0].length; j++)
           {
               int num = arr[i][j];

               if(board[i - 1][j - 1] == 0)
               {
                   if(num == 3) board[i - 1][j - 1] = 1;
               }
               else
               {
                   if(num < 2 || 3 < num) board[i - 1][j - 1] = 0;
               }
           }
        }
    }
}

제출 화면

indexing을 잘못해놓고는 "맞는데 왜 틀리지"를 2번 시전했었다.

내일은 실수을 안하고 한 번에 딱 풀었으면 좋겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.

2022년 04월 11일 월요일 - 왜 아직도 월요일..??

오늘 올려볼 문제는 1260번 Shift 2D Grid 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

오늘은 급한 일 처리하느라 좀 늦게 풀어따아....

입력

사진에서도 볼 수 있듯이 2차원 int 배열 1개와 int 값 1개가 입력으로 들어온다.

풀이 및 코드

2차원 배열을 k만큼 밀어낸 2차원 배열을 리턴하는 문제다.

오늘은 처음부터 정답을 생각해냈다.

2차원 배열을 1차원으로 봐서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        List<List<Integer>> result = new ArrayList<>();
        for(int i = 0; i < grid.length; i++) result.add(new ArrayList<>());

        int index = 0;

        k %= grid.length * grid[0].length;

        for(int i = grid.length * grid[0].length - k; i < grid.length * grid[0].length * 2 - k; i++)
        {
            int temp = i % (grid.length * grid[0].length);
            int y = temp / grid[0].length, x = temp % grid[0].length;

            if(result.get(index).size() == grid[0].length) index++;

            result.get(index).add(grid[y][x]);
        }

        return result;
    }
}

제출 화면

오늘은 문제가 쉬웠지만 재밌었다.

내일 문제도 재밌었으면 좋겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.

2022년 04월 10일 일요일 - 한강 오랜만!

오늘 올려볼 문제는 682번 Baseball Game 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

오늘 문제는 너무 쉽다구

입력

사진에서도 볼 수 있듯이 String 배열 1개가 입력으로 들어온다.

풀이 및 코드

숫자가 들어오면 저장, D가 들어오면 바로 직전의 숫자의 2배를 해서 저장, +가 들어오면 직전에 저장되어있는 숫자 2개를 더하여 저장, C가 들어오면 직전의 숫자를 삭제하고 이러한 과정을 모두 거친후 저장되어있는 수의 합을 구하는 문제이다.

오늘은 처음부터 정답을 생각해냈다.

Stack에 숫자를 저장하고 규칙에 따라서 진행하고 마지막에 수를 다 더하는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int calPoints(String[] ops) {
        Stack<Integer> s = new Stack<>();

        for(String op : ops)
        {
            if(op.equals("C"))
            {
                s.pop();
            }
            else if(op.equals("D"))
            {
                s.push(s.peek() * 2);
            }
            else if(op.equals("+"))
            {
                int temp = s.pop();
                int last = s.peek() + temp;

                s.push(temp);
                s.push(last);
            }
            else
            {
                s.push(Integer.parseInt(op));
            }
        }

        int result = 0;
        while(!s.isEmpty()) result += s.pop();

        return result;
    }
}

제출 화면

오늘 문제는 너무 쉬웠다.

내일 문제는 적당히 어려우면서 재밌는 문제였으면 좋겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.

2022년 04월 09일 토요일 - 탕수육 마시따

오늘 올려볼 문제는 347번 Top K Frequent Elements 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

n으로 풀려니깐 어렵네요

입력

사진에서도 볼 수 있듯이 int 배열 1개와 int 값 1개가 입력으로 들어온다.

풀이 및 코드

배열의 원소들 중에서 빈도수가 높은 것들 k개를 배열에 담아서 리턴하는 문제다.

오늘은 처음부터 정답을 생각해냈지만 n으로 풀기위해서 고민을 좀 했다.

쉽게 푸는 방식은 priority queue를 사용하여 푸는 방식이다.

n으로 풀기 위해서는 hashmap을 이용하여 원소의 빈도값을 저장하고 arraylist를 만들어 해당 빈도값에 해당하는 원소들을 모두 저장해놓는다.

그리고 빈도수가 높은 수부터 k개 만큼 뽑는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<Integer>[] arr = new ArrayList[nums.length + 1];

        for(int num : nums)
        {
            map.put(num, map.getOrDefault(num, 0) + 1);

            if(arr[map.get(num)] == null) arr[map.get(num)] = new ArrayList<Integer>();

            arr[map.get(num)].add(num);
        }

        int[] result = new int[k];
        int index = 0;

        Loop:
        for(int i = nums.length; i >= 0; i--)
        {
            if(arr[i] == null) continue;

            for(int j = 0; j < arr[i].size(); j++)
            {
                if(map.containsKey(arr[i].get(j)))
                {
                    map.remove(arr[i].get(j));
                    result[index++] = arr[i].get(j);
                }

                if(index == k) break Loop;
            }
        }

        return result;
    }
}

제출 화면

오늘은 n으로 풀려고해서 코드가 좀 복잡해졌다.

내일도 재밌는 문제가 나왔으면 좋겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.

2022년 04월 08일 금요일 - 강남 물가 개비싸

오늘 올려볼 문제는 703번 Kth Largest Element in a Stream 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

생각보다는 좀 어려웠음...

입력

사진에서도 볼 수 있듯이 클래스 초기화용 입력과 클래스 메소드용 입력이 따로 들어온다.

풀이 및 코드

들어온 숫자 중 k번째로 큰 수를 찾아서 리턴하는 문제다.

오늘은 처음부터 정답을 생각해냈다.

Priority Queue를 사용해서 더 큰 수가 들어올 때만 Priority Queue에 넣어서 원하는 수를 구하는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class KthLargest {
    int k;
    PriorityQueue<Integer> pq = new PriorityQueue<>();

    public KthLargest(int k, int[] nums) {
        this.k = k;

        for(int num : nums) pq.add(num);

        while(pq.size() > k) pq.poll();
    }

    public int add(int val) {
        pq.add(val);

        if(pq.size() > k) pq.poll();

        return pq.peek();
    }
}

제출 화면

생각보다는 문제가 어려웠지만 그래도 잘 풀었다.

내일도 잘 풀었으면 좋겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.

2022년 04월 07일 목요일 - 오늘은 생일!!

오늘 올려볼 문제는 1046번 Last Stone Weight 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

뭔가 깔삼하게 풀지는 모태서...

입력

사진에서도 볼 수 있듯이 int 배열 1개가 입력으로 들어온다.

풀이 및 코드

가장 큰 수 2개씩 없애서 마지막에 남는 값을 리턴하는 문제다.

수를 없애는 규칙은 두 수가 같을 때는 둘 다 없애고 아닐 때는 큰 수에서 작은 수를 뺀 값만 남긴다.

오늘은 처음부터 정답을 생각해냈다.

priority queue에 넣고 규칙대로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int lastStoneWeight(int[] stones) {
         PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for(int num : stones) pq.add(num);

        while(pq.size() > 1)
        {
            int n1 = pq.poll();
            int n2 = pq.poll();

            if(n1 == n2) continue;

            pq.add(n1 - n2);
        }

        return pq.size() == 0 ? 0 : pq.poll();
    }
}

제출 화면

오늘 문제는 nlogn으로 풀어서 살짝 멋이 없었다.

내일은 멋있게 풀어봐야겠다!

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.