🍀 주식가격
이 문제의 지문에서 가격이 떨어지지 않은 기간은 몇 초인지라는 조건이 있는데 솔직히 이건 사람마다 다르게 해석할 것 같다....(시간 엄청 버림...;;🥺) prices의 요소 하나인 가격이 시간이 지남에 따라 다른 가격보다 떨어지지 않는 시간의 합을 구하는 줄 알았다. 하지만, 떨어지는 시점까지의 시간이었다... 이 문제는 정말 다양한 방법으로 풀어보았는데 오랜만에 queue도 구현을 해 볼겸 javascript로 여러가지 방법으로 통과했다. 따라서 이번 블로깅은 python 위주보다는 javascript위주로 작성할 것이다. 그리고 풀고나서 신기한 것이 O(n^2)으로는 풀리지 않지만 O(n^2/2)복잡도로는 풀린다... 사실상 같은 O(n^2)이지만 그래도 시간을 최대한 줄여야 통과되는 것 같다. 그리고 Queue를 iterable하게 만들고 싶어서 for of가 가능하도록 공부해서 구현을 했는데 이는 따로 블로깅 할 생각이다. 구현부는 [Symbol.iterator](){}부분을 보면된다.
큐를 이용한 문제의 수도 코드
- while -> queue: 계속 dequeue시킨다.
- for -> queue: 위에서 dequeue되었으니 queue는 나머지고 이 queue를 돌아서 가격이 떨어지지 않는 시간을 계산한다.
로직은 매우 간단하지만 queue를 구현했기 때문에 코드는 상당히 길다.
1️⃣ Python
from collections import deque
def solution(prices):
answer = []
prices = deque(prices)
while prices:
c = prices.popleft()
count = 0
for i in prices:
if c > i:
count += 1
break
count += 1
answer.append(count)
return answerpython은 queue를 쓰고 싶으면 deque & popleft method를 이용하면 된다. 자바스크립트에 비해 정말 편리하긴 하다.
2️⃣ Javascript
javascript로는 총 3가지 방법으로 문제를 해결하였다. Queue를 이용한 풀이 & 생각난대로 푼 풀이(이중 for구문) & reverse & pop을 이용한 풀이이다.
Queue를 이용한 풀이
queue 구현부
// queue 구현
class Node {
constructor(num, next){
this.num = num;
this.next = null;
}
}
class Queue {
constructor() {
this.first = null;
this.end = null;
this.size = 0;
}
enqueue(num) {
const newNode = new Node(num);
if (!this.first) {
this.first = this.end = newNode;
} else {
this.end.next = newNode;
this.end = newNode;
}
this.size++;
}
dequeue() {
const currentNode = this.first;
if (!this.first) return null;
if (this.first === this.end) {
this.end = null;
}
this.first = this.first.next;
this.size--;
return currentNode.num;
}
}그리고 deque후에 현재 가격이 시간이 지남에 따라 언제 떨어지는지 알기 위해 queue를 돌아야하는데 iterator를 구현하지 않고 first.next가 null이 될 때까지 for 구문을 돌리면 되지만, 지나가듯이 생각난 iterator가 생각이 나 이를 이용하여 구현하기로 했다. 일단 간략히만 설명하자면 1️⃣ value와 done이라는 property를 담을 객체를 반환하는 next라는 method가 존재해야하며, 2️⃣ [Symbol.iterator](){} 메서드를 구현해야한다. 이 메서드는 next method를 포함한다.
iterator 구현부
// iterator
class Queue {
constructor() {
this.first = null;
this.end = null;
this.size = 0;
}
enqueue(num) { .../ }
dequeue() { .../ }
[Symbol.iterator]() {
let start = this.first;
return {
next() {
const iteratorResult = {
value: start && start.num,
done: !start
}
start = start && start.next;
return iteratorResult
},
};
}
}전체 구현부
class Node {
constructor(num, next){
this.num = num;
this.next = null;
}
}
class Queue {
constructor() {
this.first = null;
this.end = null;
this.size = 0;
}
enqueue(num) {
const newNode = new Node(num);
if (!this.first) {
this.first = this.end = newNode;
} else {
this.end.next = newNode;
this.end = newNode;
}
this.size++;
}
dequeue() {
const currentNode = this.first;
if (!this.first) return null;
if (this.first === this.end) {
this.end = null;
}
this.first = this.first.next;
this.size--;
return currentNode.num;
}
[Symbol.iterator]() {
let start = this.first;
return {
next() {
const iteratorResult = {
value: start && start.num,
done: !start
}
start = start && start.next;
return iteratorResult
},
};
}
}
function createQueue(arr){
return arr.reduce((acc, cur) => {
acc.enqueue(cur);
return acc;
}, new Queue())
}
function solution(prices) {
const acc_not_falling_time = [];
const queue = createQueue(prices);
while (queue.size > 0){
const num = queue.dequeue();
let not_falling_time = 0;
for (const price of queue){
not_falling_time++;
if (num > price) break;
}
acc_not_falling_time.push(not_falling_time);
}
return acc_not_falling_time;
}그리고 이걸 풀다가 시간을 엄청 허비했는데... createQueue를 이용하여 queue를 초기화해주는 것이 reduce를 이용하면 시간초과가 안 나고 for구문을 이용하면 시간초과가 난다...🤔 분명 for구문이 가장 빠르다는 것을 기억하고 있고 찾아도 보았는데 for구문이 가장 빨랐다. performance of array methods
기존 createQueue method
// 기존 코드
function createQueue(arr){
const q = new Queue();
for (let i = 0; i < arr.length; i++){
q.enqueue(arr[i])
}
return q;
}
위와 같이 시간초과가 발생한다. 혹시나해서 reduce로 바꾸어 보았는데 통과됐다...;;
간당간당하게 통과한 느낌이다....
생각난대로 푼 풀이
function solution (prices){
const n = prices.length;
const answer = [];
for (let i = 0; i < n; i++){
answer.push(0); // not_falling_time
for (let j = i + 1; j < n; j++){
if (prices[i] > prices[j]){
answer[answer.length - 1] += 1;
break;
}
answer[answer.length - 1] += 1;
}
}
return answer;
}이 또한 시간 복잡도는 O(n^2)로 통과한다.
reverse & pop을 이용한 풀이
function solution (prices){
const acc_not_falling_time = [];
const copy_prices = [...prices].reverse();
while (copy_prices.length > 0){
const num = copy_prices.pop();
let not_falling_time = 0;
for (let idx = copy_prices.length - 1; idx >= 0; idx--){
not_falling_time++;
if (num > copy_prices[idx]) break;
}
acc_not_falling_time.push(not_falling_time);
}
return acc_not_falling_time;
}queue가 아닌 배열에서 shift를 하게되면 n - 1의 연산이 발생하여 O(N)의 시간복잡도를 가지게 된다. 따라서 이를 해결할 수 있는 것은 reverse로 뒤집어 pop method를 이용하면 된다. 일종의 트릭이라 할 수 있다.
🛠️ 이상한 chat GPT??
여담이지만 그냥 기록하고 싶어서 남겨본다. 시간복잡도를 확인차 chat gpt에게 물어봤는데 O(n^3)이라고 했다...???🫣🫣🫣
아무리 생각해도 아닌 거 같아서 틀리다고 했는데 아래와 같은 답변을 얻을 수 있었다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
chat GPT를 자주 사용하지 않지만 처음에 이것저것 물어보다가 가끔 틀린 것도 알려준단 사실을 안 후로 그냥 참고용으로만 쓰고 있다. 주변에 무분별하게 chat GPT에만 의존하는 사람들을 많이 봐왔는데 지식이 있는 상태에서 이용하면 좋지만 아무런 베이스도 없는상태에서 의존만 하는 것은 좋은 습관이 아니라 생각된다... 다시 한 번 더 chat GPT에 의존하면 안 되겠다라는 생각을 심어준 계기가 되었다.
🔥 마치며
reverse와 pop을 이용하면 간단히 풀리겠구나 싶었지만 가끔 이상한 도전정신이 생겨 queue를 이용하여 어떻게든 성공하고 싶었다🤣🤣🤣 queue를 생성할 때 for구문이 통과과 안 돼서 시간을 엄청 잡아 먹었다... 사실상 이 문제를 하루종일 풀고 다양한 방법으로 집요하게 생각을 해 봤다. reduce로 통과될 줄은 몰랐고 아직도 의아하다... 많은 풀이과정을 생각하는 것은 사고력에 도움이 되지만 2개 정도로 제한하려 한다. 그래도 도전정신 덕에 custom한 객체를 iterable하게 하는 방법을 공부했다. [symbol.iterator] 메서드를 구현하는 것 외에 generator를 이용한 구현도 있지만, 하나라도 알고가자 주의라 나중에 기회되면 보려고 한다.
