알고리즘 문제풀이 정리 - Arrays & Hashing (1)

왜하는가?

지금까지 알고리즘을 c++로 공부해왔는데, 문득 나는 인공지능을 중점적으로 공부한 사람인데 왜 python으로 알고리즘 문제를 풀려고 하지 않았나 싶어 python으로 알고리즘 공부를 다시 하기로 하였다. 사실 마지막으로 알고리즘 공부를 한지 조금 오래되었기도하여 python으로 문제를 다시 풀면서 블로그에 내가 푼 문제를 기록으로 남기기로 다짐했다.

앞으로 https://neetcode.io/ 에 있는 Roadmap을 차례대로 풀어가려고 한다.

이번 게시물에서 다루는 카테고리는 Arrays & Hashing 이다.

Contains Duplicate

Easy

Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.

Example 1:

Input: nums = [1, 2, 3, 3]
 
Output: true

Example 2:

Input: nums = [1, 2, 3, 4]
 
Output: false

My solution

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        n=len(nums)
        books=[]
        isDup=False
        for num in nums:
            for book in books:
                if book==num:
                    isDup=True
                    break
            if isDup:
                break
            else:
                books.append(num)
 
        return isDup

Brute Force에 해당하는 방법으로 문제를 풀었다. hash table 같은 개념을 활용하면 시간복잡도를 더 낮츨 수 있음을 직감했는데 순간 python으로 어떻게 써야할지 생각이 안났다. 그런데 사실 Brute Force로도 아주 깔끔하게 풀어낸거 같지는 않다.

시간복잡도 $O(n^2)$, 공간복잡도 $O(n)$의 끔찍한 혼종.

Solutions

1. Brute Force

Solution 에서는 Brute Force 방식을 이렇게 풀었다.

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    return True
        return False

이러면 내가 쓴 방식보다 메모리를 절약할 수 있으니 더 우아한 방식이라고 할 수 있겠다.

사실 c++을 썼으면 이런식으로 썼을거 같았는데, 뭔가 python에서만 쓸 수 있는 for문의 특성인 시퀀스 순회를 써보고 싶었다.

하지만 오히려 더 비효율적이 된 거 같다.

Brute Force는 $O(n^2)$으로 가장 나쁜 시간복잡도를 자랑한다. 물론 공간복잡도는 $O(1)$ 이긴하지만 보통 시간을 더 중요한 방법으로 보기에 다른 방식을 알고갈 필요가 있다.

2. Sorting

솔루션에서 제시한 다른 방식 중 인상 깊었던건 Sorting 이었다. 정렬을 한 다음에 앞에서부터 순차적으로 체크하면 된다니. 분명 배웠던건데 공부한지 오래되어 이 포인트가 기억이 나지 않았다. 앞으로 꾸준히 공부를 해야겠다.

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False

Sorting을 사용할 경우의 시간복잡도는 $O(n \log n)$, 공간복잡도는 Sorting 알고리즘에 따라 $O(1)$ 혹은 $O(n)$이다.

3. Hash Set

다른 방식으로는 Set을 활용하는 방식이었다.

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False

list의 각 요소를 set에 하나씩 넣어가면서 다음 요소가 set에 있는 것과 일치하면 중복이 있으니 True를 반환하는 식이다.

사실 내가 짠 코드랑 비슷한데 내가 set을 활용할 생각을 못해서 결과적으로 Brute Force가 되어버렸다.

set을 활용했기에 if num in seen: 에서 시간복잡도가 $O(1)$이 되어버린다.

(seen set에 num이 있는지 확인하기 위해, python은 내부적으로 Hash 값을 사용)

그러나 내가 짠 코드는 for문으로 찾아야했으므로 $O(n)$ 이었다.

중복을 찾자마자 바로 return True를 사용한 점도 기억했다가 나중에 코드를 간결하게 작성할 때 활용해야겠다.

그래서 이 방식의 시간복잡도는 $O(n)$, 공간복잡도는 $O(n)$이다.

4. Hash Set Length

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums)) < len(nums)

위의 방식보다 더 우아한 방식이다. 적어도 코드 길이는 더 간결하다.

