LeetCode 990

문제 링크

문제 설명.

500개 이하의 같다 혹은 같지 않다(!= or ==)와 소문자 알파벳으로 이루어진 수식들이 string으로 주어졌을 때 모든 수식들이 참이 될 수 있는지는 판별하는 문제.

문제에 있는 예시만으로 충분한 설명이 되기에 이를 그대로 설명한다.

input :
equations = ["a==b","b!=a"]

output :
False

첫 번째 식에 의해 a = b라 하자.
두 번째 식이 b != a 이므로 a != a라는 결론이 나오고 결과적으로 모든 수식이 참이 되지 않기 때문에 False가 출력되어야 한다.

풀이.

어떻게 풀까 하다가 key-value를 사용해서 풀이를 만들어봤다. 두 가지 과정에 걸쳐 작동을 하는 코드를 구상했는데 우선 소문자를 key로 가지고, 각각의 key에 대해 서로 다른 값을 value로 가지는 dictionary(word_dict)과 빈 배열인 dif를 만들어주었다.

1. 첫 번째 과정으로

   1. 두 문자가 같은 경우(==), value에 대해 비교가 되는 두 문자중 큰 값을 value로 가지는 모든 단어를 작은 값의 value로 바꿔주었다.
      • (ex. d==h이고, word_dict[d] = 3, word_dict[h] = 8, word_dict[j] = 8일 때 word_dict[j]의 값 역시 3으로 바꿔줘야 한다. 앞선 루프들에서 두 문자가 같은 경우만 따졌을 때, j==h라는 식이 성립이 되었기 때문이다.)
   2. 두 문자가 같지 않은 경우(!=), dif에 두 문자를 집어넣어줬다.

2. 다음 과정으로 dif에 있는 두 문자(i,j)들에 대해 차례대로 word_dict[i] == word_dict[j]인지를 체크해준다. 만약 이것이 참일 경우 1-2에 의해 두 문자의 값은 달라야하므로 False가 return이 되고, 모두 다를 경우 True가 return이 된다.

풀이 코드.

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        word_dict = {chr(i+97):i for i in range(26)}
        dif = []
        for i in equations:
            xy = sorted([i[0],i[3]])
            if i[1] == '!':
                dif.append(xy)
            else:
                num = word_dict[xy[0]]
                chan = word_dict[xy[1]]
                for i in word_dict:
                    if word_dict[i] == chan:
                        word_dict[i] = num
            
        for i,j in dif:
            if word_dict[i] == word_dict[j]:
                return False
        
        return True

• 시간적으로 효율이 좋은 코드는 아니지만, 문자 자체가 26자로 제한되어있다는 점, 그리고 그 안에서 value의 값만으로 작동이 되는 코드였기 때문에 다른 결과중에 가장 작은 메모리가 사용되었다.

• 제출 후에 다른 사람들과 비교해서 시간효율이 많이 떨어진다는 것을 알게 되었고, 코테방에서 물어본 결과 union-find를 사용하면 좋다고 하더라.(이것도 생각해보면 그 변형이긴 하지만, default로 코드를 짠다고 생각해보면 숫자들을 key로, 문자들을 value로 집어넣어서 등호식에 따라 extend 혹은 update 등으로 같은 숫자를 합쳐주며 비교할 수 있을 것 같다.(이경우에는 시간효율이야 좋아지겠지만 메모리 효율은 낮아질 것이다.))