뒤죽박죽 코딩 이야기

2022년 2월 25일 금요일 - 역시 금요일이 최고지

오늘 올려볼 문제는 165번 Compare Version Numbers 이라는 문제이다.

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

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

아니 제약조건 잘못봐서 더 안좋게 품...

입력

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

풀이 및 코드

주어진 String 들은 각각 버전을 나타내는 데 이를 비교하여 리턴하는 문제이다.

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

사실 별거없이 직관적으로 문제를 풀면된다.

다만 난 제약조건을 잘못봐서 BigInteger를 사용해서 풀었지만 Integer를 사용해서 풀어도 된다.

이제 코드를 봐보자!

import java.math.BigInteger;
class Solution {
    public int compareVersion(String version1, String version2) {
        String[] arr1 = version1.split("[.]");
        String[] arr2 = version2.split("[.]");

        BigInteger b1 = new BigInteger("0");
        BigInteger b2 = new BigInteger("0");

        for(int i = 0; i < (arr1.length > arr2.length ? arr1.length : arr2.length); i++)
        {
            if(i >= arr1.length)
            {
                b1 = BigInteger.valueOf(0);
            }
            else
            {
                b1 = new BigInteger(arr1[i]);
            }

            if(i >= arr2.length)
            {
                b2 = BigInteger.valueOf(0);
            }
            else
            {
                b2 = new BigInteger(arr2[i]);
            }

            if(b1.compareTo(b2) > 0)
            {
                return 1;
            }
            else if(b1.compareTo(b2) < 0)
            {
                return -1;
            }
        }

        return 0;
    }
}

제출 화면

오늘은 더 메모리를 적게 쓰고 풀 수 있었지만 제약 조건을 제대로 안읽어서 메모리를 더 쓴 문제다.

다음에는 제약조건을 제대로 읽어야겠다.

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

2022년 2월 24일 목요일 - 와우 피곤한걸?

오늘 올려볼 문제는 148번 Sort List 이라는 문제이다.

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

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

메모리 O(1)로 푸는건 너무 귀찮아서 걍 O(N)으로 품ㅋㅋㅋ

입력

사진에서도 볼 수 있듯이 리스트 하나가 입력으로 들어온다.

풀이 및 코드

주어진 리스트를 정렬하고 리턴하는 문제이다.

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

리스트로부터 모든 값을 뽑아서 ArrayList에 저장하고 정렬한다.

그리고 이를 다시 리스트로 만드는 식으로 구현했다.

이제 코드를 봐보자!

class Solution {
    public ListNode sortList(ListNode head) {
        ArrayList<Integer> arr = new ArrayList<Integer>();

        if(head == null)
            return head;

        while(head != null)
        {
            arr.add(head.val);
            head = head.next;
        }

        Collections.sort(arr);

        ListNode root = new ListNode();
        ListNode result = root;

        for(int i = 0; i < arr.size(); i++)
        {
            ListNode temp = new ListNode();
            root.next = temp;
            root = temp;
            root.val = arr.get(i);
        }

        return result.next;
    }
}

제출 화면

오늘은 더 까다롭게 풀 수 있는 문제였지만 그냥 편하게 풀었다.

사실 귀찮지만 않았다면 시도했을 것이다.

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

2022년 2월 23일 수요일 - 오늘 너무 졸린데...

오늘 올려볼 문제는 133번 Clone Graph 이라는 문제이다.

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

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

오늘 문제는 꽤 귀찮았는데 안귀찮게 푸는 방법이 이써따...

입력

사진에서도 볼 수 있듯이 그래프의 시작 노드 하나가 입력으로 들어온다.

풀이 및 코드

주어진 그래프를 그대로 복사하여 리턴하는 문제다.

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

주어진 그래프를 순회하는 대로 그래프를 만드는 것이다.

이 때 계속 new를 사용하면 제대로 된 복사가 되지 않으므로 val를 기준으로 노드를 저장하고 있다가 연결해주는 방식으로 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    Node result;
    Queue<Node> q = new LinkedList<Node>();

    Node[] nodes = new Node[105];
    boolean[] visit = new boolean[105];

    public Node cloneGraph(Node node) {
        if(node == null)
            return null;

        if(node.neighbors.size() == 0)
            return new Node(node.val);

        result = new Node(node.val);
        nodes[result.val] = result;

        dfs(node);

        return result;
    }

    public void dfs(Node root)
    {
        if(visit[root.val])
            return;

        visit[root.val] = true;

        Node temp;
        for(int i = 0; i < root.neighbors.size(); i++)
        {
            temp = result;

            if(nodes[root.neighbors.get(i).val] == null)
                nodes[root.neighbors.get(i).val] = new Node(root.neighbors.get(i).val);
            result.neighbors.add(nodes[root.neighbors.get(i).val]);
            result = result.neighbors.get(i);
            dfs(root.neighbors.get(i));

            result = temp;
        }
    }
}

제출 화면

오늘은 문제가 귀찮았다.

하지만 귀찮지 않게 푸는 방법이 있었던 것을 보면 뭔가 귀찮다 싶으면 짧게 풀 수도 있겠구나 생각을 해야겠다.

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

2022년 2월 22일 화요일 - 일주일의 시작은 쉬운문제로 해주는 leetcode... 당신 친절할지도..?

오늘 올려볼 문제는 171번 Excel Sheet Column Number 이라는 문제이다.

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

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

아니 왜 A를 1로 둬서 귀찮게 하는데

입력

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

풀이 및 코드

A를 1로, Z를 26으로 봐서 주어진 String을 26진법으로 봐서 숫자로 변환하고 리턴하는 문제이다.

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

