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

2022년 2월 07일 월요일 - 으어어 월요일...

오늘 올려볼 문제는 389번 Find the Difference 이라는 문제이다.

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

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

오늘은 3분컷!

입력

사진에서도 볼 수 있듯이 string 2개가 주어진다.

---

풀이 및 코드

주어진 하나의 string과 같은 원소들을 가지고 있지만 위치는 랜덤인 string에 하나의 char을 추가했을 때 추가된 char을 찾아서 리턴하는 문제다.

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

string을 구성하는 원소의 개수를 저장하는 int배열을 만든다.

첫번째 string을 구성하는 원소는 배열에 더하고, 두번째 string을 구성하는 원소는 배열에 뺐다.

모든 과정이 끝난 후 배열을 탐색했을 때 개수가 0이 아닌 index가 추가된 char다.

이런식으로 시간복잡도 O(N)에 풀 수 있는 방법을 생각해냈다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public char findTheDifference(String s, String t) {
        char[] arr = new char[30];

        for(int i = 0; i < s.length(); i++)
        {
            arr[s.charAt(i) - 'a']++;
            arr[t.charAt(i) - 'a']--;
        }
        arr[t.charAt(t.length() - 1) - 'a']--;

        for(int i = 0; i < arr.length; i++)
        {
            if(arr[i] != 0)
                return (char)('a' + i);
        }

        return 'a';

    }
}

---

제출 화면

오늘은 어렵지 않게 풀었던 문제였다.

문제에 대한 고민을 거의 안해서 오늘은 뭔가 문제를 안풀었다고 생각이 들 정도의 날이었다. ㅋㅋㅋㅋㅋㅋㅋ

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