deeprun

소수찾기

 문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 제한 사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 입출력 예

 Python 코드

from itertools import permutations
 
def solution(numbers):
    
    # 소수 판별할 리스트 만들기
    num_list = [] # 전체 순열 넣어줄 리스트
    for i in range(1,len(numbers)+1) :
        test_list = permutations(numbers,i)       
        for j in test_list :
            num_list.append(int("".join(j)))
        
    num_list = set(num_list) # 중복과 0, 1 제외
    if 0 in num_list :
        num_list.remove(0)        
    if 1 in num_list :
        num_list.remove(1)
        
    # 소수 판별 
    answer = len(num_list) # 모든 수가 소수라 가정하고 시작
    for i in num_list :
        if i != 2 :
            for j in range(2,int(i**0.5)+1) :
                if i % j== 0 :
                    answer -=1
                    break
        
    return answer

* 참고 링크 : https://mentha2.tistory.com/8

 C++ 코드

#include<string>
#include<vector>
#include<cmath>
 
using namespace std;
 
bool Visit[10000000];
bool Select[10];
int Answer;
 
bool IsPrime(int N)
{
    if (N == 0 || N == 1) return false;
 
    for (int i = 2; i <= sqrt(N); i++)
    {
        if (N % i == 0) return false;
    }
    return true;
}
 
void DFS(int Cnt, string S, string Res)
{
    if(Res != "" && Visit[stoi(Res)] == false)
    {
        int Num = stoi(Res);
        Visit[Num] = true;
        if (IsPrime(Num) == true) Answer++;
    }
 
    for (int i = 0; i < S.length(); i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        DFS(Cnt + 1, S, Res + S[i]);
        Select[i] = false;
    }
}
 
int solution(string S)
{
    DFS(0, S, "");
    return Answer;
}

* 참고 링크 : https://yabmoons.tistory.com/336

 출처

https://programmers.co.kr/learn/courses/30/lessons/42839

모의고사

 문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 제한 사항

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

 입출력 예

 Python 코드

def solution(answers):
    
    answer = []
    # 패턴정의
    first = [ 1,2,3,4,5 ]
    second = [ 2,1,2,3,2,4,2,5 ]
    third = [ 3,3,1,1,2,2,4,4,5,5 ]
    
    # 점수정의
    first_count = 0
    second_count = 0
    third_count = 0
    
    # 정답확인
    for number in range(len(answers)):
        if answers[ number ] == first[ number % 5 ]:
            first_count += 1
        if answers[ number ] == second[ number % 8 ]:
            second_count += 1
        if answers[ number ] == third[ number %10 ]:
            third_count += 1
    pre_answer = [ first_count,second_count,third_count ]   
    
    # 가장 많이 맞힌 사람
    for person, score in enumerate(pre_answer):
        if score == max(pre_answer):
            answer.append(person + 1)
    return answer

* 참고 링크 : https://sinsomi.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%AA%A8%EC%9D%98%EA%B3%A0%EC%82%AC

 C++ 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int test1[5] = {1, 2, 3, 4, 5};
int test2[8] = {2, 1, 2, 3, 2, 4, 2, 5};
int test3[10] = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    int score[3] = {0, };
    int max_score = 0;
    for (int i = 0; i < answers.size(); i++){
        if (answers[i] == test1[i % 5]) score[0] += 1;
        if (answers[i] == test2[i % 8]) score[1] += 1;
        if (answers[i] == test3[i % 10]) score[2] += 1;
    }
    max_score = max(max(score[0], score[1]), score[2]);
    for (int i = 0; i < 3; i++){
        if (score[i] == max_score)
            answer.push_back(i + 1);
    }
    return answer;
}

* 참고 링크 : https://rile1036.tistory.com/28

 출처

https://programmers.co.kr/learn/courses/30/lessons/42840

Design 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.

You must solve the problem without using the built-in queue data structure in your programming language. 

 제한 사항

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

 입출력 예

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

 Python 코드

Python code 

