투포인터11 [Leetcode]11. Container With Most Water 문제 : https://leetcode.com/problems/container-with-most-water/ 수직선 높이를 나타내는 배열이 주어진다. 두 개의 수직선을 선택해서 그 사이에 물을 넣는다고 할 때 가능한 최대 용량은 얼마인가. 투포인터로 푼다. 왼쪽부터 시작하는 left 포인터, 오른쪽부터 시작하는 right 포인터가 있다. left, right 수직선을 선택했을 때의 용량을 구하고 이들 중 최대 값이 정답이 된다. 용량을 구한뒤 left가 right보다 낮다면 left를 +1 하고, right가 left보다 낮다면 right를 -1 해준다. 시간복잡도는 O(N). N = 배열의 크기 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/lee.. 2021. 11. 3. 투포인터 (Two pointer) 투포인터란 이름 그대로 두 개의 포인터를 사용하여 문제를 풀어나갑니다. 2개의 포인터로 배열이나 문자열을 탐색할 때 탐색 위치를 저장하고 있습니다. 말로 하는거보다는 예를 들어서 한 번 살펴봅시다. 수들의 합. N개의 자연수 배열이 주어질 때, i~j 번째 수들의 합이 M이 되는 경우의 수를 구하는 문제입니다. 1 1 1 1 배열은 위와 같고, M = 2 라고 했을 때 투포인터로 정답을 구해봅시다. 두 개의 포인터를 두고 이들을 left, right라 합시다. left는 i, right는 j 번째 수의 위치를 가리킵니다. left는 범위를 줄이고자 할 때 증가시키고, right는 범위를 증가시키고자 할 때 증가시킵니다. 시작 인덱스는 둘 다 0입니다. left right 부분 배열합 0 0 1 0 1 2.. 2021. 9. 12. [leetcode] 76. Minimum Window Substring 문제 : https://leetcode.com/problems/minimum-window-substring/ 길이가 m, n인 문자열 s, t가 입력으로 주어진다. t의 모든 문자가 포함되는 s의 부분 문자열들 중 최소 길이를 가지는 연속 부분 문자열을 구해라. 정답이 없다면 빈 문자열 반환. 투포인터로 풀었다. t문자열의 모든 문자들의 갯수를 저장하는 cnt 배열을 만들어 세팅한다. right 인덱스를 증가시키며 cnt 배열의 등장갯수를 모두 충족시킨다면 해당 right 인덱스를 부분문자열 끝으로 할 때, 해당 부분문자열을 최소 길이로 만들기 위해 left인덱스를 조정한다. left 인덱스는 0부터 증가시키며 현재 탐색중인 문자가 부분문자열에서 제외된다면 cnt 배열의 문자 갯수를 충족시킬 수 없을때까.. 2021. 8. 16. [Leetcode][611] Valid Triangle Number 문제 : https://leetcode.com/problems/valid-triangle-number/ 0이상의 정수배열 nums가 주어질 때, 이 들 중 3개 수를 골라서 삼각형을 만들 수 있는 경우의 수를 구해라. 투포인터로 풀었다. nums 배열을 오름차순 정렬한다. nums를 처음부터 탐색하면서 탐색하는 정수는 고정적으로 사용하는 변의 길이다. (let, a) 탐색한 정수의 바로 다음 정수들을 탐색하는데 이를 다음으로 선택하는 변의 길이이다. (let, b) 삼각형을 만들기위한 2개의 변을 고정했다. 삼각형이 되기 위한 조건은 두 개의 변의 길이 합이 나머지 하나(최장길이 변)의 길이보다 커야한다. 나머지 변을 c라고 하자. 만일 이전 탐색으로 구한 길이들의 관계가 a + b > c 였다면, b는.. 2021. 7. 15. [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. 이전 1 2 다음
