뒤죽박죽 코딩 이야기

2022년 08월 16일 화요일 - 화요일인데... 월요일같아....

오늘 올려볼 문제는 387번 First Unique Character in a String 이라는 문제이다.

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

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

아오 집에서 문제 풀 때는 블로그 올리기 힘들어서 회사에서 푼 문제만 올리게 되겠네

입력

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

풀이 및 코드

주어진 String의 원소중 unique 한 원소들 중 가장 앞에 있는 index를 찾아 리턴하는 문제다.

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

queue에 index를 넣으면서 원소의 unique여부를 찾는다.

이후 queue에서 index를 빼면서 unique 한지 한 번더 판단하고 리턴하는 식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int firstUniqChar(String s) {
        int[] arr = new int[26];
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < s.length(); i++) {
            if(arr[s.charAt(i) - 'a']++ == 0) {
                q.add(i);
            }
        }
        
        while(!q.isEmpty()) {
            if(arr[s.charAt(q.peek()) - 'a'] == 1) return q.poll();
            q.poll();
        }
        
        return -1;
    }
}

제출 화면

오늘은 문제가 쉬웠는데 이거보다 더 좋은 방법이 있나 찾아봤었다.

하지만 내가 맘에 드는 답을 찾을 수 없었으니 내가 제일 잘 풀었다고 생각해야겠다 ㅋㅋㅋㅋ

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

2022년 08월 11일 목요일 - 아유 요즘 문제가 안풀려 머리가 그냥 굳었어

오늘 올려볼 문제는 98번 Validate Binary Search Tree 이라는 문제이다.

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

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

요즘따라 문제 접근 방식에 대한 실력이 많이 줄은 것 같다...

입력

사진에서도 볼 수 있듯이 Binary Search Tree의 루트 노드가 입력으로 들어온다.

풀이 및 코드

주어진 Binary Search Tree가 Valid한지 판단하여 리턴하는 문제다.

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

Inorder로 트리를 순회하면서 이전 노드의 값을 기억한다.

만약 이전 노드보다 작은 값을 가진 노드가 나오면 false를 리턴하는 식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    int pre = -1;
    boolean hasPre = false;
    boolean result = true;
    public boolean isValidBST(TreeNode root) {
        solve(root);
        return result;
    }
    
    public void solve(TreeNode root) {
        if(root == null) return;
        
        solve(root.left);
        if(hasPre && pre >= root.val) result = false;
        hasPre = true;
        pre = root.val;
        solve(root.right);
    }
}

제출 화면

오늘 문제도 맨처음 봤을 때는 루트 노드부터 시작해서 어디까지 저장해야하나라는 생각으로 쉬운 방법을 생각하지 못 할 뻔했다.

다행히 Inorder를 생각해내서 문제를 쉽게 풀 수 있었던 것 같다.

요즘 들어서 일이 힘들기도하고 문제를 푸는데 시간을 별로 안들이려고 해서 답을 일찍 보기도 해서 그런지 몰라도 머리가 많이 굳은 것 같다.

내가 못풀고 스터디원들이 푸는 경우도 많아졌다. (물론 바라던 바였지만 내가 실력이 떨어져서 생긴 느낌이 더 강하다.)

다실 실력을 되찾고 싶은 생각이 들지만 그렇다고 시간을 들이기는 또 귀찮으니 굉장히 이기적인 상태에 있는 느낌이다.

하지만 그래도 꾸준히하고는 있으니 나중에 알고리즘 각잡고 할 때는 도움이 되지 않을까 생각하고 있긴하다.

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

2022년 08월 03일 수요일 - 그냥 스크린샷은 윈도우에서 찍자...

오늘 올려볼 문제는 729번 My Calendar I 이라는 문제이다.

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

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

아우 그냥 회사에서 스샷만 찍고 올려야겠어... 맥 스크린샷 너무 불편해...

입력

사진에서도 볼 수 있듯이 메소드에 대한 파라매터로 int값 2개씩 입력으로 들어온다.

풀이 및 코드

이중 예약이 되지 않게끔 캘린더 클래스를 구현하는 문제다.

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

