[COS Pro] 1급 체험 C++ (벡터 합, 최대/최소값)

Coding Test

[COS Pro] 1급 체험 C++ (벡터 합, 최대/최소값)

소젬 2022. 2. 26. 20:55

COS Pro (Professional Coding Specialist)란? Python, C, C++, Java 에 대한 자격증으로 높은 수준의 프로그래밍 활용능력이 있음을 증명 할 수 있습니다.

COS Pro (Professional Coding Specialist)는 시작부터 종료까지 100% 컴퓨터상에서 진행되는 CBT (Computer Based Test)로 평가방식이 정확함은 물론 시험 종료 즉시 시험 결과를 알 수 있습니다.

화요일까지 모의고사 6개 풀어보기

vector 합

<numeric>헤더의 accumulate함수
int sum = std::accumulate(v.begin(), v.end(), 0);

vector 순열

next_permutation함수

vector 최대값

max_element 함수
int max_index = max_element(v.begin(), v.end()) - v.begin();
int max = *max_element(v.begin(), v.end());

https://www.ybmit.com/cos_pro/cos_pro_sam.jsp

YBM IT

국제 IT 자격증

www.ybmit.com

꽃 피우기

15분

문제 설명

정사각형 크기 격자 모양 정원에 칸마다 핀 꽃 또는 피지 않은 꽃을 심었습니다. 이 정원의 꽃이 모두 피는 데 며칠이 걸리는지 알고 싶습니다. 핀 꽃은 하루가 지나면 앞, 뒤, 양옆 네 방향에 있는 꽃을 피웁니다.

현재 정원의 상태를 담은 2차원 배열 garden이 주어졌을 때, 모든 꽃이 피는데 며칠이 걸리는지 return 하도록 solution 함수를 작성해주세요.

매개변수 설명

현재 정원 상태를 담은 2차원 배열 garden이 solution 함수의 매개변수로 주어집니다.

정원의 한 변의 길이는 2 이상 100 이하입니다.
정원 상태를 담은 2차원 배열 garden의 원소는 0 또는 1 입니다.
이미 핀 꽃은 1로 아직 피지 않은 꽃은 0으로 표현합니다.
정원에 최소 꽃 한 개는 피어 있습니다.

return 값 설명

꽃이 모두 피는데 며칠이 걸리는지 return 합니다.

예제gardenreturn

[[0, 0, 0], [0, 1, 0], [0, 0, 0]]	2
[[1, 1], [1, 1]]	0

예제 설명

예제 #1
첫 날 정원은 아래와 같습니다.

1일이 지난 정원의 상태는 아래와 같습니다.

2일이 지난 정원의 상태는 아래와 같습니다.

따라서, 2일이 지나면 정원의 모든 꽃이 핍니다.

예제 #2
첫 날 화단의 상태는 아래와 같습니다.

따라서, 0일이 지나면 정원의 모든 꽃이 핍니다.

// 다음과 같이 include를 사용할 수 있습니다.
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <numeric>

using namespace std;

int solution(vector<vector<int>> garden) {
    // 여기에 코드를 작성해주세요.
    int answer = 0;
    
    int dy[] = {0,0,-1,1};
    int dx[] = {-1,1,0,0};
    
    int sum = 0;

    while(1) {
        sum = 0;
        for(vector<int> v : garden)
            sum += accumulate(v.begin(), v.end(), 0);
        
        if(sum == garden.size() * garden.size()) break;
        
        queue<pair<int,int> > q;

        for(int i=0; i<garden.size(); i++) 
            for(int j=0; j<garden.size(); j++)
                if(garden[i][j] == 1)
                    q.push(make_pair(i, j));
        while(!q.empty()) {
            int sy = q.front().first, sx = q.front().second;
            for(int dir = 0; dir<4; dir++) {
                int y = sy+dy[dir], x = sx+dx[dir];
                if(y < 0 || x < 0 || y >= garden.size() || x>= garden.size()) continue;
                garden[y][x] = 1;
            }
            q.pop();
        }    
        answer++;
    }
    
    return answer;
}

// 아래는 테스트케이스 출력을 해보기 위한 main 함수입니다.
int main() {
    vector<vector<int>> garden1 = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
    int ret1 = solution(garden1);
    
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    cout << "solution 함수의 반환 값은 " << ret1 << " 입니다." << endl;
    
    vector<vector<int>> garden2 = {{1, 1}, {1, 1}};
    int ret2 = solution(garden2);
    
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    cout << "solution 함수의 반환 값은 " << ret2 << " 입니다." << endl;
}

숫자 뽑기

시간초과

문제 설명

자연수가 들어있는 배열에서 숫자 K개를 선택하려 합니다. 이때, 선택한 숫자 중 가장 큰 수와 가장 작은 수의 차이가 최소가 되도록 해야합니다.

예를 들어 배열에 들어있는 숫자가 [9, 11, 9, 6, 4, 19] 이고, K = 4 라면

숫자 4개를 [9, 11, 9, 6]로 뽑으면 (가장 큰 수 - 가장 작은 수) = (11 - 6) = 5가 됩니다.
[9, 9, 6, 4] 와 같이 숫자를 뽑아도 (가장 큰 수 - 가장 작은 수) = (9 - 4) = 5가 됩니다.

그러나 가장 큰 수와 가장 작은 수의 차이가 5보다 작아지도록 숫자 4개를 선택하는 방법은 없습니다.

자연수가 들어있는 배열 arr, 선택해야 하는 숫자 개수 K가 매개변수로 주어질 때, 선택한 숫자중 가장 큰 수와 가장 작은 수의 차이가 최소가 되록 arr에서 숫자 K개를 선택했을 때, 그때의 가장 큰 수와 가장 작은 수의 차이를 return 하도록 solution 함수를 완성해주세요.

