tenid's dev

1. 문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

- 제한 사항

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

2. 풀이 코드

#include <string>
#include <iostream>

using namespace std;

bool solution(string s)
{
    int cnt = 0;
    for(char c : s)
      {
        if(c == '(')
          cnt++;
        else if(c == ')')
          cnt--;

        if(cnt<0)
          return false;
      }
    return cnt==0;
}

3. 정리

문자열 전체를 순회 하면서 괄호의 짝이 맞는지를 체크하는 것이 관건인 문제이다. 따라서 '(' 일때는 +1를 하고 ')' -1를 하며 기본적으로 마지막에 0이 되면 올바른 괄호로 판단하지만 순회하는 중간 카운트가 0보다 작으면 올바르지 않은 ')'가 나온 것이므로 바로 false를 리턴한다.

전체 시간 복잡도는 문자열 길이만큼 순회하기 때문에 O(N) 이다.

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

1. 문제 설명

한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.

한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.

- 제한 사항

• 3 ≤ number의 길이 ≤ 13
• -1,000 ≤ number의 각 원소 ≤ 1,000
• 서로 다른 학생의 정수 번호가 같을 수 있습니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> number) {
    int answer = 0;
    int n = number.size();
    
    
    for(int i=0;i<n-2;i++)
    {
        for(int j=i+1;j<n-1;j++)
        {
            for(int k=j+1;k<n;k++)
            {
                if(number[i]+number[j]+number[k] == 0)
                    answer++;
            }
            
        }
    }
    
    return answer;
    
}

3. 정리

배열에서 3개를 뽑아 0이 되는 모든 경우를 찾아야 하기 때문에 삼중 루프를 이용하여 모든 경우를 탐색한다.

전체 시간 복잡도는 삼중루프 이기 때문에 O(n³) 이다.

배열의 길이가 짧기 때문에 시간 초과는 나지 않는다.

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

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