list를 set으로 만들어버리면 중복이 제거되기 때문에 그것을 활용해 두 길이를 비교하고 set의 개수가 list의 개수보다 작다면 중복이 있는 것으로 판단한다.

이런 방법은 기억해뒀다가 나중에 비슷한 상황에서 응용하면 좋을 것 같다.

우아한 코드가 꼭 좋은건 아니지만 그래도 스스로 이렇게 쓰면 한단계 성장한 기분이 들 것 같다.

Valid Anagram

Easy

Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.

An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Example 1:

Input: s = "racecar", t = "carrace"
 
Output: true

Example 2:

Input: s = "jar", t = "jam"
 
Output: false

Constraints:

• s and t consist of lowercase English letters.

My solution

string에 있는 각 character를 set에 넣으며 int 1로 초기화하고 set에 이미 존재하면 int의 값을 늘리는 방식을 생각했는데 python으로 이거를 어떻게 작성할 수 있는지 생각을 못해냈다. 큰일났다. 아직 갈길이 멀다.

ai에게 물어보니 그게 곧 dictionary... 물론 set 기반으로 동작한다고 말할 수는 없지만 Hash Table을 이용해 구현된다는 점에서 원리가 같다. 왜 dictionary를 생각하지 못했는지.. 아무래도 뇌가 너무 굳은거 같다.

이참에 정리하고 넘어가자면,

• 셋(Set): 해시 테이블을 사용해 '값' 자체의 존재 여부만 관리하는 자료구조. (마치 학생 이름만 적힌 출석부)
• 딕셔너리(Dictionary): 해시 테이블을 사용해 '키'를 통해 '값'에 접근하는 자료구조. (마치 학생 이름(Key) 옆에 성적(Value)이 적힌 성적표)

이다.

한발 더 나아가 Tmi를 추가해보자면,

현대 파이썬(CPython 3.7+ 기준)의 내부 구현에서는 dictionary가 더 근본적인 자료구조이고, set은 사실상 "값이 없는 dictionary"처럼 구현되어 있다고 한다. (값을 저장하는 부분을 떼어내고 코드를 재활용으로 추정)

이는 딕셔너리 구현이 극도로 최적화되었기 때문에, 그 최적화된 구현을 셋에서도 재활용하는 것이라고 한다.

지식이 늘었다! 수정. 계속 원 출처가 어딘지 찾아봤는데 geeks와 stackoverflow에서 주장하는바가 다르므로 100% 신뢰할 수 없다. 그냥 둘다 헤시 테이블을 사용한다는 점만 참고하시길. https://stackoverflow.com/questions/3949310/how-is-set-implemented https://www.geeksforgeeks.org/python/sets-in-python/

trial 1

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        c_counts={}
        for c in s:
            if c in c_counts:
                c_counts[c]+=1
            else:
                c_counts[c]=1
        for c in t:
            if c in c_counts:
                c_counts[c]-=1
                if c_counts[c]<0:
                    return False
            else:
                return False
        return True

string s에 대해 각 알파벳의 등장 횟수를 세고 string t를 보며 알바벳의 등장 횟수를 빼는 식으로 구현해서 test case를 다 통과했길래 답안을 제출했더니

s="xx"
t="x"

를 True라고 반환해버렸다. (정답은 False) c_counts[c]가 음수가 아니라 양수로 남아 끝날 수 있는 가능성을 배제해버린 것..

trial2

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        c_counts={}
        for c in s:
            if c in c_counts:
                c_counts[c]+=1
            else:
                c_counts[c]=1
        for c in t:
            if c in c_counts:
                c_counts[c]-=1
                if c_counts[c]<0:
                    return False
            else:
                return False
        for i in c_counts.values():
            if i!=0:
                return False
        return True

해당부분 보완해서 제출했고 Accepted.

tip.

dictionary에서 value만 순회하고 싶다면 .values()를 사용하면 된다.

key와 value를 동시에 순회하고 싶다면 .items() 사용할 것.

key만 순회하고 싶다면 .keys() 사용할 것.

주의!

for 문의 dictionary를 순회하는 동안에는 dictionary의 크기를 변경하는 작업(요소 추가 또는 삭제)을 하면 안된다.

