[프로그래머스] JavaScript Lv2 - 주식가격(42584)

개요

문제 이름: 주식가격 (42584)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42584
플랫폼: 프로그래머스
알고리즘 분류: 스택/큐
소요 시간: 1시간 10분

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 주식 가격의 변동을 배열로 받아, 각 시점마다 가격이 떨어지지 않은 기간이 몇 초인지를 구하는 문제입니다. 문제를 해결하기 위해서는 배열을 순회하면서 각 시점마다 이후의 가격들을 비교하여 가격이 떨어지는 시점을 찾아야 합니다.

 

문제 해결을 위해 다음과 같은 접근 방식을 사용할 수 있습니다...!

1. 이중 반복문을 사용하여 각 시점마다 이후의 가격들을 비교하는 방법 (브루트 포스)
2. 스택을 사용하여 가격이 떨어지는 시점을 효율적으로 찾는 방법

브루트 포스 방식은 간단하지만 시간 복잡도가 O(n^2)이기 때문에 효율적이지 않습니다. 반면 스택을 사용하면 O(n)의 시간 복잡도로 문제를 해결할 수 있습니다.

 

스택을 사용한 풀이 방식은 다음과 같습니다.

1. 스택에는 가격이 떨어지지 않은 시점의 인덱스를 저장합니다.
2. 배열을 순회하면서 현재 가격과 스택의 top에 있는 인덱스의 가격을 비교합니다.
   1. 현재 가격이 top의 가격보다 작다면, 가격이 떨어진 것입니다.
   2. 스택에서 pop하고 현재 인덱스와의 차이를 계산하여 정답 배열에 저장합니다.
   3. 현재 가격이 top의 가격보다 크거나 같다면, 스택에 현재 인덱스를 push합니다.
3. 배열 순회가 끝난 후에도 스택에 남아있는 인덱스들은 가격이 떨어지지 않은 시점들입니다.
4. 배열의 마지막 인덱스와의 차이를 계산하여 정답 배열에 저장합니다.

이 풀이 방식을 사용하면 가격이 떨어지는 시점을 효율적으로 찾을 수 있습니다.

 

시도

1차 시도  (실패)

function solution(prices) {
	const answer = new Array(prices.length).fill(0);

	for (let i = 0; i < prices.length; i++) {
		for (let j = i + 1; j < prices.length; j++) {
			answer[i]++;
			if (prices[i] > prices[j]) {
				break;
			}
		}
	}

	return answer;
}

이 코드는 이중 반복문을 사용하여 각 시점마다 이후의 가격들을 비교하는 브루트 포스 방식입니다.

 

외부 반복문에서는 현재 시점 i를 순회하고, 내부 반복문에서는 i 이후의 시점 j를 순회하면서 가격이 떨어지는 시점을 찾습니다. 가격이 떨어지지 않으면 answer[i]를 증가시키고, 가격이 떨어지면 내부 반복문을 종료합니다.

 

이 방식의 시간 복잡도는 O(n^2)이므로 효율적이지 않아 시간 초과가 발생합니다.

 

2차 시도  (성공)

function solution(prices) {
	const answer = [];

	for (let i = 0; i < prices.length; i++) {
		let count = 0;
		for (let j = i + 1; j < prices.length; j++) {
			count++;
			if (prices[i] > prices[j]) {
				break;
			}
		}
		answer.push(count);
	}

	return answer;
}

이 코드는 1차 시도와 유사하지만, answer 배열을 미리 초기화하지 않고 매 시점마다 count 변수를 사용하여 가격이 떨어지지 않은 기간을 계산합니다. 가격이 떨어지지 않은 기간을 answer 배열에 push하여 저장합니다.

이 방식도 여전히 O(n^2)의 시간 복잡도를 가지지만, 테스트 케이스를 통과할 수 있습니다. 하지만 효율성 측면에서는 개선의 여지가 있습니다.

 

3차 시도 (성공)

