KPSC Welcome Contest 2024 - UPSOLVING

대회 날짜 : 2024년 5월 12일

 

A. 학식 사주기 ( UPSOLVING ) Bronze 4

문제 바로가기 (클릭시 이동)

시간 제한 1초 / 메모리 제한 1024 MB

알고리즘 분류 : 구현

 

화석인 당신은 국민대학교에 갓 입학한 새내기들에게 학식을 사주기로 했다. 국민대학교 학생식당에서는 서로 다른 번호가 부여된 여러 코너에서 각기 다른 식사 메뉴를 판매하는데, 새내기들이 먹고 싶어 하는 메뉴가 다양해서 결제해야 하는 금액을 계산하는 데 어려움을 겪고 있다.

각 코너에서 판매하는 메뉴의 가격과 새내기들이 먹고 싶어 하는 메뉴를 판매하는 코너의 번호가 주어지면 결제해야 하는 금액의 총액을 출력해 보자.

 

CODE - C++

#include <iostream>
#include <vector>
using namespace std;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<int> V;
    int N,M,S=0;
    cin >> N;
    while(N--){
        int A;
        cin >> A;
        V.push_back(A);
    }
    cin >> M;
    while(M--){
        int B;
        cin >> B;
        S+=V[B-1];
    }
    cout << S;
    return 0;
}

이 문제는 N개의 음식과 M개의 먹고 싶은 음식번호를 입력받아서 총액을 구하는 문제다.

나는 vector에 음식의 가격을 다 넣고 M개의 입력받은 음식번호의 인덱스를 참조해서 총액에 더하는 방식으로 풀었다.

• 시간복잡도 : O( N + M )
• 공간복잡도 : O( N )

 

B. 재수강 ( UPSOLVING ) Bronze 4

문제 바로가기 (클릭시 이동)

시간 제한 1초 / 메모리 제한 1024 MB

알고리즘 분류 : 구현, 문자열

 

국민대학교에서는 수강 신청, 성적 조회 등 과목의 구분이 필요할 때 ’과목 코드’를 사용한다. 과목 코드는 10자리로 이루어져 있으며, 7번째 자리는 영어 알파벳 대문자 또는 숫자, 8번째 자리는 하이픈(-), 나머지 자리는 숫자로 이루어져 있다.

당신은 망한 학점을 복구하기 위해 재수강을 해야 하는데, 재수강을 하기 위해서는 재수강할 과목과 과목코드의 앞 5자리가 일치하는 과목을 수강해야 한다. 재수강할 과목의 과목 코드와 수강 신청 가능한 과목 목록이 주어지면, 재수강으로 인정되는 과목이 몇 개가 있는지 출력하라.

 

CODE - C++

#include <iostream>
using namespace std;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string A,B;
    short N,S=0;
    cin >> A >> N;
    while(N--){
        cin >> B;
        if (A.substr(0,5)==B.substr(0,5)){
            S++;
        }
    }
    cout << S;
    return 0;
}

이 문제는 처음 입력받은 문자열과 N개의 문자열중에서 처음 5개의 자리가 일치하는 문자열의 개수를 구하는 문제다.

나는 substr으로 문자열을 5자리 잘라서 구현을 했다.

• 시간복잡도 : O( N )
• 공간복잡도 : O( 1 )

 

C. 악질 검거 ( UPSOLVING ) Bronze 1

문제 바로가기 (클릭시 이동)

시간 제한 1초 / 메모리 제한 1024 MB

알고리즘 분류 : 구현

 

2034년, 국민대학교의 KPSC 동아리는 그 명성이 대단하여 국민대 자체보다도 KPSC가 더 유명해졌다.

이러한 명성 때문에 많은 사람들이 KPSC에 가입하고자 했으나, 동아리의 명성을 유지하기 위해 한정된 인원만 받고 나머지는 모두 탈락시켜 버렸다.

그러나 동아리에 들어온 후 프로그래밍 공부를 소홀히 하며 잠적하는 회원들이 생겨나기 시작했다.