Python에서 이것은 금지되어있으며, RuntimeError를 발생시킨다.

-> 만약 순회 중에 딕셔너리를 수정해야 한다면, 키 리스트의 복사본을 만들어 순회해야 함.

my_dict = {'a': 1, 'b': 2, 'c': 3}
 
for key in list(my_dict.keys()): # list(my_dict.keys())로 키의 복사본을 만들어 순회
    if key == 'b':
        del my_dict[key]
 
print(f"수정 후 딕셔너리: {my_dict}") # 출력: 수정 후 딕셔너리: {'a': 1, 'c': 3}

tmi.

for i, j in enumerate(c_counts):
            if j!=0:
                return False

dictionary를 이런식으로 순회하면 어떻게 될까?

enumerate()은 순회 가능한 객체에 인덱스 번호를 붙여 (index, element) 형태의 tuple을 만들어주는 함수이기에,

i는 index, j는 key가 된다.

Solutions

solution은 총 3가지가 소개되어 있다.

1. Sorting

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
            
        return sorted(s) == sorted(t)

이전 문제와 해결책이 상당히 유사하다. 일단 각각 정렬을 하고, 둘이 일치하는지 동시에 순회해서 비교해보는 컨셉

이걸 sorted() 함수를 이용해 두 string이 같은지 비교해서 나오는 Boolean 값을 바로 return함으로 깔끔하게 풀어냈다.

tmi.

시간복잡도는 $O(n \log n + m \log m)$ 이다.

2. Hash Map

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
 
        countS, countT = {}, {}
 
        for i in range(len(s)):
            countS[s[i]] = 1 + countS.get(s[i], 0)
            countT[t[i]] = 1 + countT.get(t[i], 0)
        return countS == countT

위의 Sorting 풀이처럼 일단 길이가 다른지 먼저 비교하고,

s와 t에 대해 각각 dictionary로 Hash Map을 생성한다.

for문을 순회하여 각각의 dictionary를 독립적으로 만들고 마지막에 같은지 비교한다.

countS.get(s[i], 0) 부분

• countS.get(key, default): 딕셔너리 countS에서 key에 해당하는 값을 가져온다. 만약 key가 존재하지 않으면 default 값(여기서는 0)을 반환한다.
• countS[s[i]] = 1 + countS.get(s[i], 0)의 의미:
  • 만약 s[i] 문자가 countS에 처음 등장했다면: countS.get(s[i], 0)는 0을 반환. 1 + 0 이 계산되어, countS[s[i]] = 1이 된다. (새로운 문자 등록)
  • 만약 s[i] 문자가 countS에 이미 존재한다면: countS.get(s[i], 0)는 기존의 개수(예: 2)를 반환. 1 + 2 가 계산되어, countS[s[i]] = 3이 된다. (기존 개수 1 증가)

내 풀이가 solution의 방식은 다르지만 결과적으로 이 방식에 해당한다.

시간복잡도는 $O(n + m)$ 이다.

3. Hash Table (Using Array)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
 
        count = [0] * 26
        for i in range(len(s)):
            count[ord(s[i]) - ord('a')] += 1
            count[ord(t[i]) - ord('a')] -= 1
 
        for val in count:
            if val != 0:
                return False
        return True

알파벳이 26개로 이루어졌음을 이용해서 dictionary가 아니라 배열로 문제를 풀이한 케이스다.

이렇게 범용적이지는 않지만 도메인의 특성을 적용해서 더 효율적으로 풀어내려는 시도 및 고민도 중요한 것 같다.

그 외에 더하고 빼는 흐름은 내 풀이 방식과 같다.

시간복잡도는 $O(n + m)$ 이다.

Two Sum

Easy

Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.

You may assume that every input has exactly one pair of indices i and j that satisfy the condition.

Return the answer with the smaller index first.

Example 1:

Input: 
nums = [3,4,5,6], target = 7
 
Output: [0,1]

Explanation: nums[0] + nums[1] == 7, so we return [0, 1].

Example 2:

Input: nums = [4,5,6], target = 10
 
Output: [0,2]

Example 3:

Input: nums = [5,5], target = 10
 
Output: [0,1]

Constraints:

