[LeetCode][py] 290. Word Pattern

Table of Contents

• 문제
• 예제
  • Example 1
  • Example 2
  • Example 3
• 계획
• 풀이
  • 1. 키와 값을 반대로 저장한 두 딕셔너리
  • 2. 최소 런타임 샘플 답안
• 참고 자료

문제

원문 보기 : [LeetCode] 290. Word Pattern

pattern과 문자열 s가 주어진다. s가 같은 패턴을 따르는지 확인하라.

따른다는 말은 pattern의 글자와 s에 존재하는 비어있지 않은 단어가 일대일 대응이 되는 것과 같은, 완전한 매치를 의미한다.

조건(Constraints):

• 1 <= pattern.length <= 300
• pattern에는 영어 소문자만 있다.
• 1 <= s.length <= 3000
• s에는 영어 소문자와 공백(' ')만 있다.
• s의 앞뒤에 남는 공백은 없다.
• s에 있는 모든 단어는 하나의 공백으로 구분된다.

예제

Example 1

Input: pattern = “abba”, s = “dog cat cat dog”
Output: true

Example 2

Input: pattern = “abba”, s = “dog cat cat fish”
Output: false

Example 3

Input: pattern = “aaaa”, s = “dog cat cat dog”
Output: false

계획

1. 상황 파악
   패턴에 있는 글자와 문자열에 있는 단어가 딱 맞으면 된다. 글자마다 연결 리스트처럼 집합을 달아서 문자열에 있는 모든 단어를 나누어 넣고, 마지막에 단어가 하나씩만 남아있는지 확인하면 되지 않을까? 파싱은 귀찮으니 파이썬을 써서 해보겠다. 물론 당연히 입력이 커지면 시간초과가 걸릴 것 같지만 일단 틀려보고 생각하기로 했다.
2. 첫 번째 시도
   문자와 리스트를 각각 키와 값으로 갖는 딕셔너리를 만들고자 했으나, 딕셔너리에 키가 없는 경우 키를 추가하는 것이 먼저이기 때문에 단순히 append만 쓸 수는 없었다.
   여기서 몇 가지 선택지가 있다. 각 선택지 모두 마지막에는 각 알파벳마다 1개의 단어만 남는지 확인하면 된다. 하나라도 그렇지 않은 것이 있다면 False를 반환한다.
   1. 딕셔너리를 유지하고, 키가 있는지 확인하는 선택문을 추가해 오류를 발생시키지 않는 것.
   2. 패턴에 있는 알파벳의 종류 수만큼 이차원 리스트를 만들어 각 알파벳을 인덱스 삼아 단어를 리스트에 추가 후 set() 적용해 확인
   3. 패턴에 있는 알파벳을 이용해 먼저 알파벳 키와 빈 집합을 값으로 갖는 딕셔너리를 만들고 단어를 추가
3. 두 번째 시도
   2번에서 3번째 선택지로 간다. 어차피 집합으로 만들면 다른 값이 추가될 때 크기가 2로 늘어나니까 단어를 추가하는 과정에서 개수도 같이 검사하고 False를 반환하게 했다.
4. 예상치 못한 반례에서 틀림
   패턴은 서로 다른 알파벳이 2개 이상 나왔는데, 단어는 딱 한 종류만 나오는 경우 True를 반환해서 틀린다. 서로 다른 패턴의 단어가 서로 다른지 확인하지 않았다. 다시 생각을 해보자.
   1. 이미 쓴 방식을 유지하고, 마지막에 확인 과정을 추가한다. <br> 틀린 건 아닌데 내가 보기엔 비효율적이다. 이런 상황에 더 어울리는 구조가 있는 게 맞지 않을까?
   2. 딕셔너리의 구성을 바꿔서 패턴 알파벳 하나당 단어 하나씩 매치시키고, 중복된 단어나 알파벳이 나오면 일치하는지 확인한다. 앞서 걸린 반례를 통과하기 위해 키와 값이 서로 반대인 딕셔너리로 총 2개 만들자.
5. 패턴의 알파벳 수와 단어의 개수가 같다는 조건은 없었지. 또 틀림
   이건 간단하게 걸러낼 수 있어. 모든 과정을 시작하기 전 패턴의 길이와 단어의 총 수가 같은지 확인하면 돼.
6. 이게 되네? 게다가 꽤나 상위 런타임과 메모리로 들어갔다. 런타임이 가장 짧은 답안만 참고해보고, C++로 쓸 때는 어떻게 쓰면 좋을지 생각이나 해보자.
   일단 내 답은 제쳐두고 최소 런타임 샘플 답안 봤는데, 딕셔너리 이름을 map이라고 지었더라. 그거 보니까 약간 감은 왔어. 다른 언어로 쓸 때도 map을 쓰면 되는거지? 순서가 중요한 상황이 아니니까 unordered_map 쓰면 더 빠르겠다. 그리고 나랑 비슷하게 딕셔너리를 2개 썼는데, 하나는 패턴 알파벳과 단어를 매치했고 다른 하나는 단어의 등장 여부만 체크해둔 것 같더라. 자세한 건 밑에서 더 보자고요.

