본문 바로가기

two pointer

 (3)
[Leetcode] 42번 - 빗물 트래핑 1. 문제 파악해당 문제 유형은 단순히 구현이나 자료구조와 알고리즘을 아는 것보다 동작을 추상화해서 수식 또는 알고리즘으로 모델링하는 것이 핵심이다.문제 링크: https://leetcode.com/problems/trapping-rain-water/ (백준: https://www.acmicpc.net/problem/14719)문제 정의:각 인덱스의 요소값은 벽의 높이를 나타낸다.양쪽에 벽으로 막혀야 물이 고일수 있으므로, 현재 지정한 벽에서 양쪽 벽의 높이를 알아야한다.현재 지정한 벽을 기준으로, 왼쪽에서 가장 높은벽과 오른쪽에서 가장 높은 중에서 작은 쪽과의 차이가 물이 고일수있는 양이다.문제의 제약 파악 (입력값 크기, 상수 조건)1 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출[0,1,0,2,..
[Leetcode] 15번 - 세 수의 합 1. 문제 파악문제 링크: https://leetcode.com/problems/3sum/문제 요구사항: 주어진 배열에서 3개의 요소의 합이 0인 리스트중에서 중복되지 않는 리스트들을 반환해라.시간복잡도: 입력 크기가 3000개이므로 O(N^2)내의 풀이를 작성해야한다.2. 문제 풀이1. 브루트 포스로 문제 풀이 도출주어진 배열의 요소를 3개 골라야되므로 시간복잡도는 O(N^3)이다.for (int i = 0; i 2. 핵심 문제 풀이 도출: 어떻게 하면 시간복잡도 내로 풀수있을까?브루트포스로 풀면 O(N^3)이 나온다. 따라서 O(N^2) 이내로 풀어야한다. 세 개를 고르는데 O(N³)이니까 줄일 수 있는 방법은 없을까? 배열에서 요소를 하나 지정해놓고 배열을 한번 순회해서 처리할수있다면 O(N^2)이..
[Leetcode] 19번 - Remove Nth Node From End of List 1. 문제 파악문제 링크: https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/문제: 마지막 노드로부터 n번째 노드를 삭제하고 head를 반환해라.시간복잡도 파악: 연결리스트의 입력 크기가 30이라서 O(N) 이내어야한다. 2. 입출력 케이스 도출일반 케이스: head = [1,2,3,4,5], n = 2 -> [1,2,3,5], head = [1,2], n = 1 -> [1]엣지 케이스: head = [1], n = 1 -> [], head = [1,2], n = 2 -> [2] 3. 핵심 문제 풀이 도출연결리스트의 끝에서 n번째 노드를 삭제하는 것이다. 그래서 나는 스택 자료구조가 떠올랐다. 스택에 연결리스트 노드를..

티스토리툴바