[프로그래머스] Python 알고리즘 스터디 - 2주차 Stack & Hash

2주 차 

Stack, Hash

---

 

< 1. 나머지 한 점 >

def solution(coordinates):
    X_set = set()
    Y_set = set()
    
    for coordinate in coordinates:
        X, Y = coordinate

        if X not in X_set : 
            X_set.add(X)
        else: 
            X_set.remove(X)
        
        if Y not in Y_set : 
            Y_set.add(Y)
        else: Y_set.remove(Y)
    return list(X_set) + list(Y_set)

짝이 되지 않는 좌표가 나머지 한 점이다.

그런 좌표들을 합쳐서 return 해주면 되는 간단한 문제다.

 

---

< 2. 운송 트럭 >

def solution(max_weight, specs, names):
    spec_info = {}
    for spec in specs:
        name, weight = spec
        spec_info[name] = int(weight)
        
    cur_weight, cnt = 0, 1
    for name in names:
        if cur_weight + spec_info[name] <= max_weight:
            cur_weight += spec_info[name]
        else: 
            cnt += 1
            cur_weight = spec_info[name]
    return cnt

---

< 3. 빙고 >

 

1) 첫 시도

def solution(board, nums):
    nums = set(nums)
    
    for row in range(len(board)):
        for col in range(len(board)):
            if board[row][col] in nums: 
                board[row][col] = 0
         
    # 가로 : sum(board[i])
    # 세로 : sum(board[i~len(board)][0])
    # 대각선: sum(board[i,i])
    # 대각선_2 : sum(board[len(board)-i][len(board)-i])
    cnt = 0
    diag_1, diag_2 = 0, 0
    for i in range(len(board)):
        horizontal, vertical = 0, 0
        # 가로, 세로
        for j in range(len(board)):
            vertical += board[i][j]
            horizontal += board[j][i]
        
        # 대각선
        diag_1 += board[i][i]
        diag_2 += board[i][len(board)-1-i]
        if not vertical : cnt += 1
        if not horizontal : cnt += 1
    if not diag_1 : cnt += 1
    if not diag_2 : cnt += 1
    return cnt

빙고 문제는 풀리긴 풀리는데 깔끔하게 짜기가 어려웠다.

 

 

2) 리뷰받은 뒤 수정

def solution(board, nums):
    N = len(board)
    nums = set(nums)
    answer = 0
    
    for i in range(N):
        for j in range(N):
            if board[i][j] in nums:
                board[i][j] = 0

    answer += len([i for i in board if sum(i) == 0])
    answer += len([i for i in zip(*board) if sum(i) == 0])
    answer += int(sum(board[i][i] for i in range(N)) == 0)
    answer += int(sum(board[N - 1 - i][i] for i in range(N)) == 0)

    return answer

column을 간단하게 출력하려면 numpy 라이브러리를 써야만 되는 줄 알았는데 

zip(*배열 이름) <= 이런 식으로 하면 라이브러리를 쓰지 않고도 가져올 수 있다는 걸 새로 알았다.

 

---

< 4. 방문 길이 >

1. 나의 코드

def solution(ways):
    move = {'U' : [0, 1], 'D' : [0, -1], 'R' : [1, 0], 'L' : [-1, 0]}
    cur_pos = (0, 0)
    visited_paths = set()
    limit = list(range(-5, 5+1))
    
    for way in ways:
        x, y = move[way] 
        new_pos = (cur_pos[0] + x, cur_pos[1] + y)
        # 좌표 범위에 있는지 체크
        if new_pos[0] not in limit or new_pos[1] not in limit: continue
        # 이미 왔었던 좌표인지 체크
        if new_pos not in visited_paths:
            visited_paths.add((*cur_pos, *new_pos))
            visited_paths.add((*new_pos, *cur_pos))
            cur_pos = new_pos
    return len(visited_paths) // 2

 

2. 피드백받은 부분

0 <= new_pos[0] < n

