[Python] 손코딩 케이스 모음(3)
손코딩에 빈출하는 사례들을 정리
nums = [2,2,1] 처럼 주어질때 유일한 숫자를 리턴하라
# hashmap 이용 - 시간복잡도 O(N) 공간복잡도 O(N)
# nums = [4,1,2,1,2]
my_dict = {}
for n in nums:
if n in my_dict:
my_dict[n] += 1
else:
my_dict[n] = 1
answer = [k for k,v in my_dict.items() if v == 1]
answer[0] # 4
# XOR 사용
answer = 0
for n in nums:
answer ^= n
nums = [-2,1,-3,4,-1,2,1,-5,4] 처럼 주어질 때 합이 최대인 subarray를 리턴하라
max_v = nums[0]
a_sum = [nums[0]]
for i in range(len(nums)):
hubo = max(nums[i], a_sum[-1]+nums[i])
a_sum.append(hubo)
if hubo > max_v:
max_v = hubo
print(max_v)
sorted 된 array가 주어졌을 때 target_value가 있는 인덱스 혹은 들어갈 인덱스를 리턴하라
def find_index(nums, target):
low = 0
high = len(nums)-1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
high = mid-1
else:
low = mid+1
return low
# nums = [1,3,7]
# target = 8 --> low = 3, high = 2
# target = 6 --> low = 2, high = 1
# 둘 다 low 위치
숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열 가능하다.
combinations = [2,3,6,7]
target = 7
answer = []
def combination(cum_sum, path, start):
if cum_sum >= target:
if cum_sum == target:
answer.append(path)
return
for i in range(start, len(candidates)):
combination(cum_sum + candidates[i], path + [candidates[i]], i)
서로 다른 정수를 입력 받아 가능한 모든 순열을 리턴하라 - 순열
arr = [1, 2, 3]
n = len(arr)
visited = [False]*n
answer = []
def permutation(depth, result):
if depth == n:
# 리프 노드일때 결과 추가
answer.append(result)
return
for i in range(len(my_list)):
if not visited[i]:
visited[i] = True
permutation(depth+1, result+[my_list[i]])
visited[i] = False
전체 수 n을 입력받아 k개의 조합을 리턴하라 - 조합
# 조합
# 전체 수 n을 입력받아 k개의 조합을 리턴하라
n = 4
k = 2
arr = [x for x in range(1,n+1)]
visited = [False]*n
answer = []
visited = [False]*n
def combination(depth, result, start):
if depth == k:
answer.append(result)
return
for i in range(start, len(my_list)+1):
if not visited[i]:
visited[i] = True
combination(depth+1, result+[arr[i]], i)
visited[i] = False
combination(0,[],0)
print(answer) # [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
