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

 

#1269 : 대칭 차집합 (자료구조 Silver 4)

[문제]

 

 

 

[코드 및 결과]

 

#include <iostream>
#include <map>

using namespace std;

int main() {
    int N, M, num;
    map<int, bool> m;
    
    cin >> N >> M;
    
    for (int i = 0; i < N + M; i++) {
        cin >> num;
        
        if (m[num] == true) {
            m.erase(num);
        }
        else {
            m[num] = true;
        }
    }
    
    cout << m.size() << "\n";
    
    return 0;
}

 

 

 

 

 

 

[설명]

처음에는 집합으로 하려다가 두가지 값을 저장하기 좋은 map이 더 나을 것 같아서 map을 이용하여 풀었다.

두 집합의 원소들을 입력 받아서 대칭 차집합을 구하는 문제이다.

 

    for (int i = 0; i < N + M; i++) {
        cin >> num;
        
        if (m[num] == true) {
            m.erase(num);
        }
        else {
            m[num] = true;
        }

 

N과 M을 입력받아 N+M만큼 반복하는데, 수를 입력 받을 때마다 이 수가 map에 없으면 m[num]을 true로 바꿔주고, 이미 그 값이 true라면 map에서 그 수를 지워준다.

 

그 과정이 다 끝나면 남은 원소들만 출력해주면 된다.

 

 

 

 

#15650 : M과 N (2) (자료구조 Silver 3)

[문제]

 

 

 

[코드 및 결과]

 

#include <iostream>

using namespace std;

int N, M;
int arr[10];
bool visited[10];

void dfs(int num, int idx) {
    if (idx == M) {
        for (int i = 0; i < M; i++) {
            cout << arr[i] << " ";
        }
        cout << "\n";
    }
    
    for (int i = num; i <= N; ++i) {
        if (!visited[i]) {
            visited[i] = true;
            arr[idx] = i;
            dfs(i + 1, idx + 1);
            visited[i] = false;
        }
    }
}

int main() {
    cin >> N >> M;
    
    dfs(1, 0);
    
    return 0;
}

 

 

 

 

 

 

[설명]

N과 M을 입력 받아 길이가 M인 수열을 출력하는데, 조합이라고 생각하면 편하다.

중복이 없어야하므로 이미 거쳐간 수에 대한 처리가 필요하기 때문에 dfs를 사용해보기로 했다.

이전에 N과 M(1) 문제에서 작성했던 코드랑 별반 다를 게 없는 것 같아서 가져와서 조금 수정했다.

 

void dfs(int num, int idx) {
    if (idx == M) {
        for (int i = 0; i < M; i++) {
            cout << arr[i] << " ";
        }
        cout << "\n";
    }
    
    for (int i = num; i <= N; ++i) {
        if (!visited[i]) {
            visited[i] = true;
            arr[idx] = i;
            dfs(i + 1, idx + 1);
            visited[i] = false;
        }
    }
}

 

이 문제에서는 num, idx 라는 인자를 두개 전달하게 했다.

idx가 M과 같다면 배열에 저장된 값을 쭉 출력하도록 했다.

 

아래는 수열을 구하는 과정인데, 만약 i를 방문하지 않았다면 true로 상태를 바꿔주고 arr[idx]값을 i로 바꿔준 뒤에 재귀함수로 다시 dfs 함수로 들어가도록 했다. 이를 거친 후에는 다시 상태를 false로 바꿔주었다.

 

이렇게 끝까지 다 돌면 우리가 원하는 중복 없는 수열을 뽑아서 출력해낼 수 있게 된다.

 

 

 

#13417 : 카드 문자열 (자유 Silver 4)

[문제]

 

 

 

[코드 및 결과]

 

#include <iostream>
#include <deque>

using namespace std;

int main() {
    int T, N;
    char c;
    
    cin >> T;
    
    for (int i = 1; i <= T; i++) {
        deque<char> dq;
        cin >> N;
        
        for (int j = 0; j < N; j++) {
            cin >> c;
            
            if (j == 0) {
                dq.push_back(c);
            }
            else if (c <= (dq.front())) {
                dq.push_front(c);
            }
            else {
                dq.push_back(c);
            }
        }
        
        for (int j = 0; j < dq.size(); j++) {
            cout << dq[j];
        }
        
        cout << "\n";
    }
    
    return 0;
}

 

 

 

 

 

 

[설명]

N장의 카드 중에서 맨 앞에 있는 카드를 가져오고, 그 후부터는 맨 앞에 오는 카드들을 가져온 카드 맨 앞이나 맨 뒤에 붙여서 문자열을 만드는데, 그 중에서 사전 순으로 가장 앞에 오는 문자열을 구하면 된다.

 

앞이나 뒤에 삽입하기 좋게 여기서는 deque를 사용했다.

 

       for (int j = 0; j < N; j++) {
            cin >> c;
            
            if (j == 0) {
                dq.push_back(c);
            }
            else if (c <= (dq.front())) {
                dq.push_front(c);
            }
            else {
                dq.push_back(c);
            }
        }

 

반복문으로 문자를 입력받으면서 처리를 하는데, 사전 순으로 가장 앞에 오려면 카드더미에서 가져오는 카드가 현재 내 앞에 있는 카드보다 사전순으로 빠르면 앞에 두고, 느리면 뒤로 두는 식으로 처리를 해주면 된다.

 

이렇게 해서 만들어진 deque를 최종적으로 출력해주면 된다.