뒤죽박죽 코딩 이야기

2022년 05월 09일 월요일 - 아우 기침이 안멈춰

오늘 올려볼 문제는 17번 Letter Combinations of a Phone Number 이라는 문제이다.

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

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

귀찮지만 쉬운 문제

입력

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

풀이 및 코드

주어진 번호들로 만들 수 있는 문자열들을 모두 찾아서 리턴하는 문제다.

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

String 배열을 하나 만들어서 각 번호에 해당하는 문자열을 넣어두고 재귀를 사용해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    String[] arr = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> result = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits.equals("")) return result;

        solve(0, digits, "");

        return result;
    }

    public void solve(int index, String digits, String combi)
    {
        if(index == digits.length())
        {
            result.add(combi);
        }
        else
        {
            int num = digits.charAt(index) - '0';

            for(int i = 0; i < arr[num].length(); i++)
            {
                solve(index + 1, digits, combi + arr[num].charAt(i));
            }
        }
    }
}

제출 화면

오늘 문제는 미디엄을 가장한 이지 문제라서 쉽게 풀었다.

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

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

2022년 05월 08일 일요일 - 여행때문에 오랜만에 글을 씀미당

오늘 올려볼 문제는 341번 Flatten Nested List Iterator 이라는 문제이다.

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

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

생각보다는 쉽네?

입력

입력을 설명하기 애매한 문제다. 문제를 참고해주기 바란다.

풀이 및 코드

주어진 리스트를 펼쳐주는 iterator를 구현하는 문제다.

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

재귀를 사용해서 리스트를 펼치는 방식으로 구현했다.

이제 코드를 봐보자!

풀이코드

public class NestedIterator implements Iterator<Integer> {
    ArrayList<Integer> arr = new ArrayList<>();
    List<NestedInteger> nestedList;

    int index = 0;

    public NestedIterator(List<NestedInteger> nestedList) {
        this.nestedList = nestedList;
        AddAll();
    }

    @Override
    public Integer next() {
        return arr.get(index++);
    }

    @Override
    public boolean hasNext() {
        return index < arr.size();
    }

    public void AddAll()
    {
        for(int i = 0; i < nestedList.size(); i++)
        {
            Add(nestedList.get(i));
        }
    }

    public void Add(NestedInteger ni)
    {
        if(ni.isInteger())
        {
            arr.add(ni.getInteger());
        }
        else
        {
            for(int i = 0; i < ni.getList().size(); i++)
            {
                Add(ni.getList().get(i));
            }
        }
    }
}

제출 화면

오랜만에 글을 쓰니 느낌이 좀 새로운 것 같다.

내일은 구현 문제말고 푸는 맛이 있는 문제가 나왔으면 좋겠다.

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

2022년 05월 04일 수요일 - 와 4일동안 쉰다!

오늘 올려볼 문제는 1679번 Max Number of K-Sum Pairs 이라는 문제이다.

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

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

제약조건 잘못 읽어서 귀찮아씀

입력

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

풀이 및 코드

주어진 배열에 2가지 원소를 뽑아 합이 k가 되는 가지수가 몇가지가 있는지 계산하여 리턴하는 문제다.

단 한 번 세었던 원소들은 다시 세지 않는다.

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

HashMap에 원소들을 넣고 합이 k가 되는 원소가 있는지 판단하기만 했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int maxOperations(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int result = 0;

        for(int num : nums)
        {
            if(map.getOrDefault(k - num, 0) > 0)
            {
                result++;
                map.put(k - num, map.get(k - num) - 1);
            }
            else
            {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
        }

        return result;
    }
}

제출 화면

미디엄치고 너무 쉬웠다.

내일은 적당히 어렵고 재밌는 문제가 나왔으면 정말 좋겠네~~ 정말 좋겠네

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

2022년 05월 03일 화요일 - 오늘은 마치 목요일~

오늘 올려볼 문제는 581번 Shortest Unsorted Continuous Subarray 이라는 문제이다.

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

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

너무 꼼수로 풀긴 했어...

입력

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

풀이 및 코드

배열 중 정렬하면 모든 배열이 정렬되는 상태가 되는 subarray중 가장 짧은 것의 길이를 구하는 문제다.

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

조금 많이 꼼수이긴 하지만 배열을 정렬하고 원래 주어진 배열과 다른 부분을 찾아서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] sorted = nums.clone();

        Arrays.sort(sorted);

        int left = 100000, right = -1;

        for(int i = 0; i < nums.length; i++)
        {
            if(nums[i] != sorted[i])
            {
                left = i;
                break;
            }
        }

        for(int i = nums.length - 1; i >= 0; i--)
        {
            if(nums[i] != sorted[i])
            {
                right = i;
                break;
            }
        }

        if(right <= left) return 0;

        return right - left + 1;
    }
}

제출 화면

사실 leetcode가 관대해서 그렇지 보통 다른 곳에서는 time limit exceed를 뜨게해줄만한 코드다.