class MyCirculurQueue:
    def __init__(self, k):
        self.q = [None] * k
        self.maxlen = k
        self.p1 = 0
        self.p2 = 0

    # enQueue(): rear 포인터 이동
    def enQueue(self, value):
        if self.q[self.p2] is None:
            self.q[self.p2] = value
            self.p2 = (self.p2 + 1) % self.maxlen
            return True
        else:
            return False

    # deQueue(): front 포인터 이동
    def deQueue(self):
        if self.q[self.p1] is None:
            return False
        else:
            self.q[self.p1] = None
            self.p1 = (self.p1 + 1) % self.maxlen
            return True

    def Front(self):
        return -1 if self.q[self.p1] is None else self.q[self.p1]

    def Rear(self):
        return -1 if self.q[self.p2 - 1] is None else self.q[self.p2 - 1]

    def isEmpty(self):
        return self.p1 == self.p2 and self.q[self.p1] is None

    def isFull(self):
        return self.p1 == self.p2 and self.q[self.p1] is not None

* 참고 링크 : https://deep-learning-study.tistory.com/480

 C++ 코드

C ++ code

class MyCircularQueue {
public:
  MyCircularQueue(int k): q_(k) {}
  
  bool enQueue(int value) {
    if (isFull()) return false;
    q_[(head_ + size_) % q_.size()] = value;    
    ++size_;
    return true;
  }
  
  bool deQueue() {
    if (isEmpty()) return false;
    head_ = (head_ + 1) % q_.size();
    --size_;
    return true;
  }
 
  int Front() { return isEmpty() ? -1 : q_[head_]; }
 
  int Rear() { return isEmpty() ? -1 : q_[(head_ + size_ - 1) % q_.size()]; }
 
  bool isEmpty() { return size_ == 0; }
 
  bool isFull() { return size_ == q_.size(); }
private:
  vector<int> q_;
  int head_ = 0;
  int size_ = 0;
};

* 참고 링크 : https://zxi.mytechroad.com/blog/desgin/leetcode-622-design-circular-queue/

 출처

https://leetcode.com/problems/design-circular-queue/

Implement Queue using Stacks

 문제 설명

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

• You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

 제한 사항

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, peek, and empty.
• All the calls to pop and peek are valid.

 입출력 예

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

 Python 코드

Python code 

class MyQueue: 
	def __init__(self): 
		// 문제에서 2개의 스택을 사용하라고 하니, 배열을 2개를 사용
		self.stack1 = [] 
		self.stack2 = [] 
		
	def push(self, x: int): 
		// stack1에는 push 데이터를 넣어줌
		self.stack1.append(x) 
		
	def pop(self): 
	// pop을 할때에는 stack1의 배열을 거꾸로 변경하는 과정이 필요
	// pop을 할때, stack1.pop()을 하여, stack2에 넣어줌
	// stack1 [1, 2, 3] -> stack2 = [3, 2, 1] 
		self.peek() 
		return self.stack2.pop() 
		
	def peek(self): 
		// peek는 큐의 첫번째 값을 가져와야 하므로 
		// stack1의 모든 값을 거꾸로 stack2에 넣어서, stack2[-1]을 리턴
		
		if not self.stack2: 
		// stack1의 모든 값이 나올때까지 해주는데, 
		// stack2가 비어있지 않은 경우에 stack2에 값을 넣을 경우 
		// pop()이 힘들어지니 stack1을 그대로 이용
		
		// 1) stack1 [1, 2, 3] -> stack2 [3, 2, 1] 
		// 2) MyQueue.push(4) 
		// 3) stack1 -> [4] , stack2 [3, 2, 1] 의 경우 
		// stack1의 값을 넣어주면 stack2는, [3, 2, 1, 4]가 되므로 pop을 하기가 힘듬 
		// 4) stack1의 [4]는 어차피 stack2가 다 빌때까지 필요없으므로 
		// 그냥 stack2가 빌때까지 stack1에 넣어둠 
		
			while self.stack1: 
				self.stack2.append(self.stack1.pop()) 
		return self.stack2[-1] 
		
		
	def empty(self): 
		return (len(self.stack1) == 0) and (len(self.stack2) == 0)

* 참고 링크 : https://jasmine46.tistory.com/71

 C++ 코드

C ++ code

