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

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(" ", "");
    }
}

---

제출 화면

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

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

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