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

#2161 : 카드1 (자료구조 Silver 5)

[문제]

 

 

 

[코드 및 결과]

 

#include <iostream>
#include <queue>

using namespace std;

int main() {
    int n;
    queue<int> q;
    
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }
    
    while (q.size() != 1) {
        cout << q.front() << " ";
        q.pop();
        q.push(q.front());
        q.pop();
    }
    
    cout << q.front() << "\n";
    
    return 0;
}

 

 

 

 

 

 

[설명]

카드가 있을 때, 맨 위에 있는 카드를 버리고 그 다음에 있는 카드를 맨 뒤로 넘기는 걸 반복하면서 카드를 버리는데, 이때 마지막에 남는 카드가 뭔지 출력하면 된다.

여기서는 큐를 사용했다.

먼저 n을 입력받고 push로 1부터 n까지의 수를 큐에 저장해준다.

그리고 큐의 크기가 1이 되기 전까지 반복하도록 반복문을 작성해주는데, 맨 앞에 있는 수는 버릴 것이므로 출력해준 후 pop으로 제거하고, 그 후에 맨 앞에있는 수를 맨 뒤로 push한 뒤 pop으로 제거해주는 걸 반복한다.

이렇게 하면 크기가 1이 되었을 때 반복문이 멈추고 마지막에 남은 카드의 수를 출력하면 된다.

 

 

 

 

#2776 : 암기왕 (자료구조 Silver 4)

[문제]

 

 

 

[코드 및 결과]

 

// 실패한 코드
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t, n, m, num;
    vector<int> v;
    
    cin >> t;
    
    for (int i = 1; i <= t; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> num;
            v.push_back(num);
        }
        
        sort(v.begin(), v.end());
        
        cin >> m;
        for (int j = 0; j < m; j++) {
            cin >> num;
            
            cout << binary_search(v.begin(), v.end(), num) << "\n";
        }
    }
    return 0;
}

 

 

// 성공한 코드
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t, n, m;
    int note1[1000001];
    int note2[1000001];
    
    cin >> t;
    
    while (t--) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> note1[j];
        }
        
        sort(note1, note1 + n);
        
        cin >> m;
        for (int j = 0; j < m; j++) {
            cin >> note2[j];
            
            if (binary_search(note1, note1 + n, note2[j])) {
                cout << "1\n";
            }
            else {
                cout << "0\n";
            }
        }
    }
    return 0;
}

 

 

 

 

 

[설명]

왜 저렇게까지 틀린건지.... 이유를 모르겠다....

수첩1에 수를 입력받은 후에 수첩2에 수를 입력받으면서, 그 수들이 수첩1에 존재하는 수인지 확인해서 존재 여부에 따라 1과 0을 출력하는 문제이다.

일단 수첩1에서 키값을 찾아야하는 것이므로 이분탐색을 써보려고 했다. 이번에는 라이브러리 함수를 사용했는데 다음번엔 직접 함수를 구현해보도록 하자.

 

        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> note1[j];
        }
        
        sort(note1, note1 + n);

 

n을 입력받은 후 입력받은 수들을 note1 배열에 저장한 뒤에 이분탐색을 하기 위해 원소들을 오름차순으로 정렬해준다.

 

 

        cin >> m;
        for (int j = 0; j < m; j++) {
            cin >> note2[j];
            
            if (binary_search(note1, note1 + n, note2[j])) {
                cout << "1\n";
            }
            else {
                cout << "0\n";
            }
        }

 

m을 입력받은 후 입력받은 수들을 note2 배열에 저장한다.

이제 note1에 대해서 이분탐색을 진행하는데 binary_search 함수를 사용해서 note1 내에서 note2[j]를 찾도록 했다.

만약 값이 있을 경우에는 1을 출력하고, 없을 경우에는 0을 출력하도록 하면 된다.

 

사실 벡터로도 해보고 집합으로도 해봤는데 마지막에 있는 코드처럼 배열로 바꿔서야 맞았다고 떴다. 방법만 다르고 코드가 돌아가는 구성은 같아서 아직 뭐가 문제인지는 잘 모르겠지만.. 이것도 조금만 더 고민할 필요가 있을 것 같다..

 

 

 

 

#2346 : 풍성 터뜨리기 (자유 Silver 3)

[문제]

 

 

 

[코드 및 결과]

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, num;
    vector<pair<int, int>> v;
    
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> num;
        v.push_back({i, num});
    }
    
    while (!v.empty()) {
        cout << v.front().first << " ";
        
        int temp = v.front().second;
        v.erase(v.begin());
        
        if (v.empty()) {
            cout << "\n";
            return 0;
        }
        
        if (temp > 0) {
            for (int i = 0; i < temp - 1; i++) {
                v.push_back(v.front());
                v.erase(v.begin());
            }
        }
        else {
            for (int i = 0; i < abs(temp); i++) {
                v.insert(v.begin(), v.back());
                v.erase(v.end() - 1);
            }
        }
    }
    
    return 0;
}

 

 

 

 

 

 

[설명]

풍선이 원형으로 놓여있는데 제일 처음 1번 풍선을 터뜨린 후에는 입력받은 수만큼 이동하여 그곳의 풍선을 터뜨려가면서 터진 풍선의 번호를 순서대로 출력하는 문제이다. (양수는 오른쪽, 음수는 왼쪽으로 이동)

n과 num을 입력받아 풍선의 번호와 종이에 적힌 수를 pair로 묶어서 벡터에 저장한다.

그리고 벡터가 완전히 빌 때까지 다음의 내용을 반복한다.

 

 

        cout << v.front().first << " ";
        
        int temp = v.front().second;
        v.erase(v.begin());

맨 앞에 있는 풍선 번호를 출력한다.

임시변수 temp에 해당 풍선을 터뜨리고 나온 종이에 적힌 수 v.front().second를 저장해준다.

맨 앞에 있는 값을 벡터에서 삭제한다.

 

 

        if (v.empty()) {
            cout << "\n";
            return 0;
        }

 

벡터가 비었을 경우 한줄을 띄워주고 프로그램을 종료시킨다.

 

 

        if (temp > 0) {
            for (int i = 0; i < temp - 1; i++) {
                v.push_back(v.front());
                v.erase(v.begin());
            }
        }
        else {
            for (int i = 0; i < abs(temp); i++) {
                v.insert(v.begin(), v.back());
                v.erase(v.end() - 1);
            }
        }

 

이동할 숫자값이 양수이면 temp-1만큼 맨 앞에 있는 수를 뒤에 넣어주고 삭제하는 걸 반복한다.

이동할 숫자값이 음수이면 절댓값 temp만큼 맨 앞에 맨 뒤에 있는 값을 넣어주고 맨 뒤의 값을 삭제하는 걸 반복한다.

 

이런식으로 반복을 했을 때 벡터에 숫자가 딱 하나가 남았을 경우 while문 처음으로 돌아가서 해당 수를 출력하고 삭제된 뒤 if문에 걸려서 프로그램이 종료되도록 해준다.