매개변수 설명

자연수가 들어있는 배열 arr, 선택해야 하는 숫자 개수 K가 solution 함수의 매개변수로 주어집니다.

arr 배열의 길이는 5 이상 1,000 이하입니다.
arr의 원소는 1 이상 10,000 이하인 자연수입니다.
K 는 4 이상 50 이하인 자연수입니다.

return값 설명

선택한 숫자중 가장 큰 수와 가장 작은 수의 차이가 최소가 되도록 arr에서 숫자 K개를 선택했을 때, 그때의 가장 큰 수와 가장 작은 수의 차이를 return 해주세요.

순열을 쓰니까 시간초과가 뜬다..!

다시 풀어보니 간단히 생각하면 되는 문제였다...

// 다음과 같이 include를 사용할 수 있습니다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> arr, int K) {
    // 여기에 코드를 작성해주세요.
    int answer = 10000;
    vector<int> v(arr.size() - K, 0);
    do{
        v = arr;
        for(int i=0; i<arr.size() - K; i++) v.erase(v.end()-1); 
        sort(v.begin(),v.end());
        
        answer = min(answer, v.back() - v.front());
    }while(next_permutation(arr.begin(),arr.end()));
    
    return answer;
}

// 아래는 테스트케이스 출력을 해보기 위한 main 함수입니다.
int main() {
    vector<int> arr = {9, 11, 9, 6, 4, 19};
    int K = 4;
    int ret = solution(arr, K);

    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    cout << "solution 함수의 반환 값은 " << ret << " 입니다." << endl;
}

두번째 푼 소스

int solution(vector<int> arr, int K) {
    // 여기에 코드를 작성해주세요.
    int answer = 10000;

    sort(arr.begin(),arr.end());
    for(int i=0; i<arr.size()-K+1; i++) {
        answer = min(answer, arr[K-1+i]-arr[i]);
    }
    return answer;
}

메모장

6분30초

문제 설명

한 줄에 K자를 적을 수 있는 메모장에 영어 단어들을 적으려 합니다. 영어 단어는 정해진 순서로 적어야 하며, 단어와 단어 사이는 공백 하나로 구분합니다. 단, 한 줄의 끝에 단어 하나를 완전히 적지 못한다면, 그 줄의 나머지 부분을 모두 공백으로 채우고 다음 줄부터 다시 단어를 적습니다.

예를 들어 한 줄에 10자를 적을 수 있고, 주어진 단어가 순서대로 ["nice", "happy", "hello", "world", "hi"] 인 경우 각 줄에 다음과 같이 적을 수 있습니다.('_'는 공백을 나타냅니다.)

첫째 줄 : "nice_happy"
둘째 줄 : "hello_____"
셋째 줄 : "world_hi"

이때, 둘째 줄에 "hello"를 적으면 단어를 적을 수 있는 남은 칸은 5칸이며, "world"를 이어서 적으려면 공백 하나를 포함하여 총 6칸이 필요합니다. 따라서 단어가 잘리게 되므로 남은 칸을 모두 공백으로 채운 후, 다음 줄에 "world"부터 다시 단어를 적어 나갑니다.

한 줄에 적을 수 있는 글자 수 K와 적을 단어가 순서대로 담긴 배열 words가 매개변수로 주어질 때, 단어를 모두 적으면 몇 줄이 되는지 return 하도록 solution 함수를 완성해주세요.

매개변수 설명

한 줄에 적을 수 있는 글자 수 K와 적을 단어가 순서대로 담긴 배열 words가 solution 함수의 매개변수로 주어집니다.

K는 5 이상 30 이하인 자연수입니다.
words 배열의 길이는 1 이상 100 이하입니다.
words 배열에 담겨있는 모든 단어는 알파벳 소문자로만 이루어져 있으며, 각 단어의 길이는 K 이하입니다.

return값 설명

단어를 모두 적으면 몇 줄이 되는지 return해주세요.

// 다음과 같이 include를 사용할 수 있습니다.
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int solution(int K, vector<string> words) {
    // 여기에 코드를 작성해주세요.
    int answer = 1;
    int rest = K;
    
    for(string &word : words) {
        if(rest <= 0) {
            answer ++;
            rest = K;
        }
        if(rest >= word.size()) {
            rest = rest - (word.size() + 1);
        } else {
            answer ++;
            rest = K - (word.size() + 1);
        }
    }
    
    return answer;
}

// 아래는 테스트케이스 출력을 해보기 위한 main 함수입니다.
int main() {
    int K = 10;
    vector<string> words = {"nice", "happy", "hello", "world", "hi"};
    int ret = solution(K, words);

    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    cout << "solution 함수의 반환 값은 " << ret << " 입니다.";
}

저작자표시 비영리 변경금지

'Coding Test' 카테고리의 다른 글

[COS Pro] 1급 2차 C++ (조합) (0)	2022.02.28
[COS Pro] 1급 1차 C++ (0)	2022.02.27
[카카오]Lv2 거리두기 확인하기 C++ (0)	2022.02.23
[카카오]Lv2 멀쩡한 사각형 C++ (최대공약수) (0)	2022.02.23
Lv2 짝지어 제거하기 C++ (Stack) (0)	2022.02.16

현재글[COS Pro] 1급 체험 C++ (벡터 합, 최대/최소값)

뭣때멋대루

The merit of an action lies in finishing it to the end.

find함수, 백준, string find함수, iterator insert erase, split함수, 알고리즘, C++, BFS, 문자열 소문자, vector 수정, 소문자전환, vector find, 백준 알고리즘, map정렬, tolower, SW역량테스트, map 조회, 문자열 합집합, vector iterator, n진수,

Today :
Yesterday :

뭣때멋대루