// Time:  O(1), amortized
// Space: O(n)

class Queue {
public:
    // Push element x to the back of queue.
    void push(int x) {
        A_.emplace(x);
    }

    // Removes the element from in front of queue.
    void pop(void) {
        peek();
        B_.pop();
    }

    // Get the front element.
    int peek(void) {
        if (B_.empty()) {
          // Transfers the elements in A_ to B_.
          while (!A_.empty()) {
            B_.emplace(A_.top());
            A_.pop();
          }
        }
        if (B_.empty()) {  // B_ is still empty!
          throw length_error("empty queue");
        }
        return B_.top();
    }

    // Return whether the queue is empty.
    bool empty(void) {
        return A_.empty() && B_.empty();
    }

 private:
  stack<int> A_, B_;
};

* 참고 링크 : https://shareablecode.com/snippets/implement-queue-using-stacks-c-solution-leetcode-FaBa-R43B

 출처

https://leetcode.com/problems/implement-queue-using-stacks/

Implement Stack using Queues

 문제 설명

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

 제한 사항

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, top, and empty.
• All the calls to pop and top are valid.

 입출력 예

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

더보기

 Python 코드

Python code 

class MyStack:

    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)

    def pop(self) -> int:
        for i in range(len(self.q) - 1):
            self.push(self.q.popleft())
        return self.q.popleft()

    def top(self) -> int:
        return self.q[-1]

    def empty(self) -> bool:
        return len(self.q) == 0

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

* 참고 링크 : https://www.youtube.com/watch?v=rW4vm0-DLYc 

 C++ 코드

C ++ code

class MyStack {
    queue<int>q;
public:
    /** Initialize your data structure here. */
    MyStack() {
        
    }
    
