뒤죽박죽 코딩 이야기

2022년 03월 16일 수요일 - 으어어 왜 아직 수요일이야

오늘 올려볼 문제는 946번 Validate Stack Sequences 이라는 문제이다.

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

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

아 숏코딩하려고 했는데 뭔가 좀 맘에 안듦

입력

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

풀이 및 코드

pushed 배열은 Stack에 넣고 popped 배열처럼 pop 할 수 있는지 판단하여 리턴하는 문제다.

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

Stack에 pushed를 넣으면서 popped랑 비교만 하면되는 쉬운 문제이다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> s = new Stack<Integer>();
        int index = 0, i = 0;

        while(i < pushed.length && s.push(pushed[i]) == pushed[i++])
            for(; !s.isEmpty() && s.peek() == popped[index]; index++) s.pop();

        return popped.length == index;
    }
}

제출 화면

올린 코드는 줄 좀 줄여본다고 저렇게 썼지만 더 읽기 좋게도 풀 수 있다.

오늘 문제는 너무 쉬웠어서 내일 문제는 재밌었으면 좋겠다.

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

2022년 03월 15일 화요일 - 오늘 좀 피곤쓰~

오늘 올려볼 문제는 1249번 Minimum Remove to Make Valid Parentheses 이라는 문제이다.

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

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

어려워보였는데 생각보다 쉬웠음!

입력

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

풀이 및 코드

주어진 괄호를 포함하는 String에서 valid한 괄호로만 이루어진 String을 만드는데 최대한 적은 수의 괄호를 제거하여 만들고 리턴하는 문제다.

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

처음에는 boolean 배열을 만들어서 valid한지 판단하는 방식으로 풀었는데 또 다른 방식도 있을까 싶어 다른 방식으로도 풀었다.

String을 char 배열로 만들고 일단 모든 괄호들은 공백으로 바꾼다.

나중에 valid한 괄호의 쌍이 나오면 해당하는 괄호들을 다시 넣어주고 마지막으로 모든 공백을 빈 값으로 바꿔주어 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public String minRemoveToMakeValid(String input) {
        char[] arr = input.toCharArray();
        Stack<Integer> s = new Stack<Integer>();
        for(int i = 0; i < arr.length; i++)
        {
            if(arr[i] == '(')
            {
                s.push(i);
                arr[i] = ' ';
            }
            else if(arr[i] == ')')
            {
                if(!s.isEmpty())
                    arr[s.pop()] = '(';
                else
                    arr[i] = ' ';
            }
        }


        return new String(arr).replaceAll(" ", "");
    }
}

제출 화면

생각보다 풀이 속도가 느려서 의외였던 문제였다.

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

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

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

오늘 올려볼 문제는 71번 Simplify Path 이라는 문제이다.

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

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

~~오늘 문제 뭔말인가 싶었는데... 쉬웠다.. ~~

입력

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

풀이 및 코드

주어진 절대경로를 단순화하여 리턴하는 문제다.

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

/를 기준으로 split 하고 . 은 넘기고 .. 은 ArrayList에 담긴 맨 마지막 값을 빼는 식으로 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public String simplifyPath(String path) {
        ArrayList<String> arr = new ArrayList<String>();
        String[] input = path.split("/");

        for(int i = 0; i < input.length; i++)
        {
            if(input[i].equals("."))
                continue;
            else if(input[i].equals(".."))
            {
                if(arr.size() > 0)
                    arr.remove(arr.size() - 1);
            }
            else if(input[i].equals(""))
                continue;
            else
                arr.add(input[i]);
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < arr.size(); i++)
        {
            sb.append("/");
            sb.append(arr.get(i));
        }

        if(sb.length() == 0)
            sb.append("/");

        return sb.toString();
    }
}

제출 화면

문제 이해를 못했어서 푸는데 시간이 좀 걸렸는데 이해하고 나서는 굉장히 쉽게 풀었다.

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

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

2022년 03월 13일 일요일 - 왜 벌써 일요일?

오늘 올려볼 문제는 20번 Valid Parentheses 이라는 문제이다.

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

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

오늘은 문제가 너무 쉽다

입력

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

풀이 및 코드

주어진 괄호들이 valid 한지 판단하여 리턴하는 문제다.

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

괄호 문제들은 스택을 써서 푸는게 공식같은 것이므로 스택을 활용하여 이 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean isValid(String input) {
        Stack<Character> s = new Stack<Character>();

        for(int i = 0; i < input.length(); i++)
        {
            char now = input.charAt(i);
            if(now == '(')
            {
                s.push(++now);
            }
            else if(now == '{' || now == '[')
            {
                ++now;
                s.push(++now);
            }
            else
            {
                if(s.isEmpty())
                    return false;
                if(s.peek() != now)
                    return false;
                s.pop();
            }
        }

        if(!s.isEmpty())
            return false;

        return true;
    }
}

제출 화면

오늘 문제는 자료구조 배울 때 배우는 알고리즘 문제라서 너무 쉬웠다.

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

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

2022년 03월 12일 토요일 - 칩 셔플 은근 어렵다잉...

오늘 올려볼 문제는 138번 Copy List with Random Pointer 이라는 문제이다.

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

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

이상한 예외처리 문을 적어서 더 빨리 풀 수 있는거 좀 늦게 풀었다..

입력

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

풀이 및 코드

주어진 Linked List를 깊은 복사하여 리턴하는 문제이다.

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

