IT/자기계발 ( Leetcode )
2021-01-10] Create Sorted Array through Instructions
Bell_bear
2021. 1. 11. 00:14
반응형
오늘의 문제:
이번 문제는 이해가 조금 어려웠다.. ( 아직 필자는 답을 만들진 못했다.)
예시를 보며 문제를 이해해보자.
입력값으로 배열을 주어지면, 정렬을 하면서 생긴, cost 값에 대해서 최소값에 대해 합을 구하는 문제이다.
cost라는 것의 비교값으로 주어지는 것들은 정렬을 하면서 정렬값이 되었을때, 왼쪽의 원소의 개수와
오른쪽의 원소의 개수이다.
1번 예시를 보며 이해해보자.
1) 첫번째 값 1을 넣으면 값이 하나이기에 양옆의 값은 0 , 0 min은 0이고,
2) 두번째 값 5를 넣으면 5는 1보다 커서 뒤에 붙게된다. 즉, 왼쪽 원소 1개와 오른쪽원소 0개로 min은 (1,0) = 0이다.
3) 세번째 값 6도 2)와 마찬가지로 맨뒤에 붙고 왼쪽 원소 2개, 오른쪽 원소 0개로 min은 (2,0) =0 이다.
4) 마지막으로 2는 1보다 크고 5보다 작아서, [1,2,5,6]을 만들게 된다. 이때 왼쪽은 1개, 오른쪽은 2개의 원소값이 존재하고 이 때 min은 (2,1) = 1 이다. 총 cost의 값은 0 + 0 + 0 + 1 = 1 의 공식이 성립하게 된다.
이해한 바대로 문제를 풀이해보았다.
문제풀이 1차 시도 실패)
최대한 줄였으나, 좀더 줄여야 하는 듯.. 모든 test case를 통과하진 못하였다. ㅠㅜ
class Solution(object):
def createSortedArray(self, instructions):
"""
:type instructions: List[int]
:rtype: int
"""
ans=[]
minval=0
for i in range(len(instructions)):
tval=0
ti=0
large=0
if ans!= [] and instructions[i] >= max(ans):
ti=len(ans)
else:
if instructions[i] in ans:
pivot=ans.index(instructions[i])
cnt=ans.count(instructions[i])
ti=len(ans[:pivot])
large=len(ans[pivot+cnt:])
else:
for idx in range(len(ans)):
if instructions[i] > ans[idx]:
tval=instructions[i]
ti=idx+1
else:
large=len(ans)-ti
break
ans.insert(ti,instructions[i])
minval = minval + min(large,ti)
#print(ans,minval)
#print(minval)
#print(ans)
return minval
반응형