이러한 상황을 목격한 부동아리장은 분노하여 '리버스-스트릭을 이용한 강퇴'라는 새로운 규칙을 도입하기로 했다. 여기서 '리버스-스트릭'이란, 문제를 며칠 연속으로 풀지 않았는지 보여주는 지표를 의미한다. 즉, 총 𝑥일 동안 연속해서 문제를 전혀 풀지 않았다면 '리버스-스트릭' 𝑥일이라고 한다.

부동아리장을 도와 동아리에 들어온 후 잠적하며 동아리 활동을 소홀히 하는 '악질' 회원들을 식별하는 데 도움을 주자!

 

CODE - C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<pair<short,string>> V;
    vector<short> S,X;
    string A;
    short N,M,m,i;
    char c;
    cin >> N >> M;
    while(N--){
        for (i=0;i<M;i++){
            cin >> c;
            if (c=='.') X.push_back(1);
            else X.push_back(0);
        }
        cin >> A;
        m=X.front();
        for (i=1;i<M;i++){
            if (X[i]){
                X[i]+=X[i-1];
                m=max(m,X[i]);
            }
        }
        V.push_back({m,A});
        S.push_back(m);
        X.clear();
    }
    sort(S.begin(),S.end());
    S.erase(unique(S.begin(),S.end()),S.end());
    cout << S.size() << "\n";
    for (i=0;i<V.size();i++){
        cout << V[i].first << ' ' << V[i].second << "\n";
    }
    return 0;
}

이 문제는 특정 문자를 숫자로 바꾸고 누적합의 최댓값과 중복하지 않는 최댓값의 개수를 찾는 문제다.

char형 변수와 vector를 따로 선언하고 vector에 숫자를 넣으면서 누적합을 해주면 최댓값은 해결했다.

최댓값의 개수는 vector를 선언하고 값을 넣어서 중복을 제거한 vector의 크기를 출력하면 된다.

• 시간복잡도 : O( NM + N log N )
• 공간복잡도 : O( NM )

 

D. 근로장학생 ( UPSOLVING ) Silver 3

문제 바로가기 (클릭시 이동)

시간 제한 1초 / 메모리 제한 1024 MB

알고리즘 분류 : 구현, 자료 구조, 문자열, 정렬, 해시를 사용한 집합과 맵

 

하루는 문장 내에 있는 영어 단어를 찾아 그 뜻을 알려주는 프로그램을 만드는 근로장학생이 되었다.

하지만 하루는 너무 귀찮은 나머지 프로그램을 만들지 않았고, 제작 마감일 1일전 당신에게 급하게 프로그램을 만드는 걸 도와달라고 요청했다. 하루를 도와주자.

• 각 정보는 (𝑄𝑖,𝐴𝑖)로 이루어져 있으며, 𝑄𝑖는 영어 단어, 𝐴𝑖는 그 단어의 뜻을 의미한다.
• 프로그램에게 𝑁개의 정보와 𝑀개의 문장이 주어질 때, 각 문장에 대해 프로그램이 답하는 과정은 다음과 같다.
  • 문장 𝑆의 가장 왼쪽에 있는 문자의 위치를 1, 가장 오른쪽에 있는 문자의 위치를 |𝑆|라고 하자. 이때 |𝑆|는 문장 𝑆의 길이를 의미한다.
  • 프로그램은 각 문장 𝑆의 첫 번째 문자부터, 마지막 문자까지 𝑆1, 𝑆2 ⋯, 𝑆|𝑆|−1, 𝑆|𝑆|의 순서로 읽는다.
  • 문장을 읽는 도중, 만약 위치 𝑘에서 위치 𝑘, 𝑘+1, ⋯, 𝑘+|𝑄𝑖|−1에 있는 문자를 순서대로 이어 붙였을 때 𝑄𝑖를 만들 수 있다면 𝐴𝑖로 답해야 하며, 𝑘에 대해 만들 수 있는 𝑄𝑖가 여러 개라면, 사전순으로 앞선 𝑄𝑖부터 𝐴𝑖로 답하면 된다.
  • 한 문장에 대해 답해야 하는 𝐴𝑖는 여러개일 수 있다.

