코딩테스트

역순으로 저장된 연결 리스트의 숫자를 더하라. 두 수의 합을 연결 리스트로 만드는 문제이다. 먼저 역순으로 저장되어 있는 리스트의 숫자를 더할 수 있도록 숫자로 만들어준다. num1, num2 = [], [] while l1: num1.append(str(l1.val)) l1 = l1.next while l2: num2.append(str(l2.val)) l2 = l2.next num1.reverse() num2.reverse() num1, num2 = int(''.join(num1)), int(''.join(num2)) num = str(num1 + num2) 배열로 연결 리스트의 값을 받은 뒤 뒤집어서 합쳐준다. 그 다음, 두 숫자를 더한 결과 값을 num에 저장한다. 그 다음 결과 값을 다시 역순 ..

연결 리스트를 뒤집어라. 재귀로도 뒤집을 수 있지만, 더 간단히 반복문으로 뒤집어 본다. 먼저 이전 node를 기억할 수 있는 prev를 설정한다. node = head prev = None 그 다음 node가 끝날 때 까지 아래 작업을 반복한다. while node: next = node.next node.next = prev prev = node node = next next 는 원래 node의 다음 노드를 가리킨다. 뒤집기 전 앞으로 나아갈 포인터를 저장하는 것이다. node.next를 이전 node로 변경한다. 즉 뒤집는 작업을 진행하는 것이다. 그 후, prev 노드를 현재 노드로 설정하고, node를 앞서 저장한 next 값으로 바꾸어 원래 리스트의 node.next로 진행한다. 이 작업이 다..

정렬되어 있는 두 연결 리스트를 합쳐라. 연결 리스트의 정의는 앞의 문제와 같다. 여기서 리스트는 작은 숫자 순으로 정렬되어 있다. 이런 2리스트를 합치기 위해 여러 방법이 있지만 책에서는 재귀를 이용한 방법으로 깔끔하게 풀어 이를 구현하여 보았다. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: if (not li..

연결 리스트가 팰린드롬 구조인지 판별하라. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next 위의 코드가 문제에서 제시한 연결 리스트이다. val 은 현재 노드의 값, next는 다음 노드를 가리키는 것이다. 먼저 연결 리스트를 팰린드롬인지 확인하기 위해서는 자료형을 변경해야한다. 파이썬에는 deque라는 자료구조가 있다. deque는 리스트와 같지만 append와 pop을 리스트 마지막이 아닌 처음에서도 할 수 있다는 특징이 있다. 먼저, 해당 연결 리스트를 deque 자료형으로 변경한다. queue = deque() w..

한 번의 거래로 낼 수 있는 최대 이익을 산출하라. 구하는 방법은 간단하다. 저점에 사서 고점에 파는 것이다. 가장 쉽게 구하는 방법은 현재 시점에서 가장 높게 팔 수 있는 가격과의 차이를 구하여 비교하는 방법인데 이 방법은 n의 제곱으로 매우 오래 걸린다. 이를 O(n)에 해결하기 위해 저점을 구한 후, 가격차이 값을 갱신해 가며 max 값을 구하는 방식으로 해결한다. 먼저, 저점과 이익의 값을 초기화 한다. min_price = sys.maxsize profit = 0 그 다음 price 값을 살펴보며, 저점을 설정하고 저점과 현재 가격의 차이를 비교하여 최대 이익을 갱신한다. for price in prices: min_price = min(min_price, price) profit = max(p..

배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라. - 주의 : 나눗셈을 하지 않고 O(n)에 풀이하라. 이 문제를 보고 맨처음 든 생각은 전체곱에서 나누는 것이다. 그런데 나눗셈을 하면 안된다고 적혀있으니 다음 방법은 본인을 제외한 모든 수를 곱하는 것인데 이 또한 n 제곱의 시간이 걸리므로 불가능 하다. 보통 이러할 때 쓸 수 있는 방법은 시간 대신 메모리를 쓰는 것이다. 본인의 왼쪽까지의 순차적으로 누적 곱을 저장한 배열과 본인의 오른쪽 까지의 순차적으로 누적 곱을 저장한 값을 활용하여 문제를 풀이한다. 예를들어, [1,2,3,4] 라는 배열이 있다고 가정하자. 먼저 자신의 왼쪽 까지의 순차적 곱을 정리한 배열은 [1, 1, 2, 6]이 될 것이다. ..