function solution(prices) {
	const answer = new Array(prices.length).fill(0);
	// 결과를 저장할 배열 초기화
	const stack = [];
	// 스택 초기화

	// prices 배열을 순회하면서
	for (let i = 0; i < prices.length; i++) {
		// 스택이 비어있지 않고, 현재 가격이 스택의 top에 있는 인덱스의 가격보다 작으면 (가격이 떨어지면)
		while (stack.length && prices[i] < prices[stack[stack.length - 1]]) {
			const j = stack.pop();
			// 스택에서 인덱스를 꺼냄

			answer[j] = i - j;
			// 현재 인덱스와 스택에서 꺼낸 인덱스의 차이를 결과 배열에 저장
		}
		stack.push(i);
		// 현재 인덱스를 스택에 push
	}

	// 배열 순회가 끝난 후에도 스택에 남아있는 인덱스들 처리
	while (stack.length) {
		const j = stack.pop();
		// 스택에서 인덱스를 꺼냄
		answer[j] = prices.length - 1 - j;
		// 배열의 마지막 인덱스와 스택에서 꺼낸 인덱스의 차이를 결과 배열에 저장
	}

	return answer;
	// 결과 배열 반환
}

이 코드는 스택을 사용하여 문제를 해결합니다. 스택에는 가격이 떨어지지 않은 시점의 인덱스를 저장합니다.

배열을 순회하면서 현재 가격 prices[i]와 스택의 top에 있는 인덱스의 가격 prices[stack[stack.length - 1]]을 비교합니다. 현재 가격이 top의 가격보다 작다면 가격이 떨어진 것이므로, 스택에서 pop하고 현재 인덱스와의 차이를 계산하여 answer 배열에 저장합니다. 이 과정을 스택이 비거나 현재 가격이 top의 가격보다 크거나 같을 때까지 반복합니다.

배열 순회가 끝난 후에도 스택에 남아있는 인덱스들은 가격이 떨어지지 않은 시점들이므로, 배열의 마지막 인덱스와의 차이를 계산하여 answer 배열에 저장합니다.

 

이 방식의 시간 복잡도는 사실상 O(n)이며, 스택을 사용하여 가격이 떨어지는 시점을 효율적으로 찾을 수 있습니다. 모든 시도 중에서 가장 효율적입니다.

4차 시도 (성공)

function solution(prices) {
	// prices 배열의 각 요소에 대해 콜백 함수를 실행하고 결과를 모아 새로운 배열 answer를 생성해야 함
	const answer = prices.map((_, i) => {
		let count = 0;
		// 가격이 떨어지지 않은 기간을 저장할 변수

		// 현재 시점 i 이후의 가격들을 비교하기 위한 반복문
		for (let j = i + 1; j < prices.length; j++) {
			count++;
			// 가격이 떨어지지 않은 기간을 증가시킴

			// 현재 시점의 가격이 이후 시점의 가격보다 크면 (가격이 떨어지면)
			if (prices[i] > prices[j]) {
				break;
				// 반복문 종료
			}
		}
		return count;
		// 가격이 떨어지지 않은 기간을 반환
	});

	return answer;
	// 결과 배열 반환
}

이 코드는 map 메서드를 사용하여 각 시점마다 가격이 떨어지지 않은 기간을 계산합니다. map 메서드는 배열의 각 요소에 대해 주어진 콜백 함수를 실행하고, 그 결과를 모아 새로운 배열을 반환합니다.

콜백 함수 내부에서는 이중 반복문을 사용하여 현재 시점 이후의 가격들을 비교하고, 가격이 떨어지지 않은 기간을 count 변수에 저장합니다. 가격이 떨어지면 내부 반복문을 종료하고, count 값을 반환합니다.

사실 2차 시도와 map을 빼면 다른 게 없으며, 이 방식의 시간 복잡도는 O(n^2)입니다.

 

사족

3차 시도의 시간복잡도가 살짝 오락가락하는데 아마 저게 맞지 않나 싶습니다!