TreeMap을 사용해서 근사값을 구하고 이를 통해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class MyCalendar {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    
    public MyCalendar() {
        
    }
    
    public boolean book(int start, int end) {
        int s = -1, e = -1;
        if(map.floorKey(start) != null) {
            s = map.floorKey(start);
        }
        
        if(map.floorKey(--end) != null) {
            e = map.floorKey(end);
        }
        
        // start와 end의 floorKey값이 다르면 무조건 다른 일정과 겹쳐있다는 뜻이라서 이 구문 넣어줌
        if(s - e != 0) return false;
        
        if(s != -1 && start <= map.get(s)) return false;
        
        if(e != -1 && end <= map.get(e)) return false;
        
        map.put(start, end);
        
        return true;
    }
}

제출 화면

오늘 문제는 주석 처리한 부분을 생각하지 못해서 생각보다 많이 틀렸다.

그리고 아오 맥은 스크린샷 매번 위치 지정해주는게 힘들어서 그냥 회사 윈도우에서 스크린샷만 찍어서 올려야겠다.

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

2022년 08월 01일 월요일 - 맥으로 블로그 자동화 성공!!

오늘 올려볼 문제는 62번 Unique Paths 이라는 문제이다.

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

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

어우 굉장히 오랜만에 글을 쓰니깐 감회가 새롭네요

입력

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

풀이 및 코드

로봇이 1, 1에서 출발할 때 오른쪽으로 가거나 아래쪽(숫자로는 위)으로 갈 수 있다고 할 때 주어진 m, n에 도달하는 방법이 몇가지인지 구하여 리턴하는 문제이다.

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

처음에는 bfs로 풀었으나 다시 생각해보니 dp로 풀어도 될 것 같아서 dp로 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] arr = new int[m + 1][n + 1];
        arr[0][1] = 1;
        
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
            }
        }
        
        return arr[m][n];
    }
}

제출 화면

굉장히 오랜만에 블로그 글을 쓰니 좀 새로운 느낌이다.

물론 윈도우에서 만들어뒀던 환경이 아니라서 스크린샷을 찍을 때 시간이 좀 많이 들긴 하지만... 그래도 이정도면....

이는 해결방법을 찾아서 해결해보겠다!

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

2022년 06월 28일 화요일 - 오늘 좀 힘드네용

오늘 올려볼 문제는 1647번 Minimum Deletions to Make Character Frequencies Unique 이라는 문제이다.

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

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

오늘 회사에서 leetcode 들어가는 걸 까먹었다....

입력

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

풀이 및 코드

String을 구성하는 원소들 중 반복하는 개수가 겹치지 않게끔 원소를 지우는데 최소로 지워서 만족하게끔 할 수 있는 개수를 구하여 리턴하는 문제다.

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

일단 String의 원소들 개수를 세고 겹치는게 안생길 때까지 그냥 다 지워줬다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int minDeletions(String s) {
        int[] arr = new int[26];
        HashMap<Integer, Boolean> map = new HashMap<>();
        int result = 0;
        
        for(char c : s.toCharArray()) arr[c - 'a']++;
        
        for(int num : arr)
        {
            if(num == 0) continue;
            
            if(map.containsKey(num))
            {
                while(num > 0 && map.containsKey(num)) 
                {
                    num--;
                    result++;
                }
            }
            map.put(num, true);
        }
        
        return result;
    }
}

제출 화면

오늘 회사에서도 문제를 안 본 것 치고는 문제를 꽤 빨리 풀었다.

내일도 이렇게 잘 풀 수 있었으면 좋겠다.

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

2022년 06월 25일 토요일 - 와 너무 오랜만에 올린다

오늘 올려볼 문제는 665번 Non-decreasing Array 이라는 문제이다.

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

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

요즘 스터디 준비도 있고 문제가 어려운 것도 있고 해서 오랜만에 올린다!

입력

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

풀이 및 코드

원소를 최대 1개만 수정해서 non-decreasing 배열을 만들 수 있는지 판단하는 문제이다.

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

