뒤죽박죽 코딩 이야기

2022년 03월 26일 토요일 - 자고 일어났더니 문제가 풀려있네??

오늘 올려볼 문제는 704번 Binary Search 이라는 문제이다.

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

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

전에 풀었던 문제라서 0초 컷

입력

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

풀이 및 코드

이진 탐색으로 int배열에 int 값이 존재하면 그 값이 있는 index, 없다면 -1 을 리턴하는 문제다.

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

진짜 이진 탐색을 사용해서 문제를 풀면 된다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1, middle;

        while(left <= right)
        {
            middle = (left + right) / 2;

            if(nums[middle] == target)
            {
                return middle;
            }
            else if(nums[middle] > target)
            {
                right = middle - 1;
            }
            else
            {
                left = middle + 1;
            }
        }

        return -1;
    }
}

제출 화면

오늘 문제는 너무 쉬웠고 게다가 풀었던 문제라서 별 감흥이 없다.

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

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

2022년 03월 25일 금요일 - 오늘도 잃었다아아 흐규ㅠㅠ

오늘 올려볼 문제는 1029번 Two City Scheduling 이라는 문제이다.

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

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

오늘 좀 길게 풀었다가 힌트 받아서 짧게 풀음

입력

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

풀이 및 코드

문제 설명이 어렵다... 사진 참고해주길 바란다.

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

두 수의 차이를 기준으로 정렬후에 그 기준으로 그리디를 진행하는식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        int n = costs.length / 2;
        int result = 0;

        Arrays.sort(costs, (o1, o2) ->{return (o1[0] - o1[1]) - (o2[0] - o2[1]);});

        for(int i = 0; i < costs.length; i++) result += costs[i][i / n];

        return result;
    }
}

제출 화면

오늘은 문제를 풀긴 했지만 좀 안예쁘게 풀었다가 힌트를 받아서 짧게 풀게되었다.

내일은 한 번에 예쁘게 풀 수 있었으면 좋겠다.

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

2022년 03월 24일 목요일 - 게임을 만들거시야!

오늘 올려볼 문제는 881번 Boats to Save People 이라는 문제이다.

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

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

오늘은 3분 컷

입력

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

풀이 및 코드

최대 2명에 limit 무게까지 태울 수 있는 배가 무한히 있다.

이 때 주어진 사람 몸무게를 통해서 모든 사람들을 태우는데 필요한 가장 적은 배의 수를 구하여 리턴하는 문제다.

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

정렬을 하고 그리디로 문제를 풀었다.

2명까지 태울 수 있다고 했으므로 투포인터도 사용하여 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int result = 0;
        int left = 0, right = people.length - 1;

        while(right > left)
        {
            if(people[right--] + people[left] <= limit) left++;

            result++;
        }

        if(left == right)
            result++;

        return result;
    }
}

제출 화면

오늘은 내가 생각한 대로 문제가 딱 빨리 풀려서 기분이 좋았다.

내일 문제도 이러한 문제가 나왔으면 좋겠다.

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

2022년 03월 23일 수요일 - 왜 아직도 수요일인가 그것이 문제로다

오늘 올려볼 문제는 991번 Broken Calculator 이라는 문제이다.

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

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

요즘 실력이 줄은 거 같은 느낌..

입력

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

풀이 및 코드

start에 2를 곱하거나, 1을 빼는 연산만 해서 target을 만드는데 가장 적은 연산 횟수를 구하여 리턴하는 문제다.

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

그리디로 풀면 될줄 알고 start를 바꾸는 방식으로 접근했었는데 예외가 있었다.

그래서 target을 줄이는 식으로 문제를 풀었더니 문제가 풀렸다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int brokenCalc(int start, int target) {
        if(start >= target) return start - target;

        int result = 0;

        while(start < target)
        {
            if(target % 2 == 1)
            {
                target++;
                result++;
            }

            target /= 2;
            result++;
        }

        return result + start - target;
    }
}

제출 화면

요즘 들어 그렇게 어려운 문제가 아닌데도 문제푸는데 많은 시간이 드는 것 같다.

내일은 적당한 문제를 빠른 시간에 풀 수 있었으면 좋겠다.

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

2022년 03월 22일 화요일 - 바쁘다 바빠~~

오늘 올려볼 문제는 1663번 Smallest String With A Given Numeric Value 이라는 문제이다.

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

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

간단히 적는 법은 힌트를 좀 받음

입력

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

풀이 및 코드

길이가 n이고 a를 1, z를 26으로 봤을 때 모든 원소의 합이 k인 String 중에 사전순으로 가장 빠른 String을 리턴하는 문제다.

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

char 배열을 만들고 뒤에서부터 k를 다써가면서 넣으면 그리디로 문제가 풀리게 된다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public String getSmallestString(int n, int k) {
        char[] arr = new char[n];
        Arrays.fill(arr, 'a');
        k -= n;

        for(int i = n - 1; k > 0; i--)
        {
            arr[i] += Math.min(k, 25);
            k -= 25;
        }

        return new String(arr);
    }
}

제출 화면

오늘 문제는 좀 더럽게 풀었다가 discuss에서 힌트를 받아서 좀 깔끔하게 푼 문제였다.

낼 문제는 좀 더 재밌는 문제였으면 좋겠다.

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

2022년 03월 21일 월요일 - 아니 왜 아직도 월요일???

오늘 올려볼 문제는 763번 Partition Labels 이라는 문제이다.

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

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

