반응형
소개
- 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
- TIL에 대해 설명을 드리자면, TIL은 'Today I Learned'약자로 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
- 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.
문제
- 프로그래머스 - 뒤에 있는 큰 수 찾기(문제 링크)
- 배열
- 스택(Stack) 활용
문제 설명
정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.
해결 과정
- 첫 번째 방법으로는 정답 배열을 주어진 numbers 크기로 초기화한 뒤 이중 for문을 사용해 answer 배열에 값을 넣어주는 완전탐색 방법입니다.
- 두 번째 방법으로는 Stack을 활용해 문제를 해결하는 방법입니다.
첫 번째 풀이 - O(n^2) 시간 초과
class Solution {
public int[] solution(int[] numbers) {
int length = numbers.length;
int[] answer = new int[length];
answer[length - 1] = -1;
for (int i = 0; i < length - 1; i++) {
int left = numbers[i];
answer[i] = -1;
for (int j = i + 1; j < length; j++) {
int right = numbers[j];
if (left < right) {
answer[i] = right;
break;
}
}
}
return answer;
}
}
- 첫 번째 제출 코드는 시간 복잡도가 O(n^2)로, 시간 초과로 실패하였습니다.
- 내부 루프를 i+1부터 시작하도록 for문을 최적화했지만, 어차피 시간 복잡도 분석 시 상수를 제외하고 계산하므로 O(n^2)보다 성능이 좋아야 통과가 가능하다는 단서가 생겼습니다
두 번째 풀이 - O(n) 정답
import java.util.Arrays;
import java.util.Stack;
class Solution {
private static Stack<Bag> stack = new Stack<>();
private static int[] answer;
public static int[] solution(int[] numbers) {
int length = numbers.length;
answer = new int[length];
Arrays.fill(answer, -1);
for (int i = 0; i < length-1; i++) {
int left = numbers[i];
int right = numbers[i + 1];
if (left < right) {
answer[i] = right;
while (!stack.isEmpty() && stack.peek().value < right) {
Bag bag = stack.pop();
answer[bag.index] = right;
}
} else {
stack.push(new Bag(i, left));
}
}
return answer;
}
private static class Bag{
private int index;
private int value;
public Bag(int index, int value) {
this.index = index;
this.value = value;
}
}
}- Bag이라는 객체에 인덱스와 값을 담고, 스택을 사용하여 문제를 풀어봤습니다.
- Arrays.fill(answer, -1); n만큼 반복하며 두번째 매개변수로 배열을 초기화 해주는 메서드 입니다. 여기서는 정답 배열에 미리 -1을 저장하는 용도로 사용하였습니다.
- 위의 정답 코드는 최악의 경우 각 요소마다 push(O(1)) 와 pop(O(1))이 한 번씩 발생하므로, 총 O(2n)번의 연산이 발생합니다. 따라서 상수를 제외한 최악의 경우 시간 복잡도는 O(n)입니다.
- 그리고 아래 루프 내의 스택을 사용한 코드를 자세히 설명드리면
for (int i = 0; i < length-1; i++) {
int left = numbers[i];
int right = numbers[i + 1];
if (left < right) {
answer[i] = right;
while (!stack.isEmpty() && stack.peek().value < right) {
Bag bag = stack.pop();
answer[bag.index] = right;
}
} else {
stack.push(new Bag(i, left));
}
}
- 먼저, 문제와 마찬가지로 numbers 배열로 [2, 3, 3, 5]가 주어졌다고 가정하겠습니다.
- 첫 번째, 루프에서 i = 0, left = 2, right = 3 if (left < right) 조건이 true가 되어 answer[0] = 3이 됩니다.
- 두 번째, 루프에서 i = 1, left = 3, right = 3 if (left < right) 조건이 false가 되어 stack.push(new Bag(1, 3));로 스택에 값을 저장합니다.
- 세 번째, 루프에서 i = 2, left = 3, right = 5 if (left < right) 조건이 true가 되어 answer[2] = 5가 됩니다. 스택에 담겨 있는 index = 1, value = 3인 Bag 객체가 있으므로 while (!stack.isEmpty() && stack.peek().value < right) 조건이 true가 되어 stack.pop();으로 꺼내서 answer[1] = 5를 설정합니다. 이러한 과정을 반복합니다.
- 네 번째, 루프는 length - 1 = 3 이기 때문에 더 이상 반복하지 않습니다.
- 정답 배열 결과 = [3, 5, 5, -1]
마무리하며
- 무언가를 꺼내 비교하는 알고리즘 문제를 해결할 때 Stack 자료구조를 생각해보는 것은 괜찮은 접근 방식 중 하나인것 같습니다.
- 1일 1알고리즘 문제를 푼 지 꽤 되었지만, 풀이 과정을 블로그에 작성해 본 적은 없었는데, 알고리즘 풀이 과정 TIL(Today I Learned)을 작성해 보는 것도 좋은 경험인 것 같습니다.
