개발새발

35. Search Insert Position[문제]정렬된 정수 배열 nums와 목표 값 target타겟이 배열에 존재하면 인덱스를 반환존재하지 않으면 정렬된 순서를 유지하면서 삽입될 위치를 반환해야 한다.[문제 조건]배열 nums는 오름차순으로 정렬되어 있다.배열의 길이는 0 배열의 원소는 -10^4 타겟 값은 -10^4 시간 복잡도는 O(log n)[코드 1]이진탐색 버전 (시간복잡도 O(log n) )def search_insert(nums, target): left, right = 0, len(nums) - 1 while left [코드 1 설명]이진 탐색 사용:left와 right로 배열의 양끝을 설정하고, 중간값 mid를 계산해가며 탐색.조건 비교:nums[mid] == targe..

28. Find the Index of the First Occurrence in a String [문제 설명]문자열 haystack에서 부분 문자열 needle이 처음 등장하는 인덱스를 반환하라.needle이 haystack에 없다면 -1을 반환한다.[문제 조건]needle이 빈 문자열이면 0을 반환한다.needle이 haystack에 없는 경우 -1 반환.[코드]public int strStr(String haystack, String needle) { if (needle.isEmpty()) return 0; int hLength = haystack.length(); int nLength = needle.length(); // haystack의 길이가 needle보다 짧으면 -1..

27. Remove Element [문제 설명]정수 배열 nums, 특정 값 val 이 주어지면, 정수 배열 내에 있는 요소들 중 val과 같은 요소를 제자리에서 삭제한다.삭제 후 남은 요소의 개수를 반환한다.[문제 조건]배열 nums에서 모든 val 값을 제자리에서(in-place) 삭제해야 한다.삭제 후에는 배열에 val과 같지 않은 요소들만 남아야 한다.정렬 순서가 바뀌어도 상관없다.배열의 첫 k개의 요소가 val과 같지 않은 값들로 채워져 있어야 한다.[코드]class Solution(object): def removeElement(self, nums, val): """ :type nums: List[int] :type val: int :rt..

26. Remove Duplicates from Sorted Array [문제]정렬된 정수 배열 nums에서 중복을 제거하여 배열의 고유한 원소들로만 이루어진 부분을 반환해야 한다.중복을 제거한 후에도 배열의 순서는 유지되어야 하며, 중복을 제거한 후의 길이를 반환해야 한다. 배열의 첫 k개의 요소가 중복이 제거된 부분을 나타낸다. [문제 조건]정렬된 배열이 주어지기 때문에, 중복된 숫자들이 연속해서 등장한다.추가 공간을 사용하지 않고, 제자리에서(in-place) 중복을 제거해야 한다.새로운 배열이나 추가 자료구조(Set 등)를 사용하면 안 된다.반환값으로 중복이 제거된 배열의 길이(k)를 반환한다.첫 k개의 요소가 중복을 제거한 상태여야 한다.Set을 사용하면 순서가 보장되지 않아 문제 요구사항을 만..

https://leetcode.com/problems/median-of-two-sorted-arrays/[문제 설명]두개의 정렬된 배열(nums1, nums2)이 주어졌을 때, 두 배열의 중앙값 찾기단, 시간 복잡도는 O(log(m+n)) * m : nums1의 길이, n : nums2의 길이 [주의사항]중앙값을 찾아야하네? -> 두 배열을 합쳐서 정렬한 뒤 중앙값을 찾자 (XXXXXXX)배열을 합치고 정렬하는 방식의 시간 복잡도는 O((m+n) log(m+n))이기 때문에 문제의 조건과 어긋남 [접근 방법]1. 병합하지 않는다 2. 짧은 배열에 대해 이진 탐색(Binary Search)을 수행한다짧은 배열에 대해 이진 탐색을 하는 이유는 탐색 범위를 줄여서시간 복잡도를 O(log(min(m,n))로 제..