[Algo Smash] Week02 - BOJ 17413, 1021, 23843

BOJ 17413번: 단어 뒤집기

1) 접근 방법

문자열이 주어졌을 때, 태그가 없는 단어이면 단어를 뒤집고 태그 안의 내용은 그대로 출력하는 문제이다. 단어를 들어온 순서대로 출력하거나 역순으로 출력해야 한다는 점에서 큐와 스택이 떠올랐다.

1. 문자열 입력

String으로 입력이 들어오는데 문자열 내에 공백이 있기 때문에 cin으로 받기에 부족하다고 생각했다. 그래서 getline(cin, str)을 이용해 엔터가 나오기 전까지의 문자열을 다 받는 메소드를 사용하였다.

2. 태그 안에 있는 문자

'<'를 만나면 태그가 시작된 것으로 보고 다음 태그('>')가 나올 때까지 queue에 넣는다. 또한, isTag라는 flag를 사용해서 태그가 시작되면 flag를 true로 바꿨다. 이는 태크 안에 있는 단어인지 판별하는 기능으로 사용했다. 마지막으로 '>'를 만나면 그동안 큐에 쌓였던 문자를 while문을 통해서 front부터 출력한다.

3. 일반 단어

isTag=False일 때 들어오는 문자로 LIFO 순으로 출력되어야 하기 때문에 stack에 차려대로 push했다. 공백을 만나거나 태그('<')가 시작되면 스택에 쌓인 문자를 top부터 출력했다.

2) 구현 코드

#include <iostream>
#include <string>
#include <stack>
#include <queue>


using namespace std;

int main() {
    string str;
    getline(cin, str);

    bool isTag = 0;
    stack<char> s;
    queue<char> q;

    for (int i = 0; i < str.size(); i++) {
        // 태그 시작
        if (str[i] == '<') {
            // 스택에 남은 일반 단어먼저 출력 
            while (!s.empty()) {
                cout << s.top();
                s.pop();
            }
            isTag = true; 
            q.push(str[i]); 
        } 
        // 태그 끝
        else if (str[i] == '>') {
            isTag = false; 
            q.push(str[i]); 
            // 큐 출력 
            while (!q.empty()) {
                cout << q.front(); 
                q.pop(); 
            }
        }
        else if (isTag) {
            q.push(str[i]); 
        }

        // 공백
        else if (str[i] == ' ') {
            while (!s.empty()) {
                cout << s.top();
                s.pop();
            }
            cout << ' ';
        }
        // 일반 단어 
        else { s.push(str[i]); }
    }

    while (!s.empty()) {
        cout << s.top();
        s.pop();
    }


    return 0;

}

3) 시간 복잡도

입력 문자열의 길이를 N이라고 할 때, for문을 통해 각 문자를 한 번씩 돌기 때문에 시간 복잡도는 O(N)이다.

---

BOJ 1021번: 회전하는 큐

1) 접근 방법

먼저 입력받은 N개의 원소를 큐에 push한다. 그 다음 뽑아내고자 하는 수인 M만큼 for문을 돌려서 연산의 최솟값을 누적한다.

연산의 최솟값을 찾기 위해서 find_min(int num, queue<int>& q)라는 함수를 따로 분리하였다. 이 함수에서는 찾고자 하는 원소 num와 q.front()가 일치할 때까지 큐를 왼쪽으로 회전시키면 횟수를 left에 카운트한다.

오른쪽으로 회전하는 경우는 큐의 전체 사이즈에서 left를 뺀 수이기 때문에 최종적으로 left count와 right count를 비교하여 더 작은 수를 return하도록 했다.

2) 구현 코드

#include <iostream>
#include <queue>

using namespace std;

int find_min(int num, queue<int>& q) {
    int left = 0; // 왼쪽으로 회전하는 경우의 count 
    // right로 회전하는 경우는 전체 큐 사이즈에서 왼쪽에서 회전하는 경우를 빼면 됨 
    int size = q.size();

    while (q.front() != num) {
        ++left;
        int tmp = q.front();
        q.pop();
        q.push(tmp);
    }

    q.pop();  // num 뽑기
    return min(left, size - left);
}

int main() {
    int N, M;
    cin >> N >> M;

    // 큐에 int 매핑하기 
    queue<int> q;
    for (int i = 0; i < N; i++) {
        q.push(i + 1);
    }

    // find_min 함수를 통해 찾은 최소값을 sum 더하면서 반복문 돌기 
    int sum = 0;
    for (int i = 0; i < M; i++) {
        int num;
        cin >> num;
        sum += find_min(num, q);
    }

    cout << sum << endl;
    return 0;
}

3) 시간 복잡도

입력받는 뽑아내고자 하는 원소의 개수가 M개 일 때, main문에서 M번 반복하고 find_min 내부에서 최악의 경우 큐의 전체 원소 N개를 순회하기 때문에 전체 시간 복잡도는 O(N*M)이다.

---

BOJ 23843번: 콘센트

1) 접근 방법

충전 시간이 긴 시간부터 전자기기부터 충전해야 나중에 시간이 급격히 늘어나는 상황을 막을 수 있다. 따라서 전자기기의 충전시간을 배열에 저장하고, 내림차순으로 sort를 했다.

그리고 이번 문제를 풀기 위해 우선순위 큐를 사용했다. 충전시간이 가장 큰 전자기기부터 충전을 시작하고 충전이 빨리 끝나는 콘센트에 다음 전자기기르 충전해야 하기 때문에 루트가 최소값이 큐를 사용하였다. (선언방법: priority_queue<int, vector<int>, greater<int>> pq;)

전자기기의를 하나씩 꺼내서 루트(최솟값)에 충전 시간을 누적해 다시 push하는 방법으로 반복문을 돌았다.

마지막으로는 큐의 최대값을 찾아야 했는데, 우선순위 큐에는 .back()을 지원하지 않아서 반복문을 돌면서 가장 top의 값을 max 변수에 저장하고 우선순위 큐를 pop하는 형식으로 최대값을 구하였다.

2) 구현 방법

#include <iostream>
#include <queue>
#include <algorithm> // sort()

using namespace std; 


int main() {
    int N, M; 
    int arr[10000]; 

    cin >> N >> M; 
    for (int i = 0; i < N; i++) {
        cin >> arr[i]; 
    }

    sort(arr, arr + N, greater<int>()); 

    /* 콘센트 M개를 0으로 초기화하기 */
    // 루트가 최소값인 우선순위 큐
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < M; i++) pq.push(0); 

    // 각 전자기기를 루트 큐에 누적 
    for (int i = 0; i < N; i++) {
        // 가장 최소값을 tmp에 저장했다가 pop하고 arr[i]와 더해서 다시 push
        int tmp = pq.top();
        pq.pop(); 
        pq.push(arr[i] + tmp);
    }

    // 최댓값 찾기 
    int max_time = 0; 
    while (!pq.empty()) {
        max_time = pq.top(); // 가장 마지막에 나오는 값이 최대값
        pq.pop(); 
    }
    cout << max_time << endl; 

    return 0; 
}

3) 시간 복잡도

• arr의 배열을 정렬하는 시간 복잡도가 O(N log N)
• 우선순위 큐를 초기화 할 때: M번 삽입, 삽입 때마다 조정(logM) = O(M log M)
• 전자기기를 큐에 누적: 전자기기 N번만큼 push(log M) = O(N log M)
• 최댓값 찾기: O(M log M)

항상 M <= N이므로 최종 시간 복잡도는 O(N log N)이다.