본문 바로가기

Stack

 (3)
[Leetcode] 739번 - 일일 온도 1. 문제 파악문제 링크: https://leetcode.com/problems/daily-temperatures/description/문제 정의: 배열을 순회하면서 현재 지정된 배열 요소보다 큰값이 몇 번째 뒤에 위치하는지 저장하는 배열 반환문제의 제약 파악 (입력값 크기, 상수 조건)1 30 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출주어진 배열과 동일한 크기의 반환 배열을 초기화한다.배열을 순회하면서 순차적으로 요소 하나를 지정지정된 요소의 이후 배열 요소를 순회하면서, 지정된 요소보다 큰 요소 중에 가장 가까운 요소를 찾는다.지정된 요소의와 지정된 요소보다 큰 요소 중에 가장 가까운 요소의 인덱스 차이를 구한다.인덱스 차이를 반활 배열에 저장한다.for (int i = 0; i 두개의 요소..
[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번째 노드를 삭제하는 것이다. 그래서 나는 스택 자료구조가 떠올랐다. 스택에 연결리스트 노드를..
[Leetcode] 143번 - Reorder List 1. 문제 파악문제 링크: https://leetcode.com/problems/reorder-list/문제: L0 → L1 → … → Ln - 1 → Ln 수열인 연결 리스트를 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …로 재정렬해라.시간복잡도 파악: 입력크기가 50000이라서 O(nlogn) 이내어야한다. 2. 입출력 케이스 도출짝수: [1 2 3 4]홀수: [1], [1 2 3 4 5 6 7] 3. 핵심 문제 풀이 도출 양쪽 끝 투 포인터(left, right) 사용해서 연결 리스트를 재정렬할수있다. 여기서 left와 right는 기존 리스트의 노드 순서를 가리킨다.EX1) [1, 2, 3, 4][1, 2, 3, 4]: left = L1, right = L4Logic: ..

티스토리툴바