주어진 Linked List들을 ArrayList에 다 넣고 각 val을 ArrayList index로 바꾸어주었다.

그 후에 ArrayList에 들어있는 Node들에 next와 random 값을 업데이트 해주는 방식으로 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null)
            return null;
        Node start = head;
        ArrayList<Node> arr = new ArrayList<Node>();
        for(int i = 0; head != null; i++)
        {
            arr.add(new Node(head.val));
            head.val = i;
            head = head.next;
        }

        head = start;
        arr.get(0).random = head.random == null ? null : arr.get(head.random.val);
        head = head.next;
        for(int i = 1; i < arr.size(); i++)
        {
            arr.get(i - 1).next = arr.get(i);
            arr.get(i).random = head.random == null ? null : arr.get(head.random.val);
            head = head.next;
        }

        return arr.get(0);
    }
}

제출 화면

오늘 문제는 내가 잘못된 예외처리 구문을 하나 넣어서 조금 시행착오를 겪었다.

하지만 금방 해결했다. ㅋㅋㅋㅋㅋ

내일 문제도 재밌는 문제가 나오길 바란다.

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

2022년 03월 11일 금요일 - T1 15 연승!!

오늘 올려볼 문제는 61번 Rotate List 이라는 문제이다.

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

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

오늘 문제 꽤 재밌었음!

입력

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

풀이 및 코드

k 만큼 Linked List를 돌려서 리턴하는 문제다.

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

일단 리스트의 끝을 리스트의 처음과 연결하고 리스트의 길이를 구한다.

그리고 리스트 길이 - (k % 리스트 길이) 만큼 노드를 이동시키고 리스트를 끊으면 리스트를 돌린 것과 같은 효과가 난다.

위와 같은 방식으로 해당 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null) return head;

        ListNode node = head;
        int index;

        for(index = 1; node.next != null; index++) node = node.next;
        node.next = head;

        for(int i = 0; i < index - (k % index); i++) node = node.next;
        head = node.next;
        node.next = null;

        return head;
    }
}

제출 화면

오늘 문제는 꽤나 재밌게 풀었다.

내일도 이런 문제가 나왔으면 좋겠다!

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

2022년 03월 10일 목요일 - 오늘 처음으로 미리 풀어둔 문제가 오늘의 문제로 나왔다!!

오늘 올려볼 문제는 2번 Add Two Numbers 이라는 문제이다.

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

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

오늘은 BigInteger 안쓰고 풀어봤다

입력

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

풀이 및 코드

주어진 Linked List 를 뒤집은 수를 더하고 Linked List로 만들어 리턴하는 문제다.

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

Queue 2개를 만들어 각자 Linked List의 원소들을 넣는다.

그리고 Queue에서 값을 뽑은 다음 합하여 Linked List를 만드는 식으로 구현했다.

이제 코드를 봐보자!

풀이코드

import java.math.BigInteger;

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Queue<Integer> s1 = new LinkedList<Integer>();
        Queue<Integer> s2 = new LinkedList<Integer>();

        for(int i = 0; l1 != null; i++)
        {
            s1.add(l1.val);
            l1 = l1.next;
        }

        for(int i = 0; l2 != null; i++)
        {
            s2.add(l2.val);
            l2 = l2.next;
        }

        ListNode result = new ListNode();
        ListNode node = result;
        int next = 0;

        while(!s1.isEmpty() || !s2.isEmpty())
        {
            int now = next + (s1.isEmpty() ? 0 : s1.poll()) + (s2.isEmpty() ? 0 : s2.poll());
            node.next = new ListNode(now % 10);
            next = now / 10;
            node = node.next;
        }

        if(next > 0)
        {
            node.next = new ListNode(next);
            node = node.next;
        }

        return result.next;
    }
}

제출 화면

오늘은 풀었던 문제지만 메모리를 더 적게 써보려고 다시 풀었다. (근데 집에서 돌리니깐 다시 메모리 높아짐 ㅡㅡ)

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

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

2022년 03월 09일 수요일 - 아 쉬는날 너무 조아

오늘 올려볼 문제는 82번 Remove Duplicates from Sorted List II 이라는 문제이다.

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

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

오늘은 시간하고 공간을 좀 아껴보겠다고 좀 더럽게 풀었다...

입력

사진에서도 볼 수 있듯이 정렬된 Linked List 하나가 입력으로 들어온다.

풀이 및 코드

Linked List 에서 중복된 원소들은 모두 제거하여 리턴하는 문제다.

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

그냥 전에 나왔던 값을 기준으로 Linked List에 있는 중복된 원소를 삭제해주는 방식이다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null)
            return null;

        boolean unique = true;
        int pre = head.val;
        ListNode temp = head;
        ListNode node = new ListNode();
        ListNode result = node;

        head = head.next;

        while(head != null)
        {
            if(head.val == pre)
            {
                unique = false;
            }
            else
            {
                if(unique)
                {
                    node.next = temp;
                    node = node.next;
                    node.next = null;
                }

                pre = head.val;
                temp = head;
                unique = true;
            }

            head = head.next;
        }
        if(unique)
            node.next = temp;

        return result.next;
    }
}

제출 화면

사실 배열이나 HashMap을 사용하면 더 쉽게 풀 수 있긴 하지만 시간과 공간을 조금이라도 줄여보고자 조금 더럽게 풀었다.

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

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