• 2 <= nums.length <= 1000
• -10,000,000 <= nums[i] <= 10,000,000
• -10,000,000 <= target <= 10,000,000

My solution

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        answer=[]
        for i, num1 in enumerate(nums):
            for j in range(i+1, len(nums)):
                if num1+nums[j]==target:
                    answer.append(i)
                    answer.append(j)
                    break
        return answer

앞에서부터 순차적으로 비교하고 target에 해당하는 두 점을 찾으면 answer에 추가하여 반환하였다.

Brute Force 풀이에 해당한다.

둘다 enumerate를 활용해 for문을 쓰려고 했는데 그러면 j를 순회할 때 낭비가 발생해서 range를 쓰게 되었다.

tip.

• .append() : 리스트의 맨 끝에 요소 하나 추가하기

• .extend() : 리스트에 다른 리스트(또는 반복 가능한 객체)의 모든 요소 추가하기

list_a = [1, 2, 3]
list_b = [4, 5, 6]
print(f"A 변경 전: {list_a}")
print(f"B: {list_b}")
 
list_a.extend(list_b)  # list_a에 list_b의 모든 요소를 추가
print(f"extend 후: {list_a}")
 
 
list_c = [7, 8, 9] # 튜플이나 문자열 등 다른 반복 가능한 객체도 가능합니다.
list_c.extend("abc")
print(f"문자열 extend 후: {list_c}")

실행 결과:

A 변경 전: [1, 2, 3]
B: [4, 5, 6]
extend 후: [1, 2, 3, 4, 5, 6]
문자열 extend 후: [7, 8, 9, 'a', 'b', 'c']

• .append() vs .extend() 비교

x = [1, 2]
y = [1, 2]
other = [3, 4]
 
x.append(other)  # other 리스트 자체를 하나의 요소로 취급하여 추가
print(f"append 결과: {x}") # [1, 2, [3, 4]]
 
y.extend(other)  # other 리스트의 각 요소를 꺼내서 추가
print(f"extend 결과: {y}") # [1, 2, 3, 4]

• .insert() : 특정 위치(index)에 요소 하나 추가하기

my_list = ['a', 'b', 'd']
print(f"변경 전: {my_list}")
 
 
my_list.insert(2, 'c') # 인덱스 2 위치에 'c'를 삽입
print(f"insert(2, 'c') 후: {my_list}")
 
 
my_list.insert(0, 'start') # 맨 앞에 추가하고 싶을 때 (인덱스 0)
print(f"insert(0, 'start') 후: {my_list}")

실행 결과:

변경 전: ['a', 'b', 'd']
insert(2, 'c') 후: ['a', 'b', 'c', 'd']
insert(0, 'start') 후: ['start', 'a', 'b', 'c', 'd']

주의!

.insert()는 특정 위치에 요소를 삽입한 후, 그 뒤에 있던 모든 요소들을 한 칸씩 뒤로 밀어야 한다. 따라서 리스트의 크기가 매우 클 때 맨 앞부분에 insert를 반복적으로 수행하면 성능이 저하될 수 있다.

• + 연산자로 리스트 합치기

  두 리스트를 합쳐 새로운 리스트를 만들고 싶을 때 + 연산자 사용할 수 있다. .extend()와 비슷해 보이지만, 원본 리스트를 변경하지 않고 새로운 리스트를 생성한다는 점이 다르다.

• 요약

Solutions

1. Brute Force

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

내 풀이랑 정확히 일치하는데 return [i, j] 으로 반환을 표현했다는 점이 주목할만한 것 같다.

정답이 무조건 for문 끝나기 전에 나오니까 if 조건에서 return 하되 에러가 발생하는걸 피하기 위해 마지막에 return [ ] 을 적어놓은 것도 눈에 띈다.

시간복잡도는 *$O*(n^2)$.

2. Sorting

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        A = []
        for i, num in enumerate(nums):
            A.append([num, i])
        
        A.sort()
        i, j = 0, len(nums) - 1
        while i < j:
            cur = A[i][0] + A[j][0]
            if cur == target:
                return [min(A[i][1], A[j][1]), 
                        max(A[i][1], A[j][1])]
            elif cur < target:
                i += 1
            else:
                j -= 1
        return []