각 index에 해당하는 char의 아스키코드 값을 구하고 처리하는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int titleToNumber(String columnTitle) {
        int result = 0;

        for(int i = 0; i < columnTitle.length(); i++)
        {
            result += (int)(Math.pow(26, columnTitle.length() - 1 - i) * (columnTitle.charAt(i) - 'A' + 1));
        }

        return result;
    }
}

제출 화면

오늘도 문제가 너무 쉬워서 빨리 풀었다.

내일은 적당히 어려우면서 재밌는 문제가 나오길 바란다.

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

2022년 2월 21일 월요일 - 아니 왜 벌써 월요일?

오늘 올려볼 문제는 169번 Majority Element 이라는 문제이다.

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

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

1분컷 해버리기

입력

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

풀이 및 코드

주어진 배열의 원소 중 빈도수가 배열 총 원소들 개수의 절반 이상인 원소를 찾아서 리턴하는 문제이다.

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

해쉬맵에 개수를 넣고 개수가 절반 이상이 되면 리턴하는 식으로 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        int size = nums.length / 2 + (nums.length % 2 == 0 ? 0 : 1);

        for(int num : nums)
        {
            if(!map.containsKey(num))
                map.put(num, 0);

            map.put(num, map.get(num) + 1);

            if(map.get(num) >= size)
                return num;
        }

        return 0;
    }
}

제출 화면

오늘은 문제가 너무 쉬워서 빨리 풀었다.

적당히 어려우면서 재밌는 문제가 나오길 바란다.

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

2022년 2월 20일 일요일 - 오늘은 풀었다!

오늘 올려볼 문제는 1288번 Remove Covered Intervals 이라는 문제이다.

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

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

와씨 오늘은 풀어서 다행이다 진짜

입력

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

풀이 및 코드

주어진 2차원 int 배열은 범위를 저장하고 있는 배열들을 저장하는 배열이다.

이 범위들 중 완전히 포함되는 범위를 없애고 남아있는 범위들의 개수를 리턴하는 문제이다.

ex) [1, 5]과 [2, 4]가 있다면 [2, 4]는 [1, 5]에 완전히 포함된다.

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

먼저 왼쪽 범위는 오름차순, 만약 왼쪽 범위가 같다면 오른쪽 범위는 내림차순으로 정렬을 했다.

이후 맨처음 범위를 저장하는 변수를 만든다.

그리고 for문을 돌면서 저장한 값과 비교를 한다.

만약 저장한 범위에 포함된다면 개수를 하나 줄이고 계속 진행한다.

만약 저장한 범위에 포함되지 않는다면 현재 범위를 저장하고 계속 진행한다.

위 과정이 가능한 이유는 정렬을 했기 때문에 가능하므로 정렬을 해주는 것이 중요하다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        // 2차원 배열 정렬, 0번째 원소는 오름차순, 1번째 원소는 내림차순
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override public int compare(int[] o1, int[] o2)
            {
                if(o1[0] == o2[0])
                {
                    return o2[1] - o1[1];
                }
                else
                {
                    return o1[0] - o2[0];
                }
            }
        });

        // result에는 범위들의 개수를 저장해놓는다.
        int result = intervals.length;
        int[] temp = intervals[0];

        for(int i = 1; i < intervals.length; i++)
        {
            int[] now = intervals[i];

            // 저장한 범위에 포함되면 result - 1
            if(temp[0] <= now[0] && now[1] <= temp[1])
            {
                result--;
            }
            // 포함되지 않으면 저장한 범위 업데이트
            else
            {
                temp = now;
            }
        }

        return result;
    }
}

제출 화면

오늘은 되게 오랜만에 오늘의 문제를 푼 것 같았다. 해봤자 3일이긴 하지만 말이다. ㅋㅋㅋㅋㅋ

하여튼 오늘은 문제를 풀어서 다행인 것 같다.

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

2022년 2월 19일 토요일 - 아니 어제 오늘 문제 너무 어렵네...

오늘 올려볼 문제는 343번 Integer Break 이라는 문제이다.

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

오늘도 LeetCode 사이트 오늘의 문제를 못풀어서 다른 문제를 가지고 왔다.

아니 이틀 연속으로 오늘의 문제를 못풀지는 몰랐지... 그래서 다른 문제라도 올려야겠다 싶어서 올림... ㅋㅋㅋㅋ

입력

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

풀이 및 코드

어떤 수들의 합이 n인 수들의 합이나 곱중에서 가장 큰 값을 찾고 리턴하는 문제다.

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

일단 합이 n이 될 수 있는 수들의 개수는 2 ~ n 개이다.

즉 개수로 n을 나누고 나머지를 1씩 배분해주고 계산하면 답을 얻을 수 있다.

예를 들어 n은 11이고 개수는 3이라고 하면 각 수들을 3을 가지고 나머지가 2이므로 2개의 수에다가 1씩 더하면 3 4 4 가 될 것이다.

즉 (몫^(개수 - 나머지))*((몫 + 1)^나머지)를 계산하면서 최대값을 찾으면 된다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int integerBreak(int n) {
        int max = 0;

        for(int i = 2; i <= n; i++)
        {
            int share = n / i;
            int remain = n % i;

            int result = (int)(Math.pow(share , i - remain) * Math.pow(share + 1 , remain));

            if(result > max)
            {
                max = result;
                continue;
            }

            break;
        }

        return max;
    }
}

제출 화면

오늘과 어제는 문제를 못풀었어서 너무 스트레스 받았다. 사실 내 실력이 부족한 거였지만 뭐랄까 나에게 화가 나는 기분이었다...

아무렴 어때 앞으로 잘하면 된다.

이번 실패를 기억하고 앞으로는 더욱 잘해볼 것이다.

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