x, y좌표의 범위 체크를 할 때 이런 식 말고, limit라는 배열을 만들어서 하는 게 더 깔끔해 보여서 배열에서 In을 통해 검색으로 range 체크를 했는데 배열보다는 0 <= x < n 이런 식으로 하는 게 효율성이 더 좋다는 이야기를 들었다.

 

---

< 5. 짝지어 제거하기 >

 

1. 코드 리뷰 전

from collections import deque

def solution(strings):
    if len(set(list(strings))) == 1: return 0

    stack = deque([])
    
    for letter in strings:
        if not stack or letter != stack[-1]: stack.append(letter)
        elif letter == stack[-1]: stack.pop()
    return int(len(stack) == False)

 

2. 코드 리뷰

정답을 return 하는 마지막 부분에서 피드백을 받았다.

약간의 버릇으로 False는 0이나 마찬가지라는 생각으로 문제 풀 때나 코드 짤 때 int랑 바로 비교하고 그랬는데 주의해야겠다.

 

3. 수정한 코드 

from collections import deque

def solution(strings):
    if len(set(list(strings))) == 1: return 0

    stack = deque([])
    
    for letter in strings:
        if not stack or letter != stack[-1]: stack.append(letter)
        elif letter == stack[-1]: stack.pop()
    return int(len(stack) == 0)

False(Bool) 형과 비교하는걸 0과 비교하는 걸로 바꿔줬다.

python에서는 바로 비교하는 게 상관없지만 다른 언어를 사용할 때는 예외가 있을 수도 있으니까 앞으로는 신경 써야겠다.

---

< 6. 사전 순 부분 문자열 > 

1. 수정 전

def solution(strings):
    ans = []
    for letter in strings:
        while ans and ord(ans[-1]) < ord(letter):
            ans.pop()
        ans.append(letter)
    return ''.join(ans)

 

2. 피드백 수정 후

def solution(strings):
    ans = []
    for letter in strings:
        while ans and ans[-1] < letter:
            ans.pop()
        ans.append(letter)
    return ''.join(ans)

Python에서는 문자열끼리 비교할 때 굳이 ord를 사용해 형 변환하지 않아도 비교가 되기 때문에 ord는 생략해도 된다는 피드백을 받았다.

 

---

< 후기 >

2주 차는 Stack과 Hash 알고리즘 문제를 풀었다.

Stack 문제는 많이 익숙하지만 Hash 같은 경우는 생소했는데, 스터디 참여 전 스터디 커리큘럼을 봤을 때 Hash 문제는 다른 알고리즘에 비해서 많이 풀어보지 않았기 때문에 혹시라도 막힐까 봐 미리 공부를 많이 해뒀다.

 

정리하자면 Hash는 O(1) 시간 복잡도 만에 검색이 가능한 빠른 성능 덕분에 데이터 베이스나 네트워크 라우터에서도 유용하게 쓰인다.

 

알고리즘 문제를 풀 때는 특별한 건 없다.

파이썬으로 설명하자면, 특별히 따로 구현하는 건 아니고 Dictionary나 Set을 사용해 검색할 내용을 담는다.(방문한 좌표 확인, 데이터 유무, 일치 확인 등등..) O(1) 시간 안에 탐색이 가능하기 때문에 효율성이 중요한 문제에서 사용한다.

 같은 문제를 list로도 풀 수 있지만 list의 검색(in)은 O(N)이기 때문에 Hash의 O(1)과 비교하면 시간이 많이 걸린다. 데이터가 작은 경우엔 괜찮겠지만, 큰 경우라면 시간이 엄청나게 차이 난다.

Hash는 미리 공부한 거에 비해서 특별한 건 없어서 좀 허무하긴 했다 ㅋㅋ

알고리즘 코드 짤 때 list에서 in으로 검색을 많이 했는데, 효율성을 위해 list보다는 set이나 dictionary를 사용해야겠다.