deeprun

평균 구하기

 문제 설명

N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다.

위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

 제한 사항

• 마을의 개수 N은 1 이상 50 이하의 자연수입니다.
• road의 길이(도로 정보의 개수)는 1 이상 2,000 이하입니다.
• road의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.
• road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.
  • a, b(1 ≤ a, b ≤ N, a != b)는 도로가 연결하는 두 마을의 번호이며, c(1 ≤ c ≤ 10,000, c는 자연수)는 도로를 지나는데 걸리는 시간입니다.
  • 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.
  • 한 도로의 정보가 여러 번 중복해서 주어지지 않습니다.
• K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.
• 임의의 두 마을간에 항상 이동 가능한 경로가 존재합니다.
• 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.

 입출력 예

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
주어진 마을과 도로의 모양은 아래 그림과 같습니다.

1번 마을에서 배달에 4시간 이하가 걸리는 마을은 [1, 2, 3, 5] 4개이므로 4를 return 합니다.

 Python 코드

플로이드워셜

def solution(N, road, K):
    INF = 1000000000
    answer = 0
    graph = [[INF] * (N + 1) for _ in range(N + 1)]
 
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if i == j:
                graph[i][j] = 0
 
    for r in road:
        a, b, c = r[0], r[1], r[2]
        if graph[a][b] > c:
            graph[a][b] = c
            graph[b][a] = c
 
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for k in range(1, N + 1):
                graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])
 
    for j in range(1, N + 1):
        if graph[1][j] <= K:
            answer += 1
 
    return answer

다익스트라 

from queue import PriorityQueue
 
 
def solution(N, road, K):
    INF = 1000000000
    answer = 0
    distance = [INF] * (N + 1)
 
    q = PriorityQueue()
    q.put([1, 0])
    distance[1] = 0
    while not q.empty():
        now, now_cost = q.get()
 
        if now_cost > distance[now]: continue
        for start, dest, cost in road:
            next_cost = now_cost + cost
            if start == now and next_cost < distance[dest]:
                distance[dest] = next_cost
                q.put([dest, next_cost])
            elif dest == now and next_cost < distance[start]:
                distance[start] = next_cost
                q.put([start, next_cost])
 
    for i in range(1, N + 1):
        if distance[i] <= K:
            answer += 1
 
    return answer

* 참고 링크 : https://foameraserblue.tistory.com/86

 C++ 코드

#include <vector>
#include <queue>
using namespace std;
 
vector<pair<int,int>> V[55];
vector<int> Dist;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Dijkstra(int N)
{
    priority_queue<pair<int, int>> PQ;
    PQ.push(make_pair(0, 1));
    Dist[1] = 0;
 
    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        for (int i = 0; i < V[Cur].size(); i++)
        {
            int Next = V[Cur][i].first;
            int nCost = V[Cur][i].second;
 
            if (Dist[Next] > Cost + nCost)
            {
                Dist[Next] = Cost + nCost;
                PQ.push(make_pair(-Dist[Next], Next));
            }
        }
    }
}
 
int solution(int N, vector<vector<int> > road, int K)
{
    Dist.resize(N + 1, 2e9);
    for (int i = 0; i < road.size(); i++)
    {
        int N1 = road[i][0];
        int N2 = road[i][1];
        int Dist = road[i][2];
 
        V[N1].push_back(make_pair(N2, Dist));
        V[N2].push_back(make_pair(N1, Dist));
    }
 
    Dijkstra(N);
    int answer = 0;
    for (int i = 1; i <= N; i++)
    {
        if (Dist[i] <= K) answer++;
    }
 
    return answer;
}

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

 출처

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

소수찾기

 문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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

주식가격

 문제 설명

초 단위로 기록된 주식가격이 담긴 배열 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

정수 제곱근 판별

 문제 설명

임의의 양의 정수 n에 대해, n이 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 합니다.
n이 양의 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함수를 완성하세요.

 제한 사항

• n은 1이상, 50000000000000 이하인 양의 정수입니다.

 입출력 예

 Python 코드

from math import sqrt
 
def solution(n):
    return int(sqrt(n) + 1) ** 2 if sqrt(n) % 1 == 0 else -1

* 참고 링크 : https://velog.io/@cosmos/Programmers%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A0%95%EC%88%98-%EC%A0%9C%EA%B3%B1%EA%B7%BC-%ED%8C%90%EB%B3%84-python

def solution(n):
    answer = 0
    num = n ** 0.5
 
    if num == int(num):
        answer = (num+1) ** 2
    else:
        answer = -1
 
    return answer

* 참고 링크 : https://jokerldg.github.io/algorithm/2021/04/14/int-sqrt.html

 C++ 코드

#include <string>
#include <vector>
#include <cmath>
using namespace std;
 
long long solution(long long n) {
	if (sqrt(n) - (int)sqrt(n) == 0) // n이 정수의 제곱인 경우
		return (sqrt(n) + 1) * (sqrt(n) + 1);
	return -1;
}

* 참고 링크 : https://greenapple16.tistory.com/129

 출처

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

최대공약수와 최소공배수

 문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

 입출력 예

 Python 코드

from math import gcd
def solution(n, m):
    gcd_num = gcd(n, m)
    lcm_num = n*m // gcd(n,m)
    answer = [gcd_num, lcm_num]
    return answer

 C++ 코드

#include <string>
#include <vector>
 
using namespace std;
 
vector<int> solution(int n, int m) {
    vector<int> answer;
    int a, b, r;
    
    a = n;
    b = m;
    
    while(b != 0) {
        r = a % b;
        a = b;
        b = r;        
    }
    
    answer.push_back(a);
    answer.push_back(n * m / a);
    
    return answer;
}

 출처

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

