[python3] 389. Find the Difference

풀이 일자: 23.09.25

난이도: [Easy]

분류: [Hash Table/String/Bit Manipulation/Sorting]

 

문제 내용

s와 t가 주어졌을 때 s에서 1개의 letter을 추가로 넣고 섞었다고 했을 때 추가된 letter가 뭔지를 return하는 문제이다. ( 실제로는 s를 섞고 임의의 위치에 letter를 넣었다고 나오지만 편의상 넣고 섞었다고 보자)

 

문제 해결 흐름

 

1. 사실상 딱 봐도 Hash를 사용해야 하는 것이 자명하다.

→ 여러개의 알파벳이 중복해서 있을 수 있고 각각의 알파벳과 숫자를 모두 기억해두어야 하기 때문이다.

 

2. 그렇다면 s와 t중에서 뭐를 dictionary로 바꾸고 나머지를 순회해가면서 비교할지 결정해야 한다.

→ 나라면 s를 dictionary로 바꾸고 t를 순회해가면서 check할 것이다. 그 이유는 만약 t를 dictionary로 한다면 s는 무조건 모두 순회를 하고 t에서 value가 1인 것을 찾아 return해야한다. 하지만 s를 dictionary로 한다면 t를 순회하던 중 해당 letter가 없거나 더 있는 것을 순회 중에 찾을 수 있기 때문에 평균적으로 s를 dictionary로 사용하는게 좋다.

 

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        sc = Counter(s);
        ans = '';

        for letter in t:
            if letter in sc.keys():
                sc[letter] -= 1;
                if sc[letter] < 0:
                    ans = letter;
                    break;
            else:
                ans = letter;
                break;

        return ans;

 

Time Complexity:  O(N)

t를 순회하기 때문에 t의 length인 N만큼의 시간복잡도를 가질 것이다.

 

Space Complexity: O(N)

s를 비교를 위한 dictionary형태로 바꾸었기 때문에 이 또한 N의 시간복잡도를 가질 것이다.

 

 

다른 해결 방식

1. 다른 사람의 코드를 확인해보았을 때 s와 t를 list화 시켜서 sort한 후에 같은지 비교하는 코드와 둘 중 하나를 순회하면서 count를 통해서 비교를 하는 코드가 있었는데 그 코드 모두 내 코드보다는 성능이 좋지 않을 것이다.

→  그 이유는 list화 시키는 것도 시간이고 sort시키는 것도 시간이기에 크게보면 O(N)의 시간복잡도로 같더라도 정확하게 계산하면 4N의 시간복잡도로 봐야하며 count를 사용하는 코드는 s나 t를 순회하는 부분과 내부에 count가 있기 때문에 O(N²)의 시간이 걸릴 것이기에 빠르지 않다.

 

 

문제 링크

LeetCode - The World's Leading Online Programming Learning Platform