Star43 [leetcode][795] Number of Subarrays with Bounded Maximum 문제 : https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/ 양수 배열 nums, 두 개의 양수 left, right 가 입력으로 주어진다. nums 배열의 하위배열(연속적인 부분배열. 비어있지 않음)의 최대 원소가 left 이상, right 이하인 하위배열들의 수를 구해라. 재미있는 투포인터문제~ nums를 처음부터 탐색하면서 정답이 될 수 있는 범위를 l, r 변수에 저장한다. (l = 왼쪽, r = 오른쪽 인덱스) l 변수는 nums[i]가 부분배열에 포함될 때 정답이 절대 불가능할 때 갱신한다. 최대값만 left, right를 비교하기 때문에 정답이 절대 불가능한 경우는 nums[i]가 right보다 큰 경우이다. r 변.. 2021. 6. 19. [Leetcode][923] 3Sum With Multiplicity 문제 : leetcode.com/problems/3sum-with-multiplicity/ 0이상 100이하의 정수를 가지는 배열 arr이 주어진다. 서로다른 원소 3개를 더한 값이 target이 되는 조합의 개수를 구하라. 배낭문제로 구할 수 있다. dp[target][cnt] = cnt 개의 원소들을 합해서 target 을 만들 수 있는 경우의 수. i 번째 원소(num)를 기준으로 dp 배열을 갱신해나간다. num + x = target 이라 가정하면 num에 x를 더하면 target을 만들 수 있으므로, x의 경우의 수로 target 인덱스를 갱신할 수 있다. 위의 식에서 num을 우항으로 옮기면 x = target - num이 되므로 dp[target][cnt+1] += dp[target-num.. 2021. 3. 23. [programmers][2021카카오공채] 순위 검색 문제 : https://programmers.co.kr/learn/courses/30/lessons/72412 query가 100,000 infos가 50,000. query 문자열에 맞게 infos에 맞는 조건을 찾아서 정답을 구하기엔 시간이 부족하다. 개발언어가 3개. 직군 2개. 경력 2개. 소울푸드 2개. 3x2x2x2 = 24개의 조합에 맞는 score들을 저장해두면 시간을 확 줄일 수있다. scores[개발언어][직군][경력][소울푸드] = 점수들 배열. 만약 query에 개발언어가 상관없다면 scores[0~3][직군][경력][소울푸드]의 scores 조건에 맞는 점수들의 수를 정답에 포함시킨다. query에 개발언어가 java라면 scores[java 인덱스][직군][경력][소울푸드]의 s.. 2021. 3. 6. [leetcode][645] Set Mismatch 문제 : leetcode.com/problems/set-mismatch/ 1~n 까지 모든 정수를 포함하는 배열이 있다. 오류로 인해 숫자 하나가 1~n 중 다른 숫자로 변경되었다. 즉, 변경된 배열에는 누락된 숫자와 중복(2번 발생)된 숫자가 존재한다. 변경된 배열이 주어질 때 중복된 수와 누락된 수를 구하여라. n크기의 등장횟수를 저장하는 배열을 만든다. 입력 배열을 탐색하면서 등장횟수를 갱신한다. 등장횟수가 2번인 것과 0번인 수가 정답이 된다. 시간복잡도와 공간복잡도 모두 O(N). 등장하지 않거나 두 번 등장하는 수가 한 개만 존재한다고 하였기에 비트를 쓰거나 수학적으로 접근이 가능할거 같아서 토론글을 둘러보았다. 그러다 좋은 글 있어서 해당 글 보고 정리한 방법. 따봉따봉 학창시절 배운 수학공.. 2021. 3. 3. [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. [leetcode][84] Largest Rectangle in Histogram 문제 : leetcode.com/problems/largest-rectangle-in-histogram/ 히스토그램 바의 높이가 저장된 배열이 주어진다. 히스토그램들로 만들수있는 직사각형의 최대 크기를 구하라. 예시로 주어진 배열로 아이디어를 구체화해보자. 인덱스별 막대바의 높이를 직사각형의 세로길이라 할 때, 구할 수 있는 직사각형의 최대값들을 구한 뒤 이들 중 최대값이 정답이 된다. 직사각형의 세로길이를 배열 값이라 가정해놨기 때문에 하나를 예로 들어서 특정 바의 세로길이로 고정해놨을 때, 최대 직사각형을 구할 수 있는 가로길이를 어떻게 구할수있는지 찾아야한다. 인덱스가 5인 경우를 예로 들어보면 인덱스 5를 포함해서 만들 수 있는 최대 직사각형은 파란색 점선과 같다. 이 때, 인덱스 2를 기준으로 .. 2021. 1. 24. 이전 1 2 3 4 5 6 7 8 다음
