tenid's dev

1. 문제 설명

자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.

- 제한 사항

• n은 1 이상 100,000,000 이하인 자연수입니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;

    vector<int> arr = {};


    while (n > 0)
    {
        arr.push_back(n % 3);
        n /= 3;
    }

    int root = 1;

    for (int i = arr.size()-1; i >= 0; i--)
    {
        answer += arr[i] * root;
        root *= 3;

    }


    return answer;
}

3. 정리

나머지 연산을 통해 3진법을 구한다. push_back 함수를 써서 배열에 넣으면 마치 뒤집어진 것처럼 배열에 들어간다.

그리고 나서 1의 자리부터 3진법->10진법 변환 작업을 해야하므로 배열의 뒤부터 접근하여 계산하다.

전체 시간 복잡도는 O(log n) +  O(log n) =  O(log n)

1. n이 while문에서 3으로 0이 될때까지 계속 나누므로 시간 복잡도가 O(log n)이다.

2. 다음 for문에서 1번에서 순회할 크기가 log n 만큼 작아졌으므로 시간복잡도가 O(log n) 이다.

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/68935

1. 문제 설명

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.

- 제한 사항

• d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다.
• d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100,000 이하의 자연수입니다.
• budget은 예산을 나타내며, 1 이상 10,000,000 이하의 자연수입니다.

2. 풀이 코드

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>

using namespace std;


int partition(vector<int>& arr, int low, int high)
{
    int pivot = arr[high];
    int i = low-1;
    
    for(int j=low ; j<high; j++)
    {
        if(arr[j]< pivot)
        {
            swap(arr[++i], arr[j]);
        }
    }
    
    swap(arr[i+1],arr[high]);
    
    return i+1;
}


void quickSort(vector<int>& arr, int low, int high)
{
    if(low<high)
    {
        int pivotIdx = partition(arr, low, high);
        quickSort(arr, low, pivotIdx-1);
        quickSort(arr, pivotIdx+1, high);
    }
    
    
}



int solution(vector<int> d, int budget) {
    int cnt = 0;
    int dSize = d.size();
    quickSort(d, 0, dSize-1);
    
    for(int i = 0; i<dSize; i++)
    {
        budget-= d[i];
        if (budget < 0)
            break;
        cnt++;
    }
    
    return cnt;
}

3. 정리

적은 예산인 부서부터 지원하면 최대한 많은 부서들을 지원할 수 있다.

배열을 오름차순으로 정렬 후 반복문을 통해 예산이 음수가 되기 전까지 카운팅한다.

전체 시간 복잡도는 평균적으로 O(N log N + N) = O(N log N) , 최악의 경우 O(N² + N) = O(N²) 이다.

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12982

1. 문제 설명

숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분문자열 중에서, 이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 return하는 함수 solution을 완성하세요.

예를 들어, t="3141592"이고 p="271" 인 경우, t의 길이가 3인 부분 문자열은 314, 141, 415, 159, 592입니다. 이 문자열이 나타내는 수 중 271보다 작거나 같은 수는 141, 159 2개 입니다.

- 제한 사항

• 1 ≤ p의 길이 ≤ 18
• p의 길이 ≤ t의 길이 ≤ 10,000
• t와 p는 숫자로만 이루어진 문자열이며, 0으로 시작하지 않습니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;


int solution(string t, string p) {
    int answer = 0;

    int n = p.length();

    for (int i = 0; i <= t.length()-n; i++)
    {
        string num = t.substr(i, n);

        if (num <= p)
            answer++;
    }


    return answer;
}

3. 정리

for문을 이용하여 문자열의 초반부부터 인덱스+p문자열의 길이 만큼씩 잘라서 p보다 작거나 같은지 비교한다.

전체 시간 복잡도는 반복문을 t-p의길이 만큼 수행하기 때문에 O(N) 이다.

출처 :https://school.programmers.co.kr/learn/courses/30/lessons/147355

1. 문제 설명

배열 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보다 작거나 같은 정수

2. 풀이 코드

vector<int> solution(vector<int> arr)
{
    vector<int> answer = {arr[0]};

    int n = arr.size();

    int preNum = arr[0];

    for (int i = 1; i < n; i++)
    {

        if (arr[i] != preNum)
        { 
            answer.push_back(arr[i]);
        }

        preNum = arr[i];

    }

    return answer;
}

3. 정리

preNum 변수에 상시로 이전 값을 저장한다.  for문을 이용하여 배열 전체를 순회하면서 이전 값과 현재 인덱스의 값이 같으면 배열에 추가하지 않고 이전 값 갱신만 하고, 다르다면 정답 배열에 해당 값을 추가하고 이전 값을 갱신한다.

전체 시간 복잡도는 for문을 사용하니 O(n) 이다.

출처 :https://school.programmers.co.kr/learn/courses/30/lessons/12906

1. 문제 설명

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

- 제한 사항

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

2. 풀이 코드

#include <iostream>

using namespace std;

int main(void) {
    int n;
    int m;
    cin >> n >> m;
    
    for(int i =0 ; i<m; ++i){
        for(int j=0; j<n; ++j){
            cout << '*';
        }
         cout << endl;
    }
    
    
    
    return 0;
}

3. 정리

이중 for문을 이용하여 직사각형을 출력한다.

전체 시간 복잡도는 이중 for문을 사용하니 O(n²) 이다.

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

1. 문제 설명

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

- 제한 사항

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

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    vector<vector<int>> answer;
    
    int row = arr1.size();
    
    
    for(int i=0 ;i <row ; i++)
    {
        vector<int> sumArr = {};
        int col = arr1[0].size();
        
        for(int j=0;j<col;j++)
        {
            sumArr.push_back(arr1[i][j]+arr2[i][j]);
        }
        answer.push_back(sumArr);
    }
    
    
    return answer;
}

3. 정리

행과 열이 크기가 같은 것을 단서로 삼고, 배열의 같은 위치에 있는 것끼리 더해야 하므로 이중 포문을 이용하여 한다. 1번재 for문은 배열의 행을, 2번째 for문은 배열의 열을 탐색하여 덧셈을 한다. 2번째 for문이 끝나면 하나의 행이 만들어 지므로 정답 배열에 추가한다.

전체 시간 복잡도는 배열의 행과열 만큼 순회하니 O(n²) 이다.

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