예를 들어, 정보 (𝑄𝑖,𝐴𝑖)가 (ABC, X), (A, Y), (CDE, Z)이고 질문이 ABCDE라면 프로그램은 YXZ로 답해야 한다.

 

CODE - C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<string,string> A,pair<string,string> B){
    return A.first<B.first;
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<pair<string,string>> V;
    string S;
    short N,M,i,j;
    bool f=true;
    cin >> N >> M;
    while(N--){
        string Q,A;
        cin >> Q >> A;
        V.push_back({Q,A});
    }
    sort(V.begin(),V.end(),compare);
    while(M--){
        cin >> S;
        for (i=0;i<S.length();i++){
            for (j=0;j<V.size();j++){
                if (S.substr(i,V[j].first.length())==V[j].first){
                    cout << V[j].second;
                    f=false;
                }
            }
        }
        if (f) cout << "-1\n";
        else {
            f=true;
            cout << "\n";
        }
    }
    return 0;
}

이 문제는 N개의 KEY, VALUE로 이루어진 문자열들을 입력받고 M개의 문자열을 입력받으면서 문자열에 KEY가 들어있다면 VALUE를 출력하는 문제다.

N의 값이 작아서 vector pair로 문자열을 저장하고 정렬을 한다.

2중 for문을 돌면서 substr으로 문자열을 비교하면서 KEY가 들어있다면 VALUE를 출력하고 flag로 f를 사용해서 풀었다.

• 시간복잡도 : O( NM * S.length * Q.length )
• 공간복잡도 : O( N * S.length * Q.length )

 

E. 알파벳과 쿼리 (Easy) ( UPSOLVING ) Silver 5

문제 바로가기 (클릭시 이동)

시간 제한 1초 / 메모리 제한 1024 MB

알고리즘 분류 : 구현, 문자열

 

다음 조건들을 만족하는 부분 문자열을 알파벳 묶음이라고 하자.

• 하나의 동일한 알파벳으로만 문자열이 이루어져 있어야 한다.
• 전체 문자열에서 해당 부분 문자열을 포함한 길이가 더 긴 부분 문자열로 알파벳 묶음을 만들 수 있으면 그 부분 문자열은 알파벳 묶음이 아니다.

예를 들어 "AAABBAAC"와 같은 문자열이 있을 때, 알파벳 묶음은 "AAA", "BB", "AA", "C"로 4개다. 위의 문자열에서 "B", "AC"는 조건을 만족하지 않으므로 알파벳 묶음이 아니다.

영어 알파벳 대문자로만 이루어진 길이가 𝑁인 문자열 𝑆=𝑆1𝑆2…𝑆𝑁가 주어질 때, 다음 쿼리를 수행하는 프로그램을 작성하자.

•  1 𝑙 𝑟 : 부분 문자열 𝑆𝑙𝑆𝑙+1…𝑆𝑟에서 알파벳 묶음의 개수를 출력한다.
•  2 𝑙 𝑟: 부분 문자열 𝑆𝑙𝑆𝑙+1…𝑆𝑟의 모든 알파벳을 각각 알파벳 순서로 다음인 알파벳으로 변경한다. 단, Z인 경우 A로 변경한다.

 𝑆𝑙𝑆𝑙+1…𝑆𝑟는 𝑆의 𝑙번째 알파벳부터 𝑟번째 알파벳까지를 모두 순서대로 포함하는 부분 문자열이다.

 

CODE - C++

#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string S;
    short N,Q,m,l,r,i;
    cin >> N >> Q >> S;
    while(Q--){
        cin >> m >> l >> r;
        if (m==1){
            string B=S.substr(l-1,r-l+1);
            B.erase(unique(B.begin(),B.end()),B.end());
            cout << B.length() << "\n";
        }
        else {
            for (i=l-1;i<r;i++){
                if (S[i]=='Z') S[i]='A';
                else ++S[i];
            }
        }
    }
    return 0;
}

이 문제는 정해진 범위에 문자열 덩어리가 몇개인지 구하는 문제다.

문자열 B에 S문자열을 잘라서 넣고 중복제거를 하면 풀린다.

• 시간복잡도 : O( NQ )
• 공간복잡도 : O( N )