풀이

1. 키와 값을 반대로 저장한 두 딕셔너리

Runtime : 14 ms
Memory : 13.3 MB

리뷰

1. 파이썬의 딕셔너리는 해시로 구현되어 있다 ^[1]. 새로 배웠다! 파이썬이라 느릴 줄 알았는데 의외로 빨랐던 이유가 딕셔너리의 구현이 해시라서 그런 것 같다.
2. 계획을 먼저 하는 습관을 좀 더 들입시다 학생. 오늘도 냅다 코드부터 쓰다가 반례 보고 고쳤잖아. 이거 쓰면 되겠지? 하고 바로 달려들지 말고 좀 더 자세히 생각해보란 말이지.
3. 부족한 점 : 서로 반대되는 두 딕셔너리를 한번에 확인할 수 있는 방법이 생각나지 않았다, 라기 보다는 일단 문제가 풀리는 데에 만족해서 거기까지 가지 않고 생각을 놓아버렸다. 대신 보고 배웠습니다.

class Solution(object):
    def wordPattern(self, pattern, s):
        """
        :type pattern: str
        :type s: str
        :rtype: bool
        """
        words = s.split(' ')  # 단어 파싱

        if len(pattern) != len(words):  # 단어 개수와 패턴 길이 다르면 안 됨
            return False

        matchs = {}  # 패턴 사전 : 키 - 패턴, 값 - 단어
        match_reverse = {}  # 단어 사전 : 키 - 단어, 값 - 패턴

        for c, word in zip(pattern, words):  # 대응되는 패턴과 단어의 쌍 반복
            if c in matchs:  # 패턴 사전에 패턴이 존재하는데
                if matchs[c] != word:  # 단어가 다르면 안 됨
                    return False
            else:  # 없다면 추가
                matchs[c] = word

            if word in match_reverse:  # 단어 사전에 단어가 존재하는데
                if match_reverse[word] != c:  # 패턴이 다르면 안 됨
                    return False
            else:  # 없다면 추가
                match_reverse[word] = c

        return True  # 다 통과하면 됨

2. 최소 런타임 샘플 답안

Runtime : 3 ms

풀이

1. 단어의 수와 패턴의 길이가 같은지 확인하고, 다르면 False 반환.
2. 2개의 딕셔너리를 만든다. 하나는 (키, 값)으로 (패턴, 단어)를 저장하고, 다른 하나는 (단어, True)를 저장한다.
   이때 두 번째 딕셔너리는 단어의 등장 여부만을 확인하기 위함이니 값은 꼭 True가 아니어도 된다.
3. 이후 패턴의 길이만큼 반복한다.
4. 현재 패턴이 아직 등장하지 않은 새 패턴일 경우
   • 이 패턴에 대응하는 단어가 이미 등장한 단어라면 False 반환.
   • 단어도 등장하지 않은 것이라면 두 사전에 각각 추가한다.
5. 이미 등장한 패턴인데 대응되는 단어가 다른 경우 : False 반환.
6. 반복이 끝나면 True 반환.

내 답안과 비교

• 2개의 딕셔너리를 사용함
  1. 서로 반대되는 키와 값을 저장해 패턴과 단어의 대응을 2번 확인 : 패턴은 다른데 대응되는 단어가 같은 반례를 거르기 위함이었으나, 2개의 딕셔너리를 각각 확인해야 한다.
  2. 패턴과 단어의 조합은 한번씩만 저장하고, 단어의 등장 여부를 추가로 저장 : 등장하지 않은 새 패턴을 확인할 때는 두 딕셔너리를 이용해 확인하지만 이미 등장한 패턴을 확인할 때는 하나만 확인해도 되며, 이 과정이 한 블록의 선택문 안에서 해결 가능하다.

class Solution(object):
    def wordPattern(self, pattern, s):
        """
        :type pattern: str
        :type s: str
        :rtype: bool
        """
        words = s.split()
        n = len(pattern)
        if len(words) != n:
            return False
        map = dict()
        map2 = dict()
        for i in range(n):
            if map.get(pattern[i]) is None:
                if map2.get(words[i]) is not None:
                    return False
                map[pattern[i]] = words[i]
                map2[words[i]] = True
            elif map.get(pattern[i]) != words[i]:
                return False

        return True 

참고 자료

• [1] 파이썬의 딕셔너리는 어떻게 구현되어 있을까? -해시-, https://fierycoding.tistory.com/68