Bin_S+StudyRoom

• 문제

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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 이하입니다.

• 입출력 예시

• 접근방식

선입 선출의 큐를 사용해야 하고 truck_weights.size() 가 0이 될 때 까지 반복한다. 단, 벡터의 끝을 사용하려고 (pop_back, back) reverse를 시켜 주었다.

1. 주어진 벡터를 뒤집고 벡터의 크기 만큼 반복하는데

2. 우선 반복을 시작하면 시간초가 증가하고 벡터의 끝 (첫 번째 트럭)을 가져온다. (temp)

3. 만약 큐의 크기가 다리 길이와 같다면 (다리 위에 다리 길이만큼의 트럭만 있을수 있기 때문) 다리 위에 있는 트럭의 전체 무게(currentTotalWeight)에서 큐의 첫번째 값을 빼준다. (다리를 지난 트럭)

4. weight 보다 가 currentTotalWeight 와 벡터의 끝의 트럭의 무게의 합보다 크거나 같다면 (weight >= currentTotalWeight + temp)

5. 다리에 트럭을 올리고(currentTotalWeight += temp) 큐에 넣어준다음 주어진 벡터에 끝자리를 뺀다. (pop_back)

6. 조건이 아니라면 큐에 0을 넣어주어 시간이 흘러가게 한다.

7. 마지막으로 시간에 다리의 길이까지 더해준다.

• 코드

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights)
{
    int answer = 0;
    int currentTotalWeight = 0;
    queue<int> q;

    reverse(truck_weights.begin(), truck_weights.end());
    
    while (truck_weights.size())
    {
        answer++;
        int temp = truck_weights.back();
        
        if (q.size() == bridge_length)
        {
            currentTotalWeight -= q.front();
            q.pop();
        }
        
        if (currentTotalWeight + temp <= weight)
        {
            currentTotalWeight += temp;
            q.push(temp);
            truck_weights.pop_back();
        }
        else
        {
            q.push(0);
        }
    }
    
    answer += bridge_length;
    
    return answer;
}

문제링크 :https://school.programmers.co.kr/learn/courses/30/lessons/42583

• 문제

문제 설명
0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.

1. x의 모든 0을 제거합니다.
2. x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다.
예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.

0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요.

• 제한 사항

s의 길이는 1 이상 150,000 이하입니다.
s에는 '1'이 최소 하나 이상 포함되어 있습니다.

• 입출력 예시

• 접근방식

s가 1이 될 때 까지 반복하는데 시도한 횟수 cnt, 0을 몇 번 제거한지 기록한 횟수 zerocnt

1. s의 길이만큼 반복하고 "1"이면 빈 문자열 temp에 1을 붙히고 아니라면(0이라면) zerocnt증가

2. temp 길이를 저장하고 (tempLength) temp와 s를 클리어

3. tempLength가 1미만이 될 때 까지 반복하는데 1이상이면 s에 0을 tempLengh % 2 만큼 넣고 tempLength /= 2를 해줌

4. 반복이 끝나면 나온 cnt와 zerocnt를 answer에 push_back

• 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(string s)
{
    vector<int> answer;
    string temp = "";
    int zerocnt = 0;
    int cnt = 0;
    
    while (s != "1")
    {
        cnt++;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == '1')
            {
                temp += s[i];
            }
            else
            {
                zerocnt++;
            }
        }
        
        int tempLength = temp.length();
        temp.clear();
        s.clear();
    
        while (tempLength >= 1)
        {
            s.insert(0, to_string(tempLength % 2));
            tempLength /= 2;
        }
    }
        
    answer.push_back(cnt);
    answer.push_back(zerocnt);
    
    return answer;
}

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/70129?language=cpp

• 문제

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

• 준호는 처음에 병사 n명을 가지고 있습니다.
• 매 라운드마다 enemy[i]마리의 적이 등장합니다.
• 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
  • 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
  • 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
• 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
• 무적권은 최대 k번 사용할 수 있습니다.
  준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

• 제한 사항

1 ≤ n ≤ 1,000,000,000
1 ≤ k ≤ 500,000
1 ≤ enemy의 길이 ≤ 1,000,000
1 ≤ enemy[i] ≤ 1,000,000
enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

• 입출력 예시

• 접근방식

우선 순위 큐가 떠올랐다. 우선 순위 큐란 간단히 말해서 큐와 같이 선입 선출의 자료구조이지만 우선 순위가 높은 데이터가 먼저 나가는 자료구조로 힙을 기반으로 구현되어 있다.

1. 우선 순위 큐를 오름 차순으로 선언 (top에 가장 작은 값)

2. enemy의 크기만큼 반복하면서 우선 순위 큐에 현재 순번 enemy를 담고

3. k의 개수보다 많이 쌓이면 answer에 우선 순위 큐 top을 더하고 pop 해준다

4. answer이 n보다 커지면 i (라운드) 반환

5. 모든 라운드 통과면 enemy의 크기 반환

• 코드

#include <vector>
#include <queue>

using namespace std;

int solution(int n, int k, vector<int> enemy)
{
    int answer = 0;
    
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for (int i = 0; i < enemy.size(); i++)
    {
        pq.push(enemy[i]);
        
        if (pq.size() > k)
        {
            answer += pq.top();
            pq.pop();
        }
        
        if (answer > n)
        {
            return i;
        }
    }
    
    return enemy.size();
}

문제링크 :https://school.programmers.co.kr/learn/courses/30/lessons/142085

• 문제

길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.
배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

• A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
• A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
• A에서 세번째 숫자인 2, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)
  즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

• 제한 사항

배열 A, B의 크기 : 1,000 이하의 자연수
배열 A, B의 원소의 크기 : 1,000 이하의 자연수

• 입출력 예시