    /** Push element x onto stack. */
    void push(int x) 
    {
        q.push(x);
        for (int i=0; i<q.size()-1; i++)
        {
            q.push(q.front());
            q.pop();
        }        
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() 
    {
        int result=q.front();
        q.pop();
        return result;
    }
    
    /** Get the top element. */
    int top() 
    {
        return q.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() 
    {
        return q.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * bool param_4 = obj.empty();
 */

* 참고 링크 : https://github.com/wisdompeak/LeetCode/blob/master/Stack/225.Implement-Stack-using-Queues/225.Implement%20Stack%20using%20Queues.cpp

 출처

https://leetcode.com/problems/implement-stack-using-queues/submissions/

Evaluate Reverse Polish Notation

 문제 설명

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

* 역폴란드 표기법 : https://ko.wikipedia.org/wiki/역폴란드_표기법

 제한 사항

• 1 <= tokens.length <= 104
• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

 입출력 예

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

더보기

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

더보기

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

 Python 코드

Python code 

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for t in tokens:
            if t not in {"+", "-", "*", "/"}:
                stack.append(int(t))
            else:
                b, a = stack.pop(), stack.pop()
                if t == "+": stack.append(a + b)
                elif t == "-": stack.append(a - b)
                elif t == "*": stack.append(a * b)
                else: stack.append(trunc(a / b))
        return stack[0]

* 참고 링크 : https://dev.to/seanpgallivan/solution-evaluate-reverse-polish-notation-192l

* 설명 참고 링크 : https://www.youtube.com/watch?v=P8xYysvjLd0 

 C++ 코드

C ++ code

int evalRPN(vector<string>& tokens)
{
    stack<int>st;
    for(auto it : tokens)
    {
        if(it=="+" || it=="-" || it=="*" || it=="/"  )
        {
            int f = st.top();st.pop();
            int s = st.top();st.pop();

            if (it == "+")
              { int r = s + f;  st.push(r); }
            else if (it == "*")
              { int r = s * f;  st.push(r); }
            else if (it == "-")
              { int r = s - f;   st.push(r); }
            else if (it == "/")
              { int r = s / f;   st.push(r); }
        }
        else{ st.push( stoi(it)); }
    }
    return st.top();
}

* 참고 링크 : https://leetcode.com/problems/evaluate-reverse-polish-notation/discuss/1234191/c-easy-optimized-solution-150-evaluate-reverse-polish-notation

 출처

https://leetcode.com/problems/evaluate-reverse-polish-notation/

주식가격

 문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

 제한 사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

 입출력 예

 Python 코드

from collections import deque

def solution(prices):
    queue = deque(prices)  # prices로 queue를 초기화
    answer = []
    
    
    # 반복문 돌면서 앞에서부터 하나씩 popleft 한 뒤의 남은 queue를 순회하며 값이 작아지기 전까지
    # 초를 증가시키는 것을 queue가 빌때까지 반복
    while queue:
        price = queue.popleft() 
        sec = 0
        for q in queue:
            sec += 1
            if price > q:
                break 
        answer.append(sec)        
    return answer

* 참고 링크 : https://velog.io/@soo5717/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A3%BC%EC%8B%9D%EA%B0%80%EA%B2%A9-Python

def solution(prices):
    answer = [0] * len(prices)
    stack = []

    for i, price in enumerate(prices):

        while stack and price < prices[stack[-1]]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)

    while stack:
        j = stack.pop()
        answer[j] = len(prices) - 1 - j

    return answer

* 참고 링크 : 

def solution(prices):
    # answer = 몇초 후 가격이 떨어지는지 저장하는 배열
    answer = [len(prices)-i-1 for i in range(len(prices))]
    
    # stack = prices의 인덱스를 차례로 담아두는 배열
    stack = [0]
    
    for i in range(1, len(prices)):
        while stack:
            index = stack[-1]
            
            # 주식 가격이 떨어졌다면
            if prices[index] > prices[i]:
                answer[index] = i - index
                stack.pop()
            
            # 떨어지지 않았다면 다음 시점으로 넘어감 (주식 가격이 계속 증가하고 있다는 말)
            else:
                break
        
        # 스택에 추가한다.
        # 다음 시점으로 넘어갔을 때 다시 비교 대상이 될 예정이다.
        stack.append(i)
        
    return answer

* 참고 링크 : https://tngusmiso.tistory.com/34

 C++ 코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<int> s;
    int size = prices.size(); // 계속 size를 계산하는 것보다 상수값으로 저장하면 전체 함수 처리 시간 감소
    
    for (int i = 0; i < size; ++i){
        while (!s.empty() && prices[s.top()] > prices[i]){ // 가격이 줄어들었다면
            answer[s.top()] = i - s.top(); // 현재 시간 - 당시 시간
            s.pop();
        }
        s.push(i);
    }
    while (!s.empty()){
        answer[s.top()] = size - 1 - s.top(); // 종료 시간 - 당시 시간
        s.pop();
    }
    
    return answer;
}

* 참고 링크 : https://ssocoit.tistory.com/15

 출처

https://programmers.co.kr/learn/courses/30/lessons/42584

기능개발

 문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

 제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

 입출력 예

 Python 코드

import math # 수학과 관련된 함수들을 모아놓은 math 모듈 import

def solution(progresses, speeds):
    n = len(progresses)  # progresses 길이를 변수로 선언
    date_left = []       # 몇 일 남았는지 date_left라는 stack을 생성
    answer = []          # answer 배열로 생성
    
    for i in range(n):
        progress_left = 100 - progresses[i]   # 작업 진행률 확인
        share = math.ceil(progress_left / speeds[i]) # math.ceil() 함수를 이용한 올림
        date_left.append(share) # 몇 일 남았는지 share 몫을 구해 date_left append
        
# [7, 3, 9] -> 7보다 큰 값이 나올때까지 계속 더해줌 => result 2
# 0을 넣으면 left는 7이 되고 [3, 9]가 됨
# 7보다 큰 값이 나오면 탈출하여 answer.append(result)

# [9]
# answer = [2]
# left = 8 

# [9] -> []
# answer = [2, 1] // result default 값이 1이 들어감
    
    while date_left:
        left = date_left.pop(0)
        result = 1
        while len(date_left) != 0 and left >= date_left[0]: 
        # date_left의 길이가 0이 아니고, left가 date_left보다 크거나 같을 때
            result += 1        # 1일씩 추가
            date_left.pop(0)   # 추가 할 때마다 pop 시켜줌
        answer.append(result)  # 
        
    return answer

* 참고 링크 : https://www.youtube.com/watch?v=rdiXbJzgBPQ 

* math.ceil ( ) 함수 : 실수를 입력하면 올림하여 정수로 반환하는 함수

ceil은 천장을 의미하는 단어로 어떤 실수의 천장을 의미하는 바로 위 정수를 반환한다고 생각하면 좋다.

math.ceil(3.14)
# result : 4

math.ceil(-3.14)
# result : -3

math.ceil(0.15)
# result : 1

math.ceil(-0.15)   
# result : 0

math.ceil(3)  # 정수는 그대로 정수로 반환
# result : 3

math.ceil(-3)
# result : -3

* 참고 링크 : https://ooyoung.tistory.com/99

* pop ( ) 함수 : 리스트의 맨 마지막 요소를 돌려주고 그 요소는 삭제한다.

a = [1,2,3]
a.pop()     # result : 3
a           # result : [1, 2]

* 참고 링크 : https://wikidocs.net/14#pop

* append ( ) 함수 : append를 사전에서 검색해 보면 "덧붙이다, 첨부하다"라는 뜻이 있다. append(x)는 리스트의 맨 마지막에 x를 추가하는 함수이다.

a = [1, 2, 3]
a.append(4)
a
# result : [1, 2, 3, 4]

리스트 안에는 어떤 자료형도 추가할 수 있다.

다음 예는 리스트에 다시 리스트를 추가한 결과이다.

a.append([5,6])
a
# result : [1, 2, 3, 4, [5, 6]]

* 참고 링크 : https://wikidocs.net/14#append

 C++ 코드

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    //현재 진척도
    queue<int> current;
    //큐에 옮기기
    for (auto p : progresses)
        current.push(p);
    while (!current.empty()){
        //진척도 추가
        for (int i = 0; i < current.size(); i++){
            int p = current.front();
            current.pop();
            current.push(p + speeds.at(i));
        }
        int count = 0;
        //큐 내부검사
        while (true){
            //진척도가 100퍼센트 이상이라면 큐에서 제거하고 카운트 증가
            if (current.size() >0 && current.front() >= 100){
                current.pop();
                speeds.erase(speeds.begin());
                count++;
                continue;
            }
            break;
        }
        //카운트가 한개이상 올라갔다면
        //정답리스트에 몇개가 배포되는지 추가
        if (count > 0)
            answer.push_back(count);
    }
    return answer;
}

* 참고 링크 : https://mungto.tistory.com/197

