문제
입력과 출력
코드
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
for i in range(len(nums)):
if nums[i]==target:
return i
else:
nums.append(target)
nums.sort()
return nums.index(target)알고리즘
nums 배열에서 target과 같은 요소가 있으면 그 요소의 인덱스를 반환한다.
만약 배열 안에 target과 같은 요소가 없으면, target을 배열에 넣어 정렬해준 뒤에
이 target의 인덱스를 반환해준다.
회고
처음엔 문제를 너무 대충보고..ㅎ 그냥 배열 안에 target이 있으면 탐색한 수를 반환해주면 되는 줄 알았다.. ㅎㅎ
답이 틀리고 또다시 천천히 읽어보니
target이 없을 때도 이 target이 들어간다면 몇번째 인덱스에 있을지까지 반환해주어야 한다 !
이 부분을 어떻게 구현하지? 크기비교를 해야하나? 하고 고민하다가 번뜩인 생각..!! 없으면 리스트에 넣어서 정렬하면 위치를 알 수 있다는 것..!!!
그랬더니 바로 완성!
런타임은 좀 긴편인 것 같지만.. 다른 풀이가 떠오르지 않았다
다른 분들의 풀이를 보니 이진탐색으로 푼 풀이가 대부분이었다..
사실 생각해보면 파이썬 내장함수덕에 내 알고리즘이 짧아질 수 있었던 것,,
내장함수가 아니었다면 아마 이진탐색으로 풀어야했지 않을까 싶었다..
알고리즘 공부를 놓치지 않기 위해 내장함수를 쓰는 것도 좋지만 크기 비교나 이진탐색, 트리 등을 직접 구현해보는 연습도 필요할 거 같다.
풀이세션
이런식의 풀이는 이해를 잘하고 푼게 맞지만, 조건이 시간복잡도 logN이라서
...
이 풀이는 최악의 경우에 리스트를 다 돌면 N이 되기 때문에, 이진탐색으로 푸는게 낫다..!
다시 풀이를 도전해봐야겠다..
공부..일기....