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

#1417 : 국회의원 선거 (자료구조 Silver 5)

[문제]

 

 

 

[코드 및 결과]

 

 

#include <iostream>
#include <queue>

using namespace std;

int main() {
    int n, m, candidate, ans = 0, temp;
    priority_queue<int> pq;
    
    cin >> n >> m;
    
    for (int i = 0; i < n-1; i++) {
        cin >> candidate;
        pq.push(candidate);
    }
    
    while (!pq.empty() && (pq.top() >= m)) {
        temp = pq.top();
        pq.pop();
        ans++;
        m++;
        pq.push(temp - 1);
    }
    
    cout << ans << "\n";
    
    return 0;
}

 

 

 

 

 

 

[설명]

다솜이라는 사람이 국회의원 선거에 출마한다고 한다. 자신이 당선되고자 다른 후보들을 찍으려는 사람들을 매수하는데, 매수해야하는 사람의 최솟값을 구하면 되는 문제이다.

먼저 출마하는 사람 n, 다솜이를 찍을 사람 수 m, 다른 후보들을 찍을 사람 수 candidate, 답 ans, 임시값 temp를 선언한다.

여기서는 우선순위 큐를 사용하여 넣어주는 수들을 제일 큰수부터 내림차순으로 자동 정렬하도록 했다.

n, m, candidate를 입력 받고, 입력받은 candidate는 우선순위 큐 pq에 저장해준다.

이제 반복문을 돌면서 매수해야하는 사람의 최솟값을 구할 예정인데, 이는 pq가 비어있지 않고, 제일 위의 값이 m보다 클 동안 반복하도록 해준다.

pq.top, 그러니까 다른 후보들 중에 가장 많은 득표수를 찾아 이 수가 다솜이의 득표수 m 보다 클 경우 매수하도록 해준다.

이 과정을 반복하다보면 다솜이의 득표수가 가장 많게 될 때가 오고 이때 while문을 빠져나가 ans를 출력하면 된다.

 

 

 

 

#7785 : 회사에 있는 사람 (자료구조 Silver 5)

[문제]

 

 

[코드 및 결과]

 

 

#include <iostream>
#include <set>

using namespace std;

int main() {
    int n;
    string name, inout;
    set<string> s;
    
    cin >> n;
    
    while (n--) {
        cin >> name >> inout;
        
        if (inout == "enter") {
            s.insert(name);
        }
        else if (inout == "leave") {
            s.erase(name);
        }
        
    }
    
    for (auto i = s.rbegin(); i != s.rend(); ++i) {
        cout << *i << "\n";
    }
    
    return 0;
}

 

 

 

 

 

 

[설명]

사람들이 회사에 출입하고 나갔는지를 기록한 내용을 바탕으로 현재 회사에 있는 사람들을 모두 구하면 되는 문제이다.

로그에 기록된 출입 기록 수 n, 이름 name, 입출입상태를 나타내는 inout을 선언한다.

여기서는 집합 set을 사용하여 같은 원소는 존재하지 않도록 하고 들어오는 값들을 자동 오름차순으로 정렬하도록 했다.

먼저 로그 개수를 입력 받고 그 수만큼 name과 inout을 입력받도록 한다.

이때, enter일 경우 집합 s에 해당하는 이름을 넣어주고, leave인 경우 그 이름을 빼주는 식으로 출입 상태 처리를 해준다.

이렇게 되면 마지막에 집합에 이름이 저장된 사람들은 회사에 있는 사람들이 되는 것이다.

마지막으로 집합을 돌면서 저장된 이름들을 출력하는데, rbegin(), rend()를 사용하여 사전 역순으로 출력한다.

 

 

 

 

#2960 : 에라토스테네스의 체 (자유 Silver 4)

[문제]

 

 

 

[코드 및 결과]

 

 

#include <iostream>

using namespace std;

int main() {
    int n, k, cnt = 0;
    bool arr[1001];
    
    cin >> n >> k;
    
    for (int i = 2; i <= n; i++) {
        arr[i] = true;
    }
    
    for (int i = 2; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            if (arr[j] != false) {
                arr[j] = false;
                cnt++;
                
                if (cnt == k) {
                    cout << j << "\n";
                }
            }
            
        }
    }
    
    return 0;
}

 

 

 

 

 

 

[설명]

에라토스테네스의 체는 n보다 작거나 같은 모든 소수를 찾는 알고리즘이라고 한다. 알고리즘에 대한 자세한 설명은 문제에 적혀있으니 설명은 넘어간다.

먼저 입력받을 n, 지울 숫자가 몇번째인지 나타내는 k, 카운트 수 cnt, 초기 배열 arr을 선언한다.

먼저 2부터 n까지 인덱스를 가진 배열의 상태를 true로 잡아준다.

반복문을 돌면서 이제 수들을 지워나가면 되는데, 배수를 찾아가는건 j에 i를 더해주면서 찾아가도록 했고, 지워질 수는 false로 상태를 바꿔주었다.

이런식으로 수를 지워나가면서 cnt가 k와 같아진다면 그 때 지운 수를 출력하도록 한다.