 출처

https://programmers.co.kr/learn/courses/30/lessons/42586

다리를 지나는 트럭

 문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다.

모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다.

다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다.

단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다.

무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다.

이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

 제한 사항

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

 입출력 예

 Python 코드

# 시간 초과 코드

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = [0] * bridge_length # 다리 위의 리스트를 선언
    
    while len(bridge):
        answer += 1   # 1초씩 증가
        bridge.pop(0) # 다리 왼쪽 끝의 트럭을 pop
        if truck_weights: # 대기하는 트럭이 있다면
            bridge.append(truck_weights.pop(0)) # 다리에 트럭 추가
        else:
            bridge.append(0) # 무게가 아니라면 다리에 아무도 가지 않는다.
    return answer

* 참고 링크 1 : https://par3k.tistory.com/224

from collections import deque

def solution(bridge_length, weight, truck_weights):
    truck_weights = deque(truck_weights)   # truck_weights(대기트럭)을 담을 deque 생성
    bridge = deque([0 for _ in range(bridge_length)]) # 다리 길이만큼 0을 채워서 변수 생성 // 다리를 건너는 트럭
    time = 0           # 경과 시간
    bridge_weight = 0  # 지금 다리 위의 무게 // 현재 다리를 건너고 있는 무게

    while len(bridge) != 0:
        out = bridge.popleft() # 다리를 건너는 첫번째 트럭(bridge[0])를 pop 해줌
        bridge_weight -= out # 다리 무게에서 다리를 건넌 트럭의 무게를 빼줌
        time += 1 # 시간을 더해줌
        if truck_weights:  # deque에 요소가 남아 있으면 True
            # 현재 다리를 건너는 트럭의 무게와 다리에 오를 트럭의 무게의 합이
            if bridge_weight + truck_weights[0] <= weight:
                # 다리가 견딜 수 있는 무게 이하일 때
                left = truck_weights.popleft() # 대기트럭 deque에서 다음 트럭을 pop하고
                bridge_weight += left # 다리를 건너고 있는 트럭 무게에 더하고
                bridge.append(left) # 건너는 트럭 리스트에 넣어준다.
            else:
                # 다리가 견딜 수 있는 무게 초과일 때
                bridge.append(0) # 다음 트럭이 지나가지 못하므로 0을 채워준다.
    return time

* 참고 링크 2 : https://coblin.xyz/29

* 그림 설명 참고 링크 : https://eunhee-programming.tistory.com/149

* 참고 링크 3 : https://latte-is-horse.tistory.com/130

* 유튜브 설명 링크 : https://www.youtube.com/watch?v=Y9HYe4cUiZM&t=388s 

* deque 

• 양쪽 끝에서 빠르게 추가와 삭제를 할 수 있는 리스트류 컨테이너
• 양방향 큐
• 데이터의 회전도 가능
• maxlen을 설정하여 최대 항목 수를 설정

* 참고 링크 4 : https://www.youtube.com/watch?v=05roQ6gFwsM 

