two-pointer16 [Leetcode] 881. Boats to Save People 문제 : https://leetcode.com/problems/boats-to-save-people/description/ people이라는 배열이 주어지는데, people[i]는 i번째 사람의 몸무게를 나타냅니다. 그리고 무게 제한이 limit인 무수히 많은 보트가 있습니다. 각 보트는 최대 limit 무게까지 운반할 수 있으며, 최대 두 사람이 탈 수 있으며 두 사람의 무게 합이 limit 이하여야 합니다. 주어진 모든 사람을 운반하기 위해 필요한 최소 보트 수를 구하세요. 한 번에 두 명이 탈 수 있습니다. 투포인터로 해결할 수 있습니다. 먼저 people 배열을 오름차순 정렬합니다. 왼쪽부터 탐색하는 left 인덱스, 오른쪽부터 탐색하는 right 인덱스를 준비합니다. 만약 한 보트에 가장 무거운.. 2023. 4. 7. [Leetcode] 1658. Minimum Operations to Reduce X to Zero 문제 : https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/ 정수 배열 nums와 정수 x가 입력으로 주어진다. 한 번의 작업으로 배열 nums에서 가장 좌측 혹은 가장 우측에 있는 요소를 제거 하고 x에서 제거한 요소의 값을 뺄 수 있다. 최소 몇 번의 작업으로 x를 정확히 0으로 만들 수 있는지 구하라. 만일 불가능하다면 -1을 반환하라. 부분합과 투포인터로 구할 수 있다. 부분합을 만들어 subsum 배열에 세팅한다. 첫 번째 예제 [1, 1, 4, 2, 3], x=5 로 표를 세팅해보면 [그림1]과 같다. 정답이 되는 제거되는 요소는 가장 뒤 요소 2, 3이다. 이를 반대로 생각하면 제거되지 않는 요소들의 합은 nums 전체.. 2022. 6. 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. 이전 1 2 3 다음
