Algorithm/LeetCode
LeetCode #561 - Array Partition I(배열 파티션 1) 풀이
문제 문제에서는 길이가 2n인 정수 리스트를 입력받고, 정수를 n쌍으로 묶은 후 각각의 쌍의 최소값을 합한 결과가 최대가 되도록 하여 반환할 것을 요구하고 있다. 내용을 이해하는데 약 30분 정도 소요되었으며, 생각보다 간단하게 해결할 수 있었다. 길이가 6인 정수 리스트를 입력 받는 경우 n은 3이 되고, 리스트를 3조각으로 나누고, 나누어진 조각의 최소값들을 모두 더했을때 가장 큰 값이 되어야 하는 것이다. 풀이 입력받는 리스트를 오름차순으로 정렬하고, 합계를 0으로 초기화한다. nums.sort() sum = 0 입력받은 리스트를 반복하면서 짝수(0, 2, ..., 2n) 번째 인덱스에 해당하는 값을 1의 합계에 더하고, 반복이 종료되면 합계를 반환한다. for i in range(0, len(nu..
Algorithm/LeetCode
LeetCode #015 - 3Sum(세 수의 합) 풀이
문제 문제에서는 정수 값을 리스트로 입력받아 세 개의 요소로 구성된 2차원 리스트(ex) [[i, j, k], [x, y, z]]로 반환할 것을 요구하고 있다(이때, 하나의 리스트([i, j, k])의 값은 서로 중첩되면 안 되며, 요소의 합이 0이 되어야 한다). 약 2시간 동안 다음과 같은 두 번의 시도를 하였는데 모두 실패하였고, 결국에는 교재의 풀이 과정을 들여다볼 수 밖에 없었다. 세 개의 요소를 가진 리스트를 만들기 위해 반복문으로 접근하였으나 시간 초과로 인해 실패하였다. 교재에서 언급한 투 포인터 방식과 유사하게 구현은 하였으나, 중복 제거 처리 및 이미 확인한 값을 건너뛰는 코드를 구현하지 않아 실패하였다. 실패 내용 중 첫 번째 방식과 같이 매우 단순 무식한 알고리즘을 브루트 포스라고 ..
Algorithm/LeetCode
LeetCode #021 - Merge Two Sorted Lists(두 개의 연결 리스트 병합) 풀이
문제 문제내용을 살펴보면, 정렬된 두 개의 연결 리스트의 노드를 결합하여 다음 그림과 같이 하나의 정렬된 연결 리스트로 병합하여야 한다. 본 내용은 leetcode에서 제공한 아래 그림을 토대로 작성하였기 때문에 그림 1(node2로 이동), 그림 5(node1로 이동)와 같이 값이 동일한 경우 포인터를 어디로 변경할 것인지 헷갈릴 수 있다. 결론만 말하자면, 두 개의 노드 값이 동일한 경우 node1, node2 중 아무거나 선택해도 무방하다. 풀이 문제에서 주어진 예시(list1 = [1, 2, 4], list2 = [1, 3, 4])를 그림으로 나타내면 다음과 같다. 이 둘은 노드의 값을 기준으로 오름차순으로 정렬되어 있으며, 가장 왼쪽에 있는 노드가 각 연결 리스트의 head라고 할 수 있다. 그..