[Python] LeetCode 문제풀이 :: 925. Long Pressed Name

LeetCode

 

LeetCode 925번 문제풀이

 

https://leetcode.com/problems/long-pressed-name/

Long Pressed Name - LeetCode

Your friend is typing his name into a keyboard.  Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times. You examine the typed characters of the keyboard.  Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.   Example 1:     Input: name = "alex", typed = "aaleex"     Output: true     Explanation: 'a' and 'e' in 'alex' were long pressed. Example 2:     Input: name = "saeed", typed = "ssaaedd"     Output: false     Explanation: 'e' must have been pressed twice, but it wasn't in the typed output. Example 3:     Input: name = "leelee", typed = "lleeelee"     Output: true Example 4:     Input: name = "laiden", typed = "laiden"     Output: true     Explanation: It's not necessary to long press any character.

키보드로 이름을 친다. 그런데 가끔 문자가 여러 개 눌린다. alex를 쳐야 하는데 aallleex로 칠 수 있는 상황. name와 typed 두 가지 문자열이 주어졌을 때, typed가 name이 잘못 눌려서 생긴 문자열이 맞는지 검증하는 문제. 같이 풀던 동기는 쉬워보이는데 어려운 문제라고 했다. 나는 어려워보이는데 막상 풀면 은근 쉬울 문제일 것처럼 느껴졌다. 그리고 실제로 그랬다. 종이에 정리해가면서 풀면 더 빨리 풀었을 텐데, 머릿속으로만 굴리다보니깐 좀 시간이 걸렸다. 처음에는 단순하게 앞 글자부터 검사해가면서 앞 문자를 삭제하거나, 뒤로 돌리고 결과적으로 name과 typed가 같으면 True, 아니면 False를 리턴하는 방식이였다. 막상 구현해보니 상당히 많은 경우의 수가 있었다. 고민 결과 문제를 단순화해보기로 했고, 그 솔루션으로 실행 시간 92점, 메모리 100점의 좋은 결과를 얻었다.

 

# Solution 1

class Solution:
    def isLongPressedName(self, name, typed):
        nameSplit = self.chrSpliter(name)
        typedSplit = self.chrSpliter(typed)

        if (len(nameSplit) != len(typedSplit)):
            return False

        for i in range(len(nameSplit)):
            if nameSplit[i][0] != typedSplit[i][0] or len(nameSplit[i]) > len(typedSplit[i]):
                return False
        return True
        
     def chrSpliter(self, chr):
        chrList = []
        temp = ""
        for i in range(len(chr)):
            temp += chr[i]

            if i == len(chr) - 1 or chr[i] != chr[i + 1]:
                chrList.append(temp)
                temp = ""
        return chrList

 

우선 chrSpliter부터 봐야한다. 들어온 문자열을 연속된 문자 단위로 끊어서 리스트에 저장해주는 문자열이다. 끊어진 문자를 담을 chrList를 생성한다. 그리고 chrList에 담길 문자 요소인 temp를 초기화 한다. 그리고 입력된 chr의 각 문자에 대해서 반복문 시작. 먼저 temp의 끝에 chr[i]를 추가한다. 그리고 문자열의 마지막일 경우, 즉 i==len(chr)-1일 경우 또는 방금 체크한 문자와 그 다음 문자가 같지 않을 경우, 즉 chr[i]!=chr[i+1]일 경우에는 temp를 chrList에 추가하고 temp를 리셋한다. 그리고 chrList 리턴. 이럴 경우 aaabbcc가 주어지면 ["aaa", "bb", "cc"]를 리턴한다.

 

그리고 isLongPressedName에서, name과 typed를 chrSpliter()처리한 nameSplit과 typedSplit 리스트를 만든다. 어쨌든 typed가 named로부터 만들어진 거라면 각 알파벳의 덩어리는 같을 테니깐 길이가 같아야 한다. 길이가 다르면 False 리턴. 그리고 nameSplit의 각각의 요소에 대해 반복문을 돌린다. 이 때 typed가 name으로부터 만들어진 거라면, 같은 인덱스의 요소는 두 가지 조건을 충족해야 한다.

 

1. 첫번째 문자가 같아야 한다.

2. typed의 요소가 named의 요소보다 길어야 한다.

 

위 두 조건은 둘 다 충족해야 하므로 하나라도 충족하지 않으면, 즉 nameSplit[i][0]!=typedSplit[i][0] or len(nameSplit[i])>len(typedSplit[i])이면 False를 리턴해야 한다. 첫번째 체커인 두 리스트의 전체 길이 비교, 그리고 두번째 체커인 각 인덱스의 문자 일치 여부 및 길이 체크를 통과한다면 True를 리턴한다.

 

예시인 name = "alex", typed = "aaleex"로 검증을 해보자. 각각을 찢은 문자열은 ['a', 'l', 'e', 'x]와 ['aa', 'l', 'ee', 'x]가 될 것이다. 두 리스트의 길이는 모두 4이므로 첫번째 체커를 통과한다. 이제 같은 인덱스의 각 요소에 대해 비교해봐야 한다. 'a'와 'aa'는 첫번째 문자가 같고, typed 쪽이 길이도 더 길다. 그러므로 name에서부터 온 문자라고 할 수 있다. 마찬가지로 l, e, x를 비교하면 모두 조건을 충족하므로 결과는 True가 된다.

이번엔 name = "saeed", typed = "ssaaedd"로 검증을 해보자. 문자열은 ['s', 'a', 'ee', 'd']와 ['ss', 'aa', 'e', 'dd']이다. 리스트의 길이는 4로 일치한다. 's'와 'ss'는 문자가 같고 typed가 더 길기 때문에 'ss'는 's'로부터 온 문자다. 'a'와 'aa'도 마찬가지다. 그런데 'ee'와 'e'는 다르다. typed 쪽이 최소 'ee'는 되어야 typed가 name으로부터 왔다고 볼 수 있다. 그러므로 여기선 False 리턴.

 

https://github.com/infomuscle/algorithms-leetcode/blob/master/python/925.%20Long%20Pressed%20Name.py

infomuscle/algorithms-leetcode