1. 숫자와 해당 숫자의 index를 차례로 이차원 배열로 저장해 숫자를 기준으로 정렬한다.
2. i,j 투포인터로 정답을 탐색한다.

양 끝에서부터 탐색을 시작해 두 수의 합이 작으면 왼쪽 포인터를 오른쪽으로 이동시키고, 합이 크면 오른쪽 포인터를 왼쪽으로 이동시킨다.

배열이 정렬되어 순차적으로 증가하는 점을 이용하는 것이다.

문제 풀 때 숫자를 정렬하고 해결하는걸 고민 안해본건 아닌데 그랬을 때 뒤섞이는 index를 어떻게 기억하면 좋을지 그순간 떠올려내지 못했다.

공부를 쉬지 않고 꾸준히 해야하는 이유.. 안하면 기초적인 것도 금방 까먹음..

특히나 투포인터로 답을 찾아가는 풀이는 직관적인 것 같으면서도 의외로 쉽게 생각해내기 어려운 경우가 있어 흐름을 따라가서 과정을 한 번 이해한 뒤에는 패턴을 외우는게 좋을 것 같다.

시간복잡도는 $O(n \log n)$.

3. Hash Map (Two Pass)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        indices = {}  # val -> index
 
        for i, n in enumerate(nums):
            indices[n] = i
 
        for i, n in enumerate(nums):
            diff = target - n
            if diff in indices and indices[diff] != i:
                return [i, indices[diff]]

리스트를 총 두 번 순회하여 문제를 해결한다고 해서 Two Pass 이다.

첫 번째 순회에서 dictionary를 이용해 숫자를 key, index를 value로 저장한다.

두 번째 순회에서 각 숫자 n에 대해 target에서 숫자 n을 뺀 값이 diff가 dictionary에 존재하는지 확인하고 그게 n의 index와 일치하지 않는다면 두 index를 반환한다.

어째서 i가 반드시 indices[diff] 보다 작다고 보장할 수 있을까? 그건 두번째 순회에서 indices가 아닌 nums의 순서대로 탐색을 진행하기 때문이다.

시간복잡도는 $O(n)$.

4. Hash Map (One Pass)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {}  # val -> index
 
        for i, n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff], i]
            prevMap[n] = i

Two Pass의 풀이를 한번의 순회(One Pass)만으로 해결하는 더 효율적인 코드이다.

현재 숫자 n에 대해 n의 짝인 diff를 이전에 지나온 숫자들 중에 있는지 확인하는 식의 구조를 취하고 있다.

있다면 바로 정답을 반환하면되고, 없으면 현재 숫자 n과 index i를 dictionary(Hash Map)에 추가하고 다음 숫자에 대한 탐색을 이어간다.

시간복잡도는 $O(n)$.

Two Pass 방식과의 결정적인 차이점

• Two Pass: 먼저 모든 숫자의 정보를 맵에 저장한 뒤, 처음부터 다시 보면서 짝을 찾는다. (선 등록, 후 조회)
• One Pass: 숫자를 하나씩 보면서, "내 짝이 지금까지 지나온 길에 있었나?"를 확인한다. 없으면 "내가 여기 지나간다"는 기록을 남긴다. (조회 후, 후 등록)

이 "조회 후, 후 등록" 방식 덕분에 다음과 같은 장점이 생긴다.

1. 반복 최소화: 정답을 찾는 즉시 함수가 종료되므로 불필요한 반복을 하지 않음.
2. 자기 자신 중복 방지: if indices[diff] != i 와 같은 조건이 필요 없다. 왜냐하면 조회하는 시점에는 현재 숫자 n이 아직 prevMap에 등록되지 않았기 때문에, diff가 n과 같더라도 자기 자신을 가리키는 경우가 원천적으로 발생하지 않는다.

반드시 이해하고 넘어가야할 로직!!

끝맺음

Arrays & Hashing 카테고리에 총 9문제가 있는데 이번 게시글에서는 초반 3문제 풀었다.

아직 더 좋은 알고리즘을 바로 고민해내지 못한다는 점에서 갈 길이 너무 멀다.

앞으로 열심히 공부해야겠다.