Leetcode(1)

introduction

python 에 익숙해질 겸 leetcode easy 문제만 풀고 있는데, 생각할 만한 부분, 기록할 만한 부분들을 모았다. 포스팅이 너무 길어지는걸 방지하기 위해, 5문제가 쌓일 때 마다 올리려고 한다.

problems

125: valid-palindrome

문제 링크

1. map(func, input) 결과를 list() 를 이용해서 바로 list 로 바꿔버릴 수 있다.

lowered = "".join(list(map(tolower, s)))

1. map 할 필요 없이, filter 를 이용해도 됐다.
2. str.isalnum 으로 alphanumeric filter 가능하고, str.lower 쓰면 굳이 map 이 필요없었다.

s1 = ''.join(filter(str.isalnum, s))

190: reverse-bits

문제 링크

1. input 을 binary 로 formatting 하고, leading zeros 를 더해주는 방식으로 생각했다.

class Solution:
    def reverseBits(self, n: int) -> int:
        x = f'{n:b}'    # binary format using f-string
        start = "".join(['0'] * (32-len(x)) + list(x))
        return int(start[::-1],2)

나쁜 방법은 아닌것 같은데, bit 연산과 조금 더 친해질 필요가 있다.

1. 문자열을 뒤집지 않고, 맨 뒷자리 부터 2**31, 30, ... 곱해서 더해주는 방식으로 접근한다.

class Solution:
    def reverseBits(self, n: int) -> int:
        ans, shift = 0, 31
        while n:
            ans = ans + ((n & 1) << shift)
            n >>= 1
            shift -= 1
        return ans

1720: Decode XORed Array

문제 링크

XOR(이하 ^, golang, python 에서 ^ 이다.) 에 대해 생각을 좀 해봤다.

1. 같은 값은 0으로, 다른 값은 1 이다.

이런 특성을 이용해서, 한 숫자를 제외하고 쌍으로 존재하는 list 에서, 1개만 있는 숫자를 찾아내는 문제에서, list 의 모든 값을 XOR 하다보면 찾던 숫자가 나타난다.

1^1 = 0
0^0 = 0
1^0 = 1
0^1 = 1

1. 교환법칙이 성립한다.

• 당연한게, 1^1, 0^0 은 0 이고, 0^1, 1^0 은 1 이므로, 교환해도 똑같을것이다.

1. XOR 의 역함수는 XOR 이다.

출처

a = a^b^b 이다. (b^b 는 0 이고 a^0 은 a 일것이다) 만약 c = a^b 라면

a = c^b (혹은 b^c)      
b = c^a (혹은 a^c)

위의 내용을 종합해봤을때, hidden array 의 첫번째 값(first)이 주어졌으니 XOR 해가면 된다. 아래 식에서 arr[-1] 대신 encoded 를 enumerate 하거나, idx 로 접근하는 방법도 있겠지만, 귀찮았다.

class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]:
        arr = [first]
        for e in encoded:
            arr.append(e ^ arr[-1])
        return arr

1710: Maximum Units on a Truck

문제 링크

뻔한 greedy 와 sort 문제이다. 문제 해결보다는, python3 에서 2차 sort 인 경우에 lambda 를 이용해서 정렬을 하는 게 익숙하지 않았다.

# boxTypes: [[1,3],[2,2],[3,1]]
s = sorted(boxTypes, key=lambda x: x[1], reverse=True)
"""
    아래와 같이 reverse 를 생략할수도 있겠고
    s = sorted(boxTypes, key=lambda x: -x[1])

    아래와 같이 튜플을 이용해서 1차, 2차 key 지정도 가능하다
    s = sorted(boxTypes, key=lambda x: (x[0], x[1]))
"""

1700: Number of Students Unable to Eat Lunch

문제 링크

처음엔 deque 로 students 를 바꿔서, popleft, append 해가며 sandwiches 의 0번 값과 비교하는 접근이었다. 이유는 결국 111 이 남은 경우에 샌드위치가 011 이라면 학생들이 계속 돌아도 끝낼 수 없기 때문이었다. 따라서, 학생들을 돌리며 학생 length 만큼 count 가 쌓이면 terminate 하는 방식이었다.

하지만, 다른 답안을 보며 생각을 해보니 남은 샌드위치 입장에서 이 샌드위치를 먹어줄 학생이 있는지 여부만 확인하면 된다.

따라서, 처음에 학생수 count 를 세고, 샌드위치를 0~len(sandwiches) 까지 iterate 하면서 현재 샌드위치를 먹을 학생이 있는지 counter 에서 decrement 하면 문제 해결이된다.

import collections

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        c = collections.Counter(students)
        idx, end = 0, len(sandwiches)

        while (idx < end) and c[sandwiches[idx]]:
            c[sandwiches[idx]] -= 1
            idx+=1
                
        return end-idx