[LeetCode] 32번 문제를 풀어보았다. (ft. java)

2022년 05월 24일 화요일 - 힘이 든다 힘이 드러~~~

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

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

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

오늘은 문제가 풀려있었다... ㅋㅋㅋㅋ

입력

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

---

풀이 및 코드

가장 긴 유효한 괄호의 길이를 찾아서 리턴하는 문제다.

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

스택을 사용하면서 유효한 괄호를 찾아냈고 이 괄호들을 모아서 나중에 합쳐주는 과정을 통해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int longestValidParentheses(String input) {
        int result = 0;
        Stack<Integer> s = new Stack<Integer>();
        ArrayList<pair> arr = new ArrayList<pair>();

        for(int i = 0; i < input.length(); i++)
        {
            if(input.charAt(i) == '(')
            {
                s.push(i);
            }
            else
            {
                if(s.isEmpty())
                {
                    continue;
                }
                else
                {
                    int nowFirst = s.pop();
                    arr.add(new pair(nowFirst, i));
                }
            }
        }

        Collections.sort(arr);

        for(int i = 0; i < arr.size() - 1; i++)
        {
            result = Math.max(result, arr.get(i).last - arr.get(i).first + 1);

            pair temp1 = arr.get(i);
            pair temp2 = arr.get(i + 1);

            if(temp1.last == temp2.first - 1)
            {
                arr.get(i).last = temp2.last;
                arr.remove(i + 1);
                i--;
            }
            else if(temp1.first < temp2.first && temp2.last < temp1.last)
            {
                arr.remove(i + 1);
                i--;
            }
        }

        if(arr.size() != 0)
            result = Math.max(result, arr.get(arr.size() - 1).last - arr.get(arr.size() - 1).first + 1);

        return result;
    }

    class pair implements Comparable<pair>
    {
        int first, last;
        public pair(int first, int last)
        {
            this.first = first;
            this.last = last;
        }

        @Override
        public int compareTo(pair p)
        {
            return this.first - p.first;
        }
    }
}

---

제출 화면

오늘은 문제가 이미 풀려있어서 고민할 시간이 없었다.

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

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