내일은 정석적으로 섹시하게 풀 수 있었으면 좋겠다.

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

2022년 05월 02일 월요일 - 마스크를 벗는 날이 와따!!!

오늘 올려볼 문제는 905번 Sort Array By Parity 이라는 문제이다.

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

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

쉽고도 쉽구나

입력

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

풀이 및 코드

짝수를 앞에 오게끔 정렬하여 리턴하는 문제다.

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

투포인터를 사용해서 스왑해주는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int right = nums.length - 1;

        for(int left = 0 ; left < right; left++)
        {
            while(left < right && nums[right] % 2 == 1) right--;

            if(nums[left] % 2 == 1)
            {
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;

                right--;
            }
        }

        return nums;
    }
}

제출 화면

오늘은 문제가 너무 쉬웠다.

내일은 적당히 어려운 문제가 나왔으면 좋겠다.

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

2022년 05월 01일 일요일 - 오랜만에 글쓰는 느낌인데..

오늘 올려볼 문제는 844번 Backspace String Compare 이라는 문제이다.

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

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

아니 요즘 미디엄도 너무 어려워

입력

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

풀이 및 코드

#을 백스페이스로 봤을 때 두 문자열이 같은지 판단하는 문제다.

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

Stack에 문자들을 저장하면서 #이 나오면 Stack에서 저장한 문자를 pop하는 방식으로 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean backspaceCompare(String s, String t) {
        Stack<Character> s1 = new Stack<Character>();
        Stack<Character> s2 = new Stack<Character>();

        for(int i = 0; i < s.length(); i++)
        {
            if(s.charAt(i) != '#')
            {
                s1.push(s.charAt(i));
            }
            else
            {
                if(!s1.isEmpty())
                    s1.pop();
            }
        }

        for(int i = 0; i < t.length(); i++)
        {
            if(t.charAt(i) != '#')
            {
                s2.push(t.charAt(i));
            }
            else
            {
                if(!s2.isEmpty())
                    s2.pop();
            }
        }

        while(!s1.isEmpty() && !s2.isEmpty()) if(s1.pop() != s2.pop()) return false;

        if(!s1.isEmpty() || !s2.isEmpty()) return false;

        return true;
    }
}

제출 화면

최근에 미디엄 문제도 어려워서 블로그를 많이 못 썼는데 오늘은 쉬운 문제가 나와서 쓸 수 있어 다행인거 같다.

내일은 미디엄 문제도 올릴 수 있게 잘 풀었으면 좋겠다.

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

2022년 04월 26일 화요일 - 배포가 얼마 안남아서 두렵다....

오늘 올려볼 문제는 1584번 Min Cost to Connect All Points 이라는 문제이다.

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

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

딱보자마자 아 귀찮겠구나 싶었다

입력

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

풀이 및 코드

주어진 점들로 MST를 만들고 모든 선들의 길이의 합을 구하는 문제다.

오늘은 시행착오를 겪었다.

그저 브루트 포스로 풀면 될 줄 알았으나 MST 조건을 만족하지 못해서 prim 알고리즘을 활용해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int minCostConnectPoints(int[][] points) {
        boolean[] visit = new boolean[points.length];
        PriorityQueue<Node> pq = new PriorityQueue<>();

        visit[0] = true;

        {
            int[] p1 = points[0];
            for(int j = 1; j < points.length; j++)
            {
                int[] p2 = points[j];

                int dist = Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);

                pq.add(new Node(0, j, dist));
            }
        }

        int result = 0;
        int count = 1;

        while(true)
        {
            Node now = pq.poll();

            if(count == points.length) break;

            if(visit[now.i] && visit[now.j]) continue;

            if(!visit[now.i] && visit[now.j])
            {
                visit[now.i] = true;
                count++;

                for(int i = 0; i < points.length; i++)
                {
                    if(!visit[i])
                    {
                        int[] p1 = points[now.i], p2 = points[i];

                        int dist = Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);

                        pq.add(new Node(i, now.i, dist));
                    }
                }
            }
            else if(visit[now.i] && !visit[now.j])
            {
                visit[now.j] = true;
                count++;

                for(int i = 0; i < points.length; i++)
                {
                    if(!visit[i])
                    {
                        int[] p1 = points[now.j], p2 = points[i];

                        int dist = Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);

                        pq.add(new Node(i, now.j, dist));
                    }
                }
            }

            result += now.dist;
        }

        return result;
    }
}


class Node implements Comparable<Node>{
    int i, j;
    int dist;

    public Node(int i, int j, int dist)
    {
        this.i = i;
        this.j = j;
        this.dist = dist;
    }

    @Override
	public int compareTo(Node n) {
        return this.dist - n.dist;
	}
}

제출 화면

오늘은 문제가 생각보다 어려웠다.

내일은 깔삼하게 잘 풀 수 있었으면 좋겠다.

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