[Leetcode] #500.Keyboard Row

문제 :

 

처음 보자마자 고민했다. 리스트를 순회하며 검사를 할것인가 아니면 딕셔너리를 이용할것인가...

 

생각해보니 그냥 리스트를 순회하기엔 너무 값이 비쌌다. 리스트의 검색은 O(n)이 소요되기 때문에 비싸다. 

그리고 이 문제를 보면, 키보드의 첫번째, 두번째, 그리고 세번째로 나뉘어있는데, 보자마자 해시테이블(파이썬의 딕셔너리) 라는 생각이 들었다. 다시한번 복습하지만, 해시테이블의 검색은 O(1)이 소요되어 매우 빠르다.

 

아래는 내가 제출해 통과한 코드이다.

class Solution:
    def findWords(self, words: List[str]) -> List[str]:
        f = "qwertyuiop"
        s = "asdfghjkl"
        t = "zxcvbnm"

        result = []
        rows = {}
        isSame = False

        for c in f:
            rows[c] = 1
        for c in s:
            rows[c] = 2
        for c in t:
            rows[c] = 3

        for i in words:
            lowerCase = i.lower()
            all_match = True
            for j in range(len(lowerCase) - 1):
                if(rows.get(lowerCase[j]) != rows.get(lowerCase[j+1])):
                    all_match = False
                    break
            if all_match:
                result.append(i)
            
        return result

먼저, 딕셔너리에 키보드의 줄 위치를 기반으로 값들을 넣어준다. 이제 키보드의 모든 문자는 각각의 줄 번호에 맞게 딕셔너리에 잘 삽입 되었다. 그 다음, for문을 사용하여 주어진 words에서 단어를 하나씩 꺼내어 비교한다. 하지만, 방금 내가 만든 딕셔너리에는 소문자값만 있으므로, 파이썬의 소문자 변환 메서드인 .lower()을 사용해 문자열을 소문자로 변경해주고 일일히 하나씩 비교해 키값이 다르다면(즉, 키보드에서 같은 줄에 있지 않다면) break를 이용해 바로 다음 문자로 넘어가고, 만약 문자열을 끝까지 검사했을때 문자열의 문자들이 모두 키보드의 같은 줄에 있다면 결과 배열에 문자열을 더해주고 마지막에 return 해 준다.

 

하지만 여기서 이중 for문을 쓰면서 불길한 예감이 들었다. 이중 for문은 O(n^2)의 시간 복잡도를 가지기 때문이다. 역시나 런타임은 매우 낮게 나왔다. 

 

이 코드의 런타임이 긴 이유와 성능을 향상시킬 수 있는 방안은 다음과 같다:

 이유

1. 반복적인 딕셔너리 접근:
   각 단어의 문자를 검사할 때, 매번 `rows.get()` 메서드를 호출하여 딕셔너리에서 값을 가져온다. 이 작업은 각 단어의 길이만큼 반복된다.

2. 이중 반복문:
   외부 반복문은 `words` 리스트의 모든 단어를 순회하고, 내부 반복문은 각 단어의 길이만큼 순회한다. 따라서 전체 시간 복잡도는 최악의 경우 (O(n * m))이다. 여기서 (n)은 `words` 리스트의 길이, (m)은 단어의 평균 길이이다.

성능 향상 방안

1. 집합을 사용하여 더 빠른 검색:
   딕셔너리 대신 집합을 사용하여 각 행에 있는 문자들을 저장하면 더 빠른 검색이 가능하다. 집합은 평균적으로 (O(1)) 시간 복잡도로 검색을 수행할 수 있다.

2. 한 번의 순회로 검사:
   각 단어의 첫 번째 문자의 행을 기준으로 설정하고, 나머지 문자들이 같은 행에 있는지 확인하는 방식으로 변경하면 내부 반복문을 최적화할 수 있다.

