Two Sum
문제는 쉬웠지만 여러가지 방식으로 접근할 수 있어서 흥미로운 문제였다.
내가 접근한 방법은 Brute-force였다. 간단하게 그냥 모든 경우의 수를 다 따져보는 방식이었다.
# Python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
indice = [i for i in range(len(nums))]
for pair in combinations(indice, 2):
if nums[pair[0]] + nums[pair[1]] == target:
return pair
return [0, 0]
그런데 Solution을 보니 a + b = target -> a = target - b라는 점을 이용해 dictionary로 O(n)만에 탐색을 끝내는 신박한 방법이 있었다. 그래서 java로 다시 풀어보았다.
// Java
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> visited = new HashMap<Integer, Integer>();
for(int i = 0; i< nums.length; i++){
int a = target - nums[i];
if(visited.containsKey(a)){
return new int[]{ visited.get(a), i};
}
visited.put(nums[i], i);
}
return new int[]{0, 0};
}
}
파이썬 알고리즘 인터뷰 책에도 이 문제에 대한 다양한 해설이 나와있어서 함께 참고해가며 다른 풀이들을 공부했는데, 재밌었다.
Reverse Integer
문자열로 바꿔서 열심히... 굳이 힘들게 풀었다. 사실 long이나 double을 사용하면 안된다는 제약이 있어서 문자열 생각밖에 못했다.
class Solution:
def reverse(self, x: int) -> int:
max_val, min_val = str(2**31 - 1), str(-2**31)
target = ''
signed = False
for w in reversed(str(x)):
if w == '-':
signed = True
continue
target += w
target = str(int(target))
if signed:
target = '-' + target
if(len(min_val) < len(target)): print(0)
if(len(min_val) == len(target) and min_val < target): return 0
else:
if(len(max_val) < len(target)): print(0)
if(len(max_val) == len(target) and target > max_val): return 0
return target
Discussion에 java 예쁜(?) 해답이 있었는데 제대로 이해하지 못해서 댓글에 있는 유튜브 강의를 참고했다.
처음에는 코드가 간단한데 왜 난 이해를 못하지? 싶었는데 아니었다. 난 바보가 아니었다.
숫자를 더해나가다가 overflow 혹은 underflow가 발생되는 시점이 오면 random junk unexpected value가 그 자리를 대신하게 된다. 그 사실을 알고나니 코드가 이해되었다. (그걸 모르는게 바본가..?😳)
Remove Duplication
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
checked = set()
current = head
prev = None
while current:
if current.val in checked:
prev.next = current.next
current = prev
else:
checked.add(current.val)
prev = current
current = current.next
return head
위의 코드를 작성하면서 고려해야할 케이스가 크게 두 가지였다.
- delete할 노드의 앞 노드에 대한 정보
- Singly LinkedList였기 때문에 현재 바라보고 있는 노드를 삭제해주기 위해서는 앞에 있는 노드의 정보가 필요했다. 그래서 prev를 만들어주었다.
- Singly LinkedList였기 때문에 현재 바라보고 있는 노드를 삭제해주기 위해서는 앞에 있는 노드의 정보가 필요했다. 그래서 prev를 만들어주었다.
- 중복 체크
- 체크된 정보인지 아닌지를 추적하기 위해서 checked라는 set을 만들었다. (set으로 만든 이유는 탐색시간을 O(1)으로 만들기 위해서)
근데 다른 해답을 보고서..ㅎ 괜한 고민이었다는 생각이 들었다.
- current와 current.next를 동시에 null인지 아닌지 체크해주면서 로직을 수행하면 된다. 이렇게되면 prev가 필요없다.
- Sorted Linked List이기 때문에 그냥 현재 노드가 이전 노드와 같은 data인지만 확인해주면 중복 체크는 끗(왜 sorted인거 생각을 못했을까)
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
current = head
while current and current.next:
if current.next.val == current.val:
current.next = current.next.next
else:
current = current.next
return head
* 파이썬에서는 매번 값을 비교하는 연산보다 in 연산이 더 빠르다. 그리고 파이썬의 set()은 hash table로 구현되었기 때문에 in 연산이 O(1)이다.
'코테 준비' 카테고리의 다른 글
[프로그래머스/2019 카카오 개발자 겨울 인턴십/python] 불량사용자 (2) | 2021.01.25 |
---|---|
[프로그래머스 / 그리디(Greedy) /python] 큰 수 만들기 (0) | 2021.01.24 |
[프로그래머스/카카오 블라인드 테스트 2018/python] 추석트래픽 (0) | 2021.01.12 |
[프로그래머스/python] 가장 큰 수 (0) | 2021.01.10 |
[프로그래머스/카카오 블라인드 테스트 2020/python] 자물쇠와 열쇠 (0) | 2021.01.08 |