배열을 순회하면서 non-decreasing이 아닐 때 원소를 수정하고 다시 순회해서 판단하는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean checkPossibility(int[] nums) {
        if(nums.length <= 2) return true;
        
        boolean flag = false;
        
        for(int i = 1; i < nums.length; i++)
        {
            if(nums[i - 1] > nums[i])
            {
                if(i == nums.length - 1) return true;
                
                if(nums[i - 1] < nums[i + 1])
                {
                    nums[i] = nums[i - 1];
                }
                else
                {
                    nums[i - 1] = nums[i];
                }
                break;
            }
        }
        
        for(int i = 1; i < nums.length; i++)
        {
            if(nums[i - 1] > nums[i])
            {
                return false;
            }
        }
        
        return true;
    }
}

제출 화면

요즘 개인 프로젝트하랴 스터디 준비하랴 바쁜 나머지 알고리즘을 손놓고 있었던 것 같다.

또 자동화 프로그램을 윈도우 종속적으로 만든것도 어느정도 블로그를 안올리게 되는 것도 있는 것 같다.

그래도 열심히 풀어야지!!

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

2022년 06월 16일 목요일 - 오늘이 100번째 포스팅!!!!

오늘 올려볼 문제는 5번 Longest Palindromic Substring 이라는 문제이다.

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

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

100번째까지 오는데까지 약 반년.... 생각보다는 오래걸렸넹

입력

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

풀이 및 코드

substirng 중에서 palindromic 하면서 가장 긴 substirng을 찾아서 리턴하는 문제다.

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

for문으로 알파벳 하나씩 순회하면서 나아간다.

이 원소를 기준으로 양쪽으로 펼쳐나가며 palindromic한 substirng을 찾는다.

이 substirng중에서 가장 긴 것을 찾는다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public String longestPalindrome(String s) {
        String result = "";
        
        if(s.length() == 1) return s;
        
        if(s.length() == 2) return s.charAt(0) == s.charAt(1) ? s : s.substring(0, 1);
        
        for(int i = 0; i < s.length(); i++)
        {
            int left = i, right = i;
            
            while( 0 <= left && right < s.length() && s.charAt(left) == s.charAt(right))
            {
                left--;
                right++;
            }
            
            if(result.length() < right - left - 1)
            {
                result = s.substring(left + 1, right);
            }
            
            left = i; 
            right = i + 1;
            
            while( 0 <= left && right < s.length() && s.charAt(left) == s.charAt(right)) 
            {
                left--;
                right++;
            }
            
            if(right - left == 1) continue;
            
            if(result.length() < right - left - 1)
            {
                result = s.substring(left + 1, right);
            }
        }
        
        return result;
    }
}

제출 화면

오늘이 leetcode 문제 풀이를 올리는 100번째 포스팅이다!

그동안 열심히 꾸준히 한 내가 자랑스러움을 느끼며...

내일도 문제를 재밌게 풀 수 있었으면 좋겠다!

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

2022년 06월 13일 월요일 - 아니 오늘 왜 월요일임? 수요일 아님?

오늘 올려볼 문제는 120번 Triangle 이라는 문제이다.

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

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

아 자리 바꾸기 시른데 바꿈...

입력

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

풀이 및 코드

삼각형처럼 생긴 배열꼭대기에서 부터 바닥까지 가장 합이 작은 경로를 구하여 리턴하는 문제이다.

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

각 원소에서 위쪽 원소 2개를 비교하여 작은 것을 더해가며 최소값을 찾았다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int size = triangle.size();
        
        for(int i = 1; i < triangle.size(); i++)
        {
            for(int j = 0; j < i + 1; j++)
            {
                if(j == 0)
                {
                    triangle.get(i).set(j, triangle.get(i).get(j) + triangle.get(i - 1).get(j));
                }
                else if(j == i)
                {
                    triangle.get(i).set(j, triangle.get(i).get(j) + triangle.get(i - 1).get(j - 1));
                }
                else
                {
                    triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i - 1).get(j), triangle.get(i - 1).get(j - 1)));
                }
            }
        }
        
        int result = triangle.get(size - 1).get(0);
        for(int i = 1; i < size; i++)
        {
            result = Math.min(result, triangle.get(size - 1).get(i));
        }
        
        return result;
    }
}

제출 화면

옛날에 풀었던 문제와 비슷해서 잊지 않고 풀 수 있었던 것 같다.

내일도 이렇게 멋있게 문제를 풀 수 있었으면 좋겠다.

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