전체 글657 [leetcode][268] Missing Number 문제 : leetcode.com/problems/missing-number/ 고유한 숫자 배열 nums가 주어질 때, 0~n 까지 수 중 누락된 수를 구하라. 누락된 수는 0~n까지 수들의 합에서 nums배열의 합을 뺀 값과 같다. 0~n까지 수들의 합은 등차수열의 합 공식으로 n(n+1)/2로 구할 수 있고, nums배열의 합은 배열을 한 번 탐색하면서 구할 수 있다. 시간복잡도는 O(n), 공간복잡도는 O(1). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/268.%20Missing%20Number.cpp 2021. 3. 3. [leetcode][645] Set Mismatch 문제 : leetcode.com/problems/set-mismatch/ 1~n 까지 모든 정수를 포함하는 배열이 있다. 오류로 인해 숫자 하나가 1~n 중 다른 숫자로 변경되었다. 즉, 변경된 배열에는 누락된 숫자와 중복(2번 발생)된 숫자가 존재한다. 변경된 배열이 주어질 때 중복된 수와 누락된 수를 구하여라. n크기의 등장횟수를 저장하는 배열을 만든다. 입력 배열을 탐색하면서 등장횟수를 갱신한다. 등장횟수가 2번인 것과 0번인 수가 정답이 된다. 시간복잡도와 공간복잡도 모두 O(N). 등장하지 않거나 두 번 등장하는 수가 한 개만 존재한다고 하였기에 비트를 쓰거나 수학적으로 접근이 가능할거 같아서 토론글을 둘러보았다. 그러다 좋은 글 있어서 해당 글 보고 정리한 방법. 따봉따봉 학창시절 배운 수학공.. 2021. 3. 3. [leetcode][575] Distribute Candies 문제 : leetcode.com/problems/distribute-candies/ n개의 사탕타입 배열이 주어진다. n/2개의 사탕만 먹을 때, 가장 다양하게 먹을 수 있는 사탕 타입의 수를 구하라. n/2와 사탕타입의 개수 중 최소값이 정답이 된다. 배열을 탐색하면서 set에 타입을 저장한다. set의 크기가 사탕 타입의 개수가 된다. 시간복잡도는 O(N). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/575.%20Distribute%20Candies.cpp 2021. 3. 2. [Leetcode][581] Shortest Unsorted Continuous Subarray 문제 : leetcode.com/problems/shortest-unsorted-continuous-subarray/ 정수형 배열이 주어질 때, 연속적인 서브배열을 오름차순 정렬하면 전체 배열이 오름차순 정렬이 되게 하는 서브배열의 최소 길이를 구하라. 가장 간단한 방법은 주어진 배열을 오름차순 정렬한뒤 정렬한 배열과 기존 배열을 비교하면서 다른 요소값을 가지는 인덱스의 최소 값과 최대 값을 구한다. 최대값 - 최소값 + 1이 정답이된다. 이 방법으로 한 경우 정렬이 필요하므로 O(NlogN)의 시간이 소요된다. 문제에서는 선형복잡도로 풀 수 있는지 물었으므로 좀 더 효율적인 방법을 살펴보자. [2,6,4,8,10,9,15] 를 예로 들어보자. 배열이 오름차순 정렬이라고 가정한다면, 왼쪽에서 오른쪽으로 .. 2021. 2. 26. [210224] 중고 자전거 구입 [210101] 해피뉴이어 글에서 다짐했던 투두리스트 중 하나 자전거 구입 연말정산의 힘으로 해냈다. '자전거 구입'가고 '국토종주' 어서오고 잘가~ 자전거를 샀으면 자전거 사진을 넣어야하지만 집이 좁아 이쁘게 디피할 공간이 없으므로 나중에 밖에서 한 컷 이쁘게 찍어야겠다. 히힣 이제 곧 3월인데 1개 해냈다. 시간순삭이네 2021. 2. 24. [leetcode][13] Roman to Integer 문제 : leetcode.com/problems/roman-to-integer/ 로마 문자를 숫자로 1:1 매칭하는 map을 하나 만든다. 문자열 s를 처음부터 탐색하면서 문자를 숫자로 바꾼 결과(let, value)를 stack에 넣는다. 만약 value가 1이 아니라면 바로전 값이 1, 10, 100인지 확인하고 그 값의 5, 10의 배수가 value와 맞는지 비교해야 한다. 이를 위해 바로 전 값을 stack의 top에서 가져온 뒤 판단한다. 만약 마이너스가 되는 경우라면 value에 top 값을 빼주면서 stack을 pop 해준다. value를 적절히 갱신 후 stack에 push 한다. 문자열 s를 모두 탐색해서 stack을 다 채웠다면 stack의 모든 숫자를 더한 값이 정답이 된다. 시간복잡.. 2021. 2. 21. 이전 1 ··· 33 34 35 36 37 38 39 ··· 110 다음
