개발새발

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))로 제..

https://leetcode.com/problems/add-two-numbers/ 알고리즘 문제를 풀다 보면, 가끔은 나도 모르게 ‘답만 나오면 된다’는 식으로 접근할 때가 있다.그런데 이번 문제를 풀면서 Linked List라는 자료구조의 본질적인 구조와 연결 방식을 다시 생각하게 됐다.단순한 구현 문제처럼 보여도, 기초를 다지는 데 정말 좋은 문제였던 것 같다.그래서 이 문제는 그냥 넘기지 않고, 블로그에 기록해두기로 🤭 [문제 간단 요약]두 개의 역순으로 저장된 Linked List가 있고, 각 노드는 한 자리 숫자를 담고 있다.이걸 실제 정수처럼 더해서, 결과를 똑같이 역순 Linked List로 리턴하기Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 0..