Today I learned
2022/01/17
회고록
1/17
항해 99, 알고리즘 1주차
교재 : 파이썬 알고리즘 인터뷰
7장 배열
1. 이론
파이썬의 배열은 여러 원소를 하나의 묶음으로 관리하고 각 원소간에는 순서(order)가 존재하여 인덱스(Index)를 통해 접근하는 리스트로 파이썬에서는 리스트(list)와 튜플(tuple)이라는 두가지 타입이 있습니다. 통상 프로그래밍 언어에서 배열은 동일한 데이터 타입의 원소들로 구성되지만 파이썬에서는 각 원소의 데이터 타입이 동일하지 않아도 되고 심지어 다른 배열을 원소로 갖는 것도 허용 됩니다. 배열간의 비교는 동일 인덱스 끼리 각각 비교해 가는 방식으로 적용 됩니다.
■ 리스트(list)와 튜플(tuple)
리스트(list)는 [1, 2, 3] 형태로 정의하며 각 원소를 수정 할 수 있는 특성을 갖습니다. []는 빈 list를 의미 합니다.
b = [1,"aa",3,4,5]
type (b)
<type 'list'>
튜플(tuple)은 (1, 2, 3) 형태로 정의하며 한번 정의한 원소를 수정 할 수 없는 특성이 있습니다. 튜플 원소에 대한 수정 작업은 "TypeError: 'tuple' object does not support item assignment" 같은 오류를 발생시킵니다. 원소의 추가 및 삭제도 할 수 없습니다. ()는 빈 tuple을 의미한다. 주의할 점은 원소가 하나만 있는 tuple은 일반적인 괄호와 구분이 되지 않기 때문에 ('A',)와 같이 기술하면 tuple임을 명시할 수 있습니다. 원소를 교체하거나 추가 하는 등의 작업은 새로운 튜플을 생성하는 방법으로만 가능 합니다. 아래의 예에서는 첫원소를 대문자 'A'바꾼 새로운 배열로 교체 했습니다.
b = ( 1, "aa", [3, 4, 5], 6, 7)
type (b)
<type 'tuple'>
t = ('a', 'b', 'c', 'd', 'e')
t = ('A',) + t[1:]
t
('A', 'b', 'c', 'd', 'e')
배열 내부에 또다른 배열을 갖는 경우 해당 원소에 대한 접근은 b[2][0]같은 방식으로 인덱스를 지정 합니다. 파이썬에서 배열의 인덱스는 0부터 시작합니다. 배열 내부에 이미 정의한 다른 배열 변수를 포함시키면 포함된 배열을 참조하는 형태로 관리되어 포함된 배열을 수정하면 포함한 상위 배열도 같은 내용을 보게 됩니다. 아래 예제를 보면 a 배열이 b 배열을 포함했는데, b[2][0]을 'test'로 변경했을때 a배열에도 동일한 내용이 반영되는 것을 확인할 수 있습니다.
print b
(1, 'aa', [3, 4, 5], 6, 7)
print b[2]
[3, 4, 5]
print b[2][0]
3
a = [3, b, 'aaa']
print a
[3, (1, 'aa', [3, 4, 5], 6, 7), 'aaa']
b[2][0] = 'test'
print a
[3, (1, 'aa', ['test', 4, 5], 6, 7), 'aaa']
2. 문제
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = []
Output: []
Example 3:
Input: nums = [0]
Output: []
Constraints:
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
https://leetcode.com/problems/3sum/
3. MySol
def sum_three_num_func(nums):
result = []
for pivot in range(len(nums)):
j = pivot + 2
for i in range(1,len(nums)-1):
j=i+1
while (True):
print('pivot : ' + str(pivot) + ', i : ' + str(i) + ', j : ' + str(j))
# 여기에 구현
if (nums[pivot] + nums[i] + nums[j] == 0):
temp = []
temp.append(nums[pivot])
temp.append(nums[i])
temp.append(nums[j])
result.append(temp)
if j >= (len(nums) - 1):
break
j += 1
if i >= len(nums) - 2:
break
return result
if __name__ == '__main__':
nums = [-1, 0, 1, 2, -1, -4]
result_for_print = sum_three_num_func(nums)
print('result : ' + str(result_for_print))
나는 3개의 pivot,i,j 반복문을 이용한 부르트 포싱 계산을 하였으나, 책에서는 투포인터 방식의 해답을 내놓았다.
여기서부터 부르트포싱을 이용한 방법은 답은 나오지만, 효율성 통과를 하지 못해 리트코드에 코드가 Accept 되지 못한다.
책에서 제시한 투포인터 방식은 i를 두고, j와 k가 남은 문자열의 양 끝에서부터 조여오는 방식이다.
게다가, sort를 하고 시작하여 합계가 클 때와, 작을 때를 구분하여 j를 우측으로 움직이거나, k를 좌측으로 움직이는 알고리즘이다.
4. 배운 점
-
투포인터 : 앞에 pivot을 두고 한칸씩 전진한다. 동시에 뒤에 두 포인터를 양 끝에 둔다. 이때, sum이 0보다 작으면, j를 우측으로 움직여 합계를 키우고, 0보다 크다면 k를 좌측으로 움직여 합계를 줄인다.
-
부르트포스 방식 : 타임아웃
투포인터 : 884ms
5. 총평
투포인터 방식 익숙해지기
