본문 바로가기

two-pointer16

[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.
[Programmers][2020 카카오 인턴십] 보석 쇼핑 문제 : https://programmers.co.kr/learn/courses/30/lessons/67258 투포인터로 풀었다. gems를 돌면서 보석 종류 수를 구한다. 보석의 개수를 저장하는 cnts map을 하나 만든다. key = 보석이름, value = 보석 수. 그리고 탐색하면서 만난 보석들의 종류를 저장하는 set을 하나만든다. (let, exists) 투포인터의 오른쪽 인덱스(right)를 0부터 1씩 증가시키며 left 인덱스를 갱신한다. 탐색중인 보석의 수를 cnts 맵에 1더해서 갱신시킨다. exists set에 탐색한 보석을 추가한다. 정답가능한 배열의 크기를 최소화로 만들기 위해 left인덱스를 갱신한다. 만일 gems[left] 에 해당하는 보석의 개수(cnts 참고)가 1보다.. 2021. 6. 13.
[leetcode][870] Advantage Shuffle 문제 : leetcode.com/problems/advantage-shuffle/ 길이가 같은 정수 배열 A, B이 주어질 때, A의 원소의 순서를 변경하여 A[i] > B[i]인 원소의 개수가 최대가 되는 수열 A를 구하여라. 기본 아이디어는 A[i] > B[i] (조건)를 만들 수 있는 A[i] 값은 A 원소가 클수록 조건을 만족할 가능성이 높으며 A 원소가 작을수록 조건을 만족할 가능성이 낮다. 즉, 큰 원소값이 조건을 만족할 수 없으면 이는 작은 원소값도 만족할 수 없다. 따라서 큰 원소값을 세팅할 수 있는 곳에 먼저 세팅하고, 큰 원소값을 사용할 수 없는 곳은 버리는 수로 작은 원소값으로 대체한다. A 배열을 오름차순 정렬하고, B 배열을 {원소값, 인덱스} 배열로 변경하여 이를 오름차순 정렬한.. 2021. 3. 26.
[leetcode][122] Best Time to Buy and Sell Stock II 문제 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ 주식 가격 배열이 주어진다. 어떤 주식을 샀을 때 해당 주식을 팔기 전까지는 주식을 구입할 수 없다고 하자. 주식을 사고 판다고 했을 때 얻을 수 있는 최대 이익은 얼마인가? 투 포인터로 해결했다. 처음에는 DP로 했었는데 이건 그렇게하면 TLE 난다. 다시 생각해보니 주식을 사고 나서 최대가를 찍었을 때 파는 거다. 주식가격이 상승 곡선이 시작하기 전 가장 최소값을 찍었을 때, 주식을 구입한다. 상승 곡선이 끝날 때, 주식의 가격이 최대가 됐을 때 주식을 판다. 주식을 판 다음 날부터 다시 위 과정을 반복한다. 이를 배열 끝날때까지 반복한다. 상승 곡선이 끝나기 전에 배열이 종.. 2020. 4. 6.
[leetcode][567] Permutation in String 문제: https://leetcode.com/problems/permutation-in-string/ 문자열 s1, s2가 주어졌을 때, s2 서브 문자열에서 s1 문자열 문자들이 전부 존재하는지 구하는 문제. 예를 들어, s1="ab", s2="eidbaooo" 라면 true. s1="ab", s2="eidboaoo" 라면 false. 투포인터로 풀었다. 문자열 s1을 전부 탐색하면서 문자개수를 저장한다. (let, arr) s2 서브 문자열 범위의 시작 위치와 종료 위치를 변수 s, e에 저장한다. s2 문자열을 탐색하면서 탐색 중인 문자 위치를 e라 하자. (let, nowChar = s2[e]) 만약 arr[nowChar] 이 0 보다 크다면 arr[nowChar]를 1 감소시키고 다음 문자를 탐.. 2020. 3. 10.
[leetcode] 904. Fruit into Baskets 문제 : https://leetcode.com/problems/fruit-into-baskets/description/ 슬라이딩 윈도우 문제. 인덱스를 가리키는 변수 l(왼쪽), r(오른쪽)을 둔다. tree[l]을 포함하여 수집할 수 있는 최대 범위를 r로 구한다. tree[l ~ r]이 과일종류가 3개 이상이 되기전까지 r을 증가시킨다. r을 구했으면 tree[l]을 포함할 때 수집할 수 있는 최대 과일 수를 구할 수 있다. (l~r 범위) ex) l = 0. r = 4 -> r - l + 1 = 5(0번째 인덱스를 포함하여 수집할 수 있는 최대 과일 수) 다음 탐색 시 tree 배열을 다시 탐색하지 않으려면 구한 범위에서 tree[l]이 아닌 과일의 종류가 무엇인지 알아야하고 이 과일이 가장 나중에.. 2019. 9. 3.