class Solution:
    def findWords(self, words: List[str]) -> List[str]:
        # 각 행에 있는 문자들을 집합으로 저장
        row1 = set("qwertyuiop")
        row2 = set("asdfghjkl")
        row3 = set("zxcvbnm")

        result = []

        for word in words:
            lowerCase = word.lower()
            if lowerCase[0] in row1:
                target_row = row1
            elif lowerCase[0] in row2:
                target_row = row2
            else:
                target_row = row3

            all_match = all(char in target_row for char in lowerCase)

            if all_match:
                result.append(word)

        return result

1. 집합 사용:
   각 행에 있는 문자들을 집합으로 저장하여 검색 속도를 향상시켰다.

2. 한 번의 순회로 검사:
   각 단어의 첫 번째 문자를 기준으로 해당하는 행을 설정하고, 나머지 문자들이 같은 행에 있는지 확인한다. `all()` 함수를 사용하여 단어의 모든 문자가 동일한 행에 있는지 확인한다.

이 개선된 코드의 시간 복잡도는 (O(n * m))에서 (O(n * k))로 줄어든다. 여기서 n은 `words` 리스트의 길이, m은 단어의 평균 길이, k는 집합에서의 검색 시간(평균적으로 (O(1))이다. 따라서 이 방법은 성능을 크게 향상시킬 수 있다.

 

 

새로 알게된 내용 : 

all() 함수는 파이썬 내장 함수로, 주어진 반복 가능한(iterable) 객체의 모든 요소가 참(True)인지 검사한다. 만약 모든 요소가 참이면 True를 반환하고, 하나라도 거짓(False)이면 False를 반환한다. 빈 반복 가능한 객체에 대해 호출하면 True를 반환한다.

all() 함수의 일반적인 사용 예는 다음과 같다:
리스트의 모든 요소가 참인지 검사:

numbers = [1, 2, 3, 4, 5]
result = all(numbers)
print(result)  # 출력: True (모든 요소가 참)

리스트의 일부 요소가 거짓인 경우:

numbers = [0, 1, 2, 3, 4]
result = all(numbers)
print(result)  # 출력: False (0이 거짓 값이므로)

조건을 만족하는지 검사:
리스트의 모든 요소가 양수인지 확인하는 예제:

numbers = [1, 2, 3, 4, 5]
result = all(n > 0 for n in numbers)
print(result)  # 출력: True (모든 요소가 양수이므로)

문자열이 모두 소문자인지 확인:

words = ["hello", "world", "python"]
result = all(word.islower() for word in words)
print(result)  # 출력: True (모든 단어가 소문자이므로)

 

- 그리고, 마지막에서 살짝 헷갈렸던 부분이 있다.

for i in words:
            lowerCase = i.lower()
            all_match = True
            for j in range(len(lowerCase) - 1):
                if(rows.get(lowerCase[j]) != rows.get(lowerCase[j+1])):
                    all_match = False
                    break
            if all_match:
                result.append(i)
            
        return result

이 부분을 보면 words문자열에서 문자열을 하나씩 뽑아내 다시 for문을 순회하며 문자를 하나하나씩 가져와 j + 1과같이 다음 문자와 비교하는 구간인데, 위의 조건문처럼 만약 다음 문자의 딕셔너리값이 같지 않다면 break를 통해 빠져나오고, 만약 문자열을 끝까지 검사했는데도 불구하고 문자열 모두가 같은 딕셔너리의 값을 갖고있으면 result에 append를 해야했다. 하지만 "만약 문자열을 끝까지 검사했는데도 불구하고 문자열 모두가 같은 딕셔너리의 값을 갖고있으면" 이 부분을 어떻게 코드로 써낼지 살짝 헷갈렸다. 이럴때는 위처럼 boolean플래그를 사용하면 된다. 물론 if문에 조건(끝까지 검사 했는지)을 추가하면 되지만, if문으로 비교하는것은 비싸다. 그래서 앞으로 이럴땐 boolean 플래그를 쓰도록 하자.