2021-03-24 Circular Queue,20. Valid Parentheses

Circular Queue

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Implementation the MyCircularQueue class:

• MyCircularQueue(k) Initializes the object with the size of the queue to be k.
• int Front() Gets the front item from the queue. If the queue is empty, return -1.
• int Rear() Gets the last item from the queue. If the queue is empty, return -1.
• boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.
• boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful.
• boolean isEmpty() Checks whether the circular queue is empty or not.
• boolean isFull() Checks whether the circular queue is full or not.

Example 1:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

Explanation
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // return True
myCircularQueue.enQueue(2); // return True
myCircularQueue.enQueue(3); // return True
myCircularQueue.enQueue(4); // return False
myCircularQueue.Rear();     // return 3
myCircularQueue.isFull();   // return True
myCircularQueue.deQueue();  // return True
myCircularQueue.enQueue(4); // return True
myCircularQueue.Rear();     // return 4

Constraints:

1 <= k <= 1000
0 <= value <= 1000
At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

풀이

var MyCircularQueue = function(k) {
    this.front = 0;
    this.rear = -1;
    this.array = new Array(k);
    this.maxSize = k;
    this.currentSize = 0;
};

/** 
 * @param {number} value
 * @return {boolean}
 */
MyCircularQueue.prototype.enQueue = function(value) {
    if(this.isFull()) return false;
    
    this.rear = (++this.rear)%this.maxSize;
    this.array[this.rear] = value;
    this.currentSize++;
    return true;
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.deQueue = function() {
    if(this.isEmpty()) return false;
    
    delete this.array[this.front];
    this.front = (++this.front) % this.maxSize;
    this.currentSize--;
    return true;
};

/**
 * @return {number}
 */
MyCircularQueue.prototype.Front = function() {
    if(this.isEmpty()) return -1;
    return this.array[this.front];
};

/**
 * @return {number}
 */
MyCircularQueue.prototype.Rear = function() {
    if(this.isEmpty()) return -1;
    return this.array[this.rear];
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.isEmpty = function() {
    return this.currentSize === 0;
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.isFull = function() {
    return this.currentSize === this.maxSize;
};

느낀점 : %의 활용

20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

• 내 풀이 Runtime : 88ms, Memory : 40.3MB

var isValid = function(s) {
    // let arr = s.split('');
    let arr = [];
    let p1 = ['(','{','['];
    let p2 = [')', '}', ']'];
    for(let i = 0; i < s.length; i++){
        if(p1.includes(s[i])){
            arr.push(s[i])    
        }else if(p2.includes(s[i])){
            let last = arr.pop();
            if(s[i] === ')'){
                if(last !== '(') return false;
            }else if(s[i] === '}'){
                if(last !== '{') return false;
            }else if(s[i] === ']'){
                if(last !== '[') return false;
            }
        }
    }
    return arr.length === 0
};

• 다른 사람 걸 참고한 답 Runtime : 84ms, memory : 39MB

var isValid = function(s) {
    let arr = s.split('');
    let stack = [];
    if(arr === null || arr.length <= 0) return false;
    for(let i = 0; i < arr.length; i++){
        if(arr[i] === '('){
            stack.push(')');
        }else if(arr[i] === '{'){
            stack.push('}')
        }else if(arr[i] === '['){
            stack.push(']');
        }else if(stack.length ===0 || stack.pop() !== arr[i]){
            return false
        }
    }
    return stack.length === 0;
};

느낀점 : 스택의 활용

739. Daily Temperatures

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

풀이 : 처음에는 브루트 포스로 2중포문을 사용해 해결했었다.

var dailyTemperatures = function(T) {
    let arr = [];
    for(let i = 0; i < T.length-1; i++){
        let flag = true;
        for(let j = i+1; j < T.length; j++){
            if(T[i] < T[j]){
                arr.push(j-i);
                flag = false;
                break;
            }
        }
        if(flag) arr.push(0);
    }
    arr.push(0);
    return arr;
};

이 때, Runtime: 988 ms, Memory : 49.7 MB

스택을 사용한 훨씬 더 나은 답이 존재한다.

var dailyTemperatures = function(T) {
    let answer = new Array(T.length).fill(0);
    let stack = [];
    for(let i = 0; i < T.length; i++){
        while(stack.length && T[i] > T[stack[stack.length -1]]){
            let temp = stack.pop();
            answer[temp] = i - temp;
        }
        stack.push(i);
    }
    return answer;
};

Runtime : 144ms, Memory : 49.2MB
실행시간이 10배 가까이 효율적으로 개선되었다! 이것이 알고리즘의 힘이나 보다.
반드시 복습할 것!
참조 : [LeetCode Medium] Daily Temperatures JavaScript

프로그래머스 - 기능개발

나의 답

function solution(progresses, speeds) {
    let day = [];
    let arr1 = [];
    let arr2 = [];
    let arr2size = -1;
    for(let i = 0; i < progresses.length; i++){
        let progress = 100 - progresses[i]
        day.push(Math.ceil(progress/speeds[i]));
    }
    
    //[7,3,4,9,4]
    
    for(let i = 0; i < day.length; i++){
        if(day[arr1[arr1.length-1]] >= day[i] && arr1.length){
            arr2[arr2size] += 1;
        }
        
        if(day[i] > day[arr1[arr1.length -1]] || i === 0){
            arr1.push(i);    
            arr2size++;
            arr2[arr2.length] =1;
        }
        
    }
    return arr2;
    
}