오늘 문제 좀 어려워쓰

입력

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

풀이 및 코드

주어진 String을 최대한 많은 Partition으로 나누는데 한 Partition에 포함된 원소들이 다른 Partition에는 존재하면 안된다고 할 때 Partition들의 크기를 담은 List를 리턴하는 문제다.

오늘은 시행착오를 겪다가 문제를 풀었다.

Stack을 사용할까 했는데 그냥 for문 한 번 더 도는 방식으로 구현하기로 했다.

dp라는 배열에는 list넣을 index를 저장하고 있게끔 했다.

주어진 String을 읽으면서 중복된 원소가 나오면 중복된 원소부터 이번 원소까지 중복된 원소가 가지고 있는 index로 모두 바꾸어주고 중복된 원소의 위치를 현재 원소로 바꾸어주었다.

후에 dp를 순회하면서 list에 size를 넣어주는 방식으로 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public List<Integer> partitionLabels(String input) {
        HashMap<Character, Integer> map = new HashMap<>();
        int[] dp = new int[input.length()];
        int index = 0;

        for(int i = 0; i < input.length(); i++)
        {
            char now = input.charAt(i);

            if(map.containsKey(now))
            {
                for(int j = map.get(now) + 1; j <= i; j++)
                {
                    dp[j] = dp[map.get(now)];
                }
                map.put(now, i);
            }
            else
            {
                dp[i] = index++;
                map.put(now, i);
            }
        }

        List<Integer> result = new ArrayList<>();
        int pre = 0;
        for(int i = 0; i < input.length(); i++)
        {
            if(dp[pre] != dp[i])
            {
                result.add(i - pre);
                pre = i;
            }
        }
        result.add(input.length() - pre);

        return result;
    }
}

제출 화면

생각보다 어려웠는데 그래도 풀어서 다행인 것 같다.

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

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

2022년 03월 20일 일요일 - 오늘 칩 많이 잃어따.... 흐규

오늘 올려볼 문제는 1007번 Minimum Domino Rotations For Equal Row 이라는 문제이다.

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

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

뭔가 안될거 같았는데 돼서 빨리 풀음 ㅋㅋㅋㅋ

입력

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

풀이 및 코드

각각 tops와 bottoms는 1 ~ 6 사이의 숫자 하나를 가지고 있는데 tops와 bottoms을 교환해서 모두 같은 숫자로만 이루어진 배열을 만들 수 있다면 최소한의 교환 개수를 리턴하는 문제이다. 교환이 불가능하다면 -1을 리턴한다.

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

일단 숫자의 빈도를 가지고 있는 배열을 선언하고 숫자의 개수를 저장한다.

숫자의 개수가 배열의 길이보다 긴지 판단하고 for문을 돌면서 적은 교환 개수를 구하는 식으로 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        int[] t = new int[7];
        int[] b = new int[7];

        for(int i = 0; i < tops.length; i++)
        {
            t[tops[i]]++;
            b[bottoms[i]]++;
        }

        int result = 20005;

        Loop:
        for(int i = 1; i < t.length; i++)
        {
            if(t[i] + b[i] >= tops.length)
            {
                int tnum = 0, bnum = 0;
                for(int j = 0; j < tops.length; j++)
                {
                    if(tops[j] == i && bottoms[j] == i) continue;
                    else if(tops[j] == i && bottoms[j] != i) tnum++;
                    else if(tops[j] != i && bottoms[j] == i) bnum++;
                    else continue Loop;
                }

                result = Math.min(result, Math.min(tnum, bnum));
            }
        }

        if(result == 20005)
            result = -1;

        return result;
    }
}

제출 화면

오늘 문제도 더 좋게 풀 수 있었는데 조금 나쁘게 푼 것 같아서 아쉽다.

내일 문제는 비상하게 풀 수 있었으면 좋겠다.

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

2022년 03월 17일 목요일 - 아니 왤케 시간이 안가지?

오늘 올려볼 문제는 856번 Score of Parentheses 이라는 문제이다.

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

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

와 오늘 문제 못 푸는 줄

입력

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

풀이 및 코드

주어진 괄호들의 score를 구하는 문제이다.

() 이 괄호는 1점 괄호 옆에 괄호가 붙은 AB 방식이면 A + B로 계산하고 A를 B가 포함한다면 B는 2 * A와 같이 계산하는 방식이다.

오늘은 꽤 시행착오를 겪다가 문제를 풀었다.

각 괄호마다 level이 있다고 생각하고 (여는 괄호가 나오면 level + 1, 닫는 괄호가 나오면 level - 1) 각 레벨에 값을 저장해줬다.

만약 해당 레벨에 값이 존재한다면 2를 곱하고 없다면 1을 더해주는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int scoreOfParentheses(String input) {
        Stack<Integer> s = new Stack<Integer>();
        int[] level = new int[26];
        int result = 0, lv = 0;
        for(int i = 0; i < input.length(); i++)
        {
            if(input.charAt(i) == '(')
                lv++;
            else
            {
                if(level[lv] == 0)
                    level[lv - 1] += 1;
                else
                {
                    level[lv - 1] += level[lv] * 2;
                    level[lv] = 0;
                }

                lv--;
            }
        }

        return level[0];
    }
}

제출 화면

오늘은 뭔가 문제가 어려워서 꽤 힘들게 풀었다..

그래도 풀었으니 다행이라 생각한다..

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