자릿수 더하기

 문제 설명

자연수 N이 주어지면, N의 각 자릿수의 합을 구해서 return 하는 solution 함수를 만들어 주세요.
예를들어 N = 123이면 1 + 2 + 3 = 6을 return 하면 됩니다.

 제한 사항

• N의 범위 : 100,000,000 이하의 자연수

 입출력 예

 Python 코드

def solution(n):
    new = str(n)
    add = 0 
    
    for i in range(len(new)):
        add += int(new[i])
    return add

n을 문자열로 바꿔 new에 저장.
new의 길이 만큼 반복하는 i, 그동안 n의 i 인덱스 값을 add에 계속 더해줌. (더할 때는 int로 바꿔줘야 연산가능)
add 값 return

def sum_digit(number):
    return sum([int(i) for i in str(number)])

sum 함수를 통해 한 줄로 표현 가능

* 참고 링크 : https://velog.io/@joygoround/test%EC%9E%90%EB%A6%BF%EC%88%98-%EB%8D%94%ED%95%98%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

 C++ 코드

#include <iostream>
using namespace std;
 
int solution(int n)
{
    int answer = 0;
 
    while(n != 0)
    {
        answer = answer + n%10;
        n = n/10;
    }
 
    return answer;
}

* 참고 링크 : https://blockdmask.tistory.com/282

 출처

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

행렬의 덧셈

 문제 설명

행렬의 덧셈은 행과 열의 크기가 같은 두 행렬의 같은 행, 같은 열의 값을 서로 더한 결과가 됩니다. 2개의 행렬 arr1과 arr2를 입력받아, 행렬 덧셈의 결과를 반환하는 함수, solution을 완성해주세요.

 제한 사항

• 행렬 arr1, arr2의 행과 열의 길이는 500을 넘지 않습니다.

 입출력 예

 Python 코드

def solution(arr1, arr2):
    for i in range(len(arr1)):
        for j in range(len(arr1[0])):
            arr1[i][j] += arr2[i][j]
    return arr1

이중 for문으로 행렬의 행과 열에 접근

먼저 변수 i는 리스트 arr1의 길이만큼 반복문에 적용

이때 len(arr1)은 행렬이 [[]]형식 일 때 바깥 대괄호에서 적용되는 길이

[[], [], ...]로 된 행렬은 리스트의 데이터로 리스트를 포함하고 있는 것으로

arr1의 길이라고 하면 안쪽 대괄호의 개수 즉 행의 개수라고 할 수 있음

두 번째 for문 변수 j는 len(arr1[0])만큼 반복되는데,

이는 [[], [], ...] 형식의 행렬에서 안쪽 대괄호 안의 데이터 개수이므로 열의 개수임

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

 C++ 코드

#include<iostream>
#include<vector>
using namespace std;
 
vector<vector<int> > sumMatrix(vector<vector<int> >A, vector<vector<int> >B)
{
    vector<vector<int> > answer;
 
    for(int i=0; i<A.size(); i++){  //2차원 배열의 y
 
        vector<int> v;              //하나의 y에 대한 x의 값들 (1차원 배열이라고 생각)
 
        for(int j=0; j<A[0].size(); j++){   //2차원 배열의 x
            v.push_back(A[i][j] + B[i][j]);
        }
 
        answer.push_back(v);
    }
    return answer;
}

* 참고 링크 : https://blockdmask.tistory.com/256

 출처

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

직사각형 별찍기

 문제 설명

이 문제에는 표준 입력으로 두 개의 정수 n과 m이 주어집니다.
별(*) 문자를 이용해 가로의 길이가 n, 세로의 길이가 m인 직사각형 형태를 출력해보세요.

 제한 사항

• n과 m은 각각 1000 이하인 자연수입니다.

 입출력 예

입력

5 3

출력

*****
*****
*****

 Python 코드

a, b = map(int, input().strip().split(' '))
answer = ('*' * a + '\n') * b
print(answer)

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

 C++ 코드

#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
    int a;
    int b;
    cin >> a >> b;
	
    string s="";
    //a 갯수만큼 * 더해주기
    s.append(a,'*');
    
    for(int i =0;i<b;i++) {
        cout << s << endl;
    }
    return 0;
}

* 참고 링크 : https://programforlife.tistory.com/25

 출처

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

같은 숫자는 싫어

 문제 설명

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

• arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
• arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

 제한 사항

• 배열 arr의 크기 : 1,000,000 이하의 자연수
• 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

 입출력 예

 Python 코드

def solution(arr):
    answer = []                       # 답을 담을 배열 선언
    answer.append(arr[0])             
    
    for i in range(1, len(arr)):      # 주어진 배열을 하나씩 접근
        if arr[i-1] != arr[i]:        # arr[i-1]과 arr[i] 값이 같지 않다면
          answer.append(arr[i])       # answer에 arr[i]를 append하여 추가
 
    return answer

• 먼저 첫번째 값을 배열에 넣어준다.
• 이전값과 현재값을 비교하여 틀리면 배열에 추가해준다.

* 참고 링크 : https://jokerldg.github.io/algorithm/2021/04/03/no-same-number.html

 C++ 코드

#include <vector>
#include <iostream>
 
using namespace std;
 
vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
    
    for(int i = 0; i < arr.size(); i++)
    {
        if(answer.size() == 0 || answer[answer.size() - 1] != arr[i]) 
            answer.push_back(arr[i]);
    }
 
    return answer;
}

* 참고 링크 :  https://c1oud9.tistory.com/171

 출처

https://programmers.co.kr/learn/courses/30/lessons/12906?language=python3