[LeetCode] Find the Difference

Find the Difference

문제

You are given two strings s and t.
String t is generated by random shuffling string s and then add one more letter at a random position.
Return the letter that was added to t.

Example 1:
Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:
Input: s = "", t = "y"
Output: "y"

Constraints:
0 <= s.length <= 1000
t.length == s.length + 1
s and t consist of lowercase English letters.

고민

주어지는 s와 t를 비교하여 더 많이 쓰인 단어를 찾아 반환하는 것이 목적이다.
나는 여기서 shuffling을 안보고 무작정 비교했다가 계속 fail 이 되었다.. 🥲
그렇다면 어떤 특정 단어가 더 쓰여있는지를 확인하려면 어떻게 해야할까?
sorted? 그냥 for 문?
나는 이전에 어느 코딩테스트 문제에서 썻던 방법을 사용할 것이다.

해결

class Solution {
    fun findTheDifference(s: String, t: String): Char {
        val sCountArray = IntArray(26)
        val tCountArray = IntArray(26)
        for (char in s) {
            sCountArray[char - 'a']++
        }

        for (char in t) {
            tCountArray[char - 'a']++
        }
        for (index in sCountArray.indices) {
            if (sCountArray[index] != tCountArray[index]) return ('a' + index)
        }
        return t[t.lastIndex]
    }
}

각각의 IntArray의 역할은 char 가 몇번 사용되었는지를 저장할 배열이다. 참고로 배열의 크기는 'a'~'z'까지이다.
그래서 두 개의 string 을 각 for 문을 돌며 char 가 몇번 사용되었는지를 저장한다.

그럼 이제 쉽다.
두 개의 배열에서 사용된 숫자가 다르다면 그 char 는 더 사용된것이므로 그 char 를 반환한다.

로직상 가장 마지막 return 까지 도달할 수는 없지만 혹시 모르니 Example 2 에 나왔던 것처럼 안전하게 마지막 char 를 반환한다.

결과

처음부터 아주 만족스러운 결과이군!

후기

char 를 하나하나 비교할 수 있겠지만, 중복으로 나올 경우에는 또 다른 분기처리가 필요할 것이고 앞서 제약에 보면
String s의 길이는 1000이 될 수 있다. 루프로 1000 을 돌며 하나씩 요소를 확인할 때 Char 보다는 Int 가 더 가벼울 것이니
이러한 방법을 사용했다.

코딩 테스트를 여러번 풀어보다 보니 조금은 문제의 풀이가 눈에 쏙쏙 들어온다.