[BOJ] 2022 SISS 1학기 스터디 - 6주차

#1181 : 단어 정렬 (Class 2 Silver 5)

[문제]

 

 

 

[코드 및 결과]

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(string a, string b){
    if (a.size() == b.size())
        return a < b;
    else
        return a.size() < b.size();
}

int main() {
    int N;
    string str;
    
    cin >> N;
    
    vector<string> v;
    for (int i = 0; i < N; i++) {
        cin >> str;
        v.push_back(str);
    }
    
    sort(v.begin(), v.end(), cmp);
    
    cout << v[0] << "\n";
    for (int i = 1; i < N; i++) {
        if (v[i] == v[i-1]) {
            continue;
        }
        cout << v[i] << "\n";
    }
    
    return 0;
}

 

 

 

 

 

 

[설명]

입력받은 단어들을 길이가 짧은 것부터, 길이가 같으면 사전 순으로 정렬해서 출력하는 문제이다.

정말정말 쉬운 문제였는데..... 인덱스 범위를 간과해서 한참 고민한 문제이다.

 

단어의 개수를 입력 받고 그 개수만큼 단어를 입력받은 뒤 벡터 v에 넣어준다.

sort 함수로 벡터를 정렬하는데, cmp 함수로 cmp 함수로 길이가 같으면 사전 순으로, 아니면 길이 순으로 정렬하도록 했다.

 

아래의 출력 부분에서 OutOfBounds 런타임 에러가 계속 났었다.

같은 단어는 한번만 출력한다는 거에서 v[i]와 v[i-1]이 같으면 넘어가도록 해주었는데, 처음에 for 시작을 i 가 0일때부터 해서 오류가 났었다. 

여러번 수정 끝에 인덱스가 0일 때는 따로 빼주고 1부터 N이 되기 전까지 반복하여 유일성을 판단하고 유일하다면 이를 출력하도록 코드를 바꿔주니 성공할 수 있었다.

 

 

 

#1966 : 프린터 큐 (Class 2 Silver 3)

[문제]

 

 

 

[코드 및 결과]

 

 

#include <iostream>
#include <queue>

using namespace std;

int main() {
    int T, N, M, gravity;
    int index, value;
    
    cin >> T;
    
    for (int t = 1; t <= T; t++) {
        cin >> N >> M;
        
        int cnt = 0;
        queue<pair<int, int>> q;
        priority_queue<int> pq;
        
        for (int i = 0; i < N; i++) {
            cin >> gravity;
            q.push({i, gravity});
            pq.push(gravity);
        }
        
        while (!q.empty()) {
            index = q.front().first;
            value = q.front().second;
            
            q.pop();
            
            if (pq.top() == value) {
                pq.pop();
                cnt++;
                
                if (index == M) {
                    cout << cnt << "\n";
                    break;
                }
                
            }
            else
                q.push({index, value});
            
        }
        
    }
    
    return 0;
}

 

 

 

 

 

 

[설명]

문제가 긴데, 결국 요약하자면 문서마다 중요도가 주어지고, 이 중요도 순서대로 인쇄를 하는데, 입력받은 문서가 몇번째로 출력되는지 그 순서의 번호를 출력하면 되는 문제이다.

출력하면 queue에서 제거하고 출력하는 게 아니라면 queue의 제일 뒤로 보낸다.

 

pair로 문서의 인덱스와 중요도를 함께 큐에 저장하고, 우선순위 큐에는 중요도만 저장해준다.

 

큐가 비어있는 동안 아래의 처리를 반복해준다.

index와 value값에 큐 처음 값들을 저장한 뒤에 큐에서 제거해준다.

우선순위 큐의 제일 위에 있는 값과 value 값을 비교하여 같다면 cnt를 1 증가시키고 이 value 값이 찾고 있는 문서의 번호와 같다면 cnt 값을 출력한다.

위의 상황이 아니라면 그 값을 큐의 맨 뒤에 다시 넣어준다.

 

위의 과정을 통해 나온 cnt 값을 테스트케이스별로 출력해주면 된다.

 

 

 

#11047 : 동전 0 (자유 Silver 3)

[문제]

 

 

 

[코드 및 결과]

 

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, k, num, cnt = 0;
    
    cin >> N >> k;
    
    vector<int> v;
    
    for (int i = 0; i < N; i++) {
        cin >> num;
        v.push_back(num);
    }
    
    int j = N-1;
    while (k > 0) {
        cnt += k / v[j];
        k %= v[j];
        j--;
    }
    
    cout << cnt << "\n";
    
    return 0;
    
}

 

 

 

 

 

 

[설명]

입력받은 돈 액수를 입력받은 동전들로 나타내는데, 이 때 최소로 필요한 동전의 개수를 출력하는 문제이다.

필요한 동전의 개수가 최소이려면 큰 단위로 먼저 값을 맞춰주면 된다.

 

일단 동전의 종류 개수와 돈을 입력 받는다.

그리고 동전의 종류 개수만큼 동전의 단위들을 입력받아 벡터 v에 넣어준다.

 

동전의 종류를 오름차순으로 입력받았으므로 큰 단위부터 보려면 벡터의 제일 뒤 인덱스부터 보면 된다.

 

한 단위에서 필요한 동전의 개수는 돈을 그 단위로 나눴을 때의 몫이므로 그 값을 cnt에 더하고 남은 돈은 나머지 연산으로 업데이트 해주면 된다.

 

위의 과정을 돈이 0원이 될 때까지 한 뒤에 마지막으로 cnt 값을 출력한다.