 C++ 코드

#include <queue>
#include <vector>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    
    int idx=0;    //차량 지목용 idx
    int sum=0;   //현재 다리에 올라와있는 차량 무게 총합
    queue<int> q;  //현재 다리를 건너는 트럭 체크용 큐
    
    while(1){
        
        if(idx == truck_weights.size()){  //마지막 트럭일 때
            answer += bridge_length;  //마지막 트럭이 지나는 시간 추가
            break;  
        }
        
        answer++; //시간초 증가
        int tmp = truck_weights[idx];
        
        //차가 다리를 다 건넜을 경우
        if(q.size() == bridge_length){
            sum -= q.front();  //다 건넜으니 현재 다리에 있는 차들의 무게에서 제외
            q.pop();  
        }
        
        if(sum + tmp <= weight){  //다리에 다음 차가 진입할 수 있다면
            sum += tmp;  //차량 무게 추가
            q.push(tmp);  
            idx++;  //다음 차량을 위해서
        }else{   
            q.push(0);  //진입할 수 없다면 0을 푸시해서 시간초 계산
        }
    }
   
    return answer;
}

* 참고 링크 : https://velog.io/@qhsh866/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Level2-%EB%8B%A4%EB%A6%AC%EB%A5%BC-%EC%A7%80%EB%82%98%EB%8A%94-%ED%8A%B8%EB%9F%AD-C

 출처

https://programmers.co.kr/learn/courses/30/lessons/42583

43. Multiply Strings

 문제 설명

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

 제한 사항

• 1 <= num1.length, num2.length <= 200
• num1 and num2 consist of digits only.
• Both num1 and num2 do not contain any leading zero, except the number 0 itself.

 입출력 예

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

 Python 코드

Python code 

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        def str_to_int(num_str):
            num = 0
            for i, c in enumerate(num_str[::-1]):
                num += pow(10, i) * (ord(c) - ord('0'))
            return num

        return str(str_to_int(num1) * str_to_int(num2))

* 참고 링크 : https://wellsw.tistory.com/94?category=1054641

 C++ 코드

C ++ code

class Solution {
public:
	string multiply(string num1, string num2) {
		string res(num1.size() + num2.size(), '0');
		for (int i = num1.size() - 1; i >= 0; --i) {
			int carry = 0;
			for (int j = num2.size() - 1; j >= 0; --j) {
				int tmp = (res[i + j + 1] - '0') + (num2[j] - '0')*(num1[i] - '0') + carry;
				res[i + j + 1] = tmp % 10 + '0';
				carry = tmp/10;
			}
			res[i] += carry;
		}
		auto pos = res.find_first_not_of('0');
		if (pos == string::npos)
			return "0";
		return res.substr(pos, res.length() - pos);
	}
};