• 접근방식

1. A와 B의 두 수를 곱했을 때 가장 작은 값이 나와야 다 더했을 때 최솟값이 됨

2. A를 오름 차순 정렬, B를 내림 차순 정렬하고 곱하면 된다

• 코드

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;

    sort(A.begin(), A.end());
    sort(B.rbegin(), B.rend());

    for (int i = 0; i < A.size(); i++)
    {
        answer += A[i] * B[i];
    }

    return answer;
}

문제링크 :https://school.programmers.co.kr/learn/courses/30/lessons/12941

• 문제

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

• 제한 사항

삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

• 입출력 예시

• 접근방식

1. 2차원 벡터 triangle을 표로 표현하면 아래와 같음

2. 표를 보면 i와 j의 위치를 가지고 본인 아래에 인접한 두 수를 찾을 수 있다. (왼쪽:i - 1, j) (오른쪽:i - 1, j - 1)

3. 임의의 2차원 배열(또는 벡터) dp를 정의하고 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j] 인데

4. 해당 행에서 숫자가 제일 왼쪽인 경우( j == 0)와 제일 오른쪽인 경우(j == i)만 예외 처리를 해주면 된다

5. 반복문 끝에 dp[i][j] += triangle[i][j]를 해주어서 dp에 저장되어 있는 값 중 제일 큰 값으로 계산해도 되지만 answer과 dp[i][j]를 바로 비교해도 괜찮다

• 코드

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

using namespace std;

int solution(vector<vector<int>> triangle)
{
    int answer = 0;
    
    vector<vector<int>> dp;
    dp.assign(501, vector<int>(501, 0));
    
    dp[0][0] = triangle[0][0];
    
    for (int i = 1; i < triangle.size(); i++)
    {
        for(int j = 0; j <= i; j++)
        {
            if (j == 0) // 제일 왼쪽
            {
                dp[i][j] = dp[i - 1][j] + triangle[i][j];
            }
            else if (j == i) // 제일 오른쪽
            {
                dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
            }
            
            answer = max(answer, dp[i][j]);
        }
    }
    
    
    return answer;
}

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43105

• 문제

xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.

• 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다.
• 사원은 딱 한 번씩 경기를 합니다.
• 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다.
• 만약 숫자가 같다면 누구도 승점을 얻지 않습니다.

전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 팀원들의 출전 순서를 정했습니다. 이때의 B팀이 얻는 승점을 구해주세요.
A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열 A와 i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열 B가 주어질 때, B 팀원들이 얻을 수 있는 최대 승점을 return 하도록 solution 함수를 완성해주세요.

• 제한 사항

A와 B의 길이는 같습니다.
A와 B의 길이는 1 이상 100,000 이하입니다.
A와 B의 각 원소는 1 이상 1,000,000,000 이하의 자연수입니다.

• 입출력 예시

• 접근방식

1. 우선 두 벡터를 오름 차순으로 정렬 해보기
2. aIndex와 bIndex를 0부터 시작해서 각각(aIndex, bIndex) 현재 A팀과 B팀의 크기보다 커지면 반복을 종료하는 반복문 시작
3. B팀의 현재 숫자가 A팀의 숫자보다 큰 경우, 승점 획득 > A팀과 B팀 모두 다음으로 넘어감 (A팀 index++, B팀 index++)
4. B팀의 현재 숫자가 A티므이 숫자보다 작은 경우, 해당 숫자 소모하고 B팀만 다음으로 넘어감 (B팀 index++)

• 코드

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

using namespace std;

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;
    
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    int aIndex = 0;
    int bIndex = 0;
    
    while (aIndex < A.size() && bIndex < B.size())
    {
        if (A[aIndex] < B[bIndex])
        {
            answer++;
            aIndex++;
        }
        bIndex++;
    }
    
    return answer;
}

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12987

• 문제

자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.

1. 각 원소의 합이 S가 되는 수의 집합
2. 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합
예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.
{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

• 제한 사항

최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.
자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

• 입출력 예시

• 접근방식

1. 각 원소의 합이 s, 즉 겹치지 않는 원소의 곱이 최대가 되는 집합을 찾으면 됨
2. 해당 집합은 n와 s를 나누기와 모듈러 연산을 통하여 구한다
3. s / n 으로 나눈 해당 숫자를 n개 만큼 생성후
4. s % n 으로 나운 숫자를 각각에 더해준다
5. 단, 만들 수 없는 경우는 (n > s) -1만 담고 return

• 코드

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

using namespace std;

vector<int> solution(int n, int s)
{
    vector<int> answer;
    
    if (n > s)
    {
        answer.push_back(-1);
        return answer;
    }
    
    int divideNumber = s / n;
    
    answer.assign(n, divideNumber);
    
    int modulerNumber = s % n;
    
    for (int i = 0; i < answer.size() && modulerNumber > 0; i++)
    {
        answer[i]++;
        modulerNumber--;
    }
    
    sort(answer.begin(), answer.end());
    return answer;
}

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12938

• 문제

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

• 제한 사항

문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

• 입출력 예시

• 접근방식

1. s에서 '('가 나오면 스택에 push
2. 만약 다른 문자 ( ')' )가 나오고 스택에 요소가 존재하면 pop
3. 그 외의 것은 false 출력
4. 반복문이 끝난 후 스택이 남아 있지 않으면 true 출력

• 코드

#include <string>
#include <iostream>
#include <stack>

using namespace std;

bool solution(string s)
{
    bool answer = false;
    stack<char> stk;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == '(')
        {
            stk.push(s[i]);
        }
        else if (stk.size())
        {
            stk.pop();
        }
        else
        {
            return answer;
        }
    }

    if (!stk.size())
    {
        answer = true;
    }

    
    return answer;
}

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12909