* 참고 링크 : https://blog.fearcat.in/a?ID=00850-66ef66e8-11ca-463c-82ae-c4af5cb77fae

 출처

https://leetcode.com/problems/multiply-strings/

Remove Element

 문제 설명

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

 제한 사항

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

 입출력 예

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

 Python 코드

Python code 

class Solution: 
    def removeElement(self, nums: List[int], val: int) -> int:
        answer = [num for num in nums if num != val] 
        for i in range(len(answer)): 
            nums[i] = answer[i] 
            
        nums = nums[:len(answer)] 
        return len(nums)

* 참고 링크 : https://somjang.tistory.com/entry/leetCode-27-Remove-Element-Python

https://redquark.org/leetcode/0027-remove-element/

class Solution:
    def removeElement(self, nums, val):
        for i in range(len(nums)):
            if nums[0] != val:
                nums.append(nums[0])
                del nums[0]
            else:
                del nums[0]
        return len(nums)

* 참고 링크 : https://bortfolio.tistory.com/124

 C++ 코드

C ++ code

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int count = 0;
        for(int i = 0; i < nums.size(); i++){
            if (nums[i] != val){
                nums[count++] = nums[i];
            }
        }
        return count;
    }
};

* 참고 링크 : https://egbert-yu-ting.github.io/posts/1afffcb4/

https://lessbutbetter.tistory.com/entry/LeetCodeEasyC%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-27-Remove-Element

 출처

https://leetcode.com/problems/remove-element/

Valid Parentheses

 문제 설명

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

An input string is valid if:

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

 제한 사항

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

 입출력 예

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

 Python 코드

Python code 

class Solution:
  def isValid(self, s: str) -> bool:
      stack = []
      dic = {'(':')',
             '{':'}',
             '[':']'
            }

      for char in s:
          if char in dic.keys():
              stack.append(char)

          elif stack == [] or char != dic[stack.pop()] :
              return False

      return stack ==[]

* 참고 링크 : https://chaerim-kim.github.io/data%20structures%20and%20algorithms/ValidParentheses/

class Solution:
    def isValid(self, s: str) -> bool:
        stack=[]
        brackets={'}':'{',')':'(',']':'['}
        for bracket in s:
            if bracket in brackets.values(): #Opening bracket 
                stack.append(bracket)
            else:# Closing bracket
                if stack and brackets[bracket]==stack[-1] :  
                    stack.pop()
                else: 
                    return False
        
        if stack:
            return False
        return True

* 참고 링크 : https://velog.io/@kgh732/Python-%EC%9C%BC%EB%A1%9C-%ED%91%B8%EB%8A%94-Leetcode20.-Valid-Parentheses

class Solution: 
	def isValid(self, s: str) -> bool: 
    	s_list = list(s)
        
        answer = True 
        
        stack = [] 
        
        for s in s_list: 
        	if s == '[' or s == '(' or s == '{': 
            	stack.append(s) 
            elif len(stack) != 0: 
            	if (s == ']' and stack[-1] == '[') or (s == '}' and stack[-1] == '{') or (s == ')' and stack[-1] == '('): 
                	stack.pop() 
                else: 
                    answer = False 
                    break 
            else: 
            	answer = False 
                break 
                
        if len(stack) != 0: 
        	answer = False 
        return answer

* 참고 링크 : https://somjang.tistory.com/entry/leetCode-20-Valid-Parentheses-Python

C++ 코드

C ++ code

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        
        for(int i = 0; i < s.size(); i++) {
            if(s.at(i) == '{' || s.at(i) == '(' || s.at(i) == '[')      st.push(s.at(i));
            else {
                if(st.empty())      return false;
                else {
                    if((s.at(i) == '}' && st.top() != '{') || (s.at(i) == ')' && st.top() != '(') 
                        || (s.at(i) == ']' && st.top() != '['))
                            st.push(s.at(i));
                    else    st.pop();
                }
            }   
        }
        
        return st.empty();
    }
};

* 참고 링크 : https://m.blog.naver.com/tac1994/221839649888

 출처

https://leetcode.com/problems/valid-parentheses/submissions/