[Algo Smash] Week01 - BOJ 13335, 5052, 1759

Ⅰ. 13335: 트럭

1. 자료구조

친절하게 그림까지 그려줘서,, 이 그림을 보자마자 큐가 생각났다!

(자료구조를 배운 것이 2년 전이고 그동안 백준도 안 풀어서 algo-smach를 하면서 기초적인 내용도 정리할 예정이다.)
Queue(큐)란 먼저 들어간 데이터가 먼저 나오는 방식의 선형 자료구조이다.
간단하게 queue를 구현한다면 다음과 같이 구현할 수 있을 것 같다.

struct Queue {
    int data[2000]; 
    int front = 0; 
    int rear = 0; 

    void push(int val) {
        data[rear++] = val;
    }

    void pop() {
        front++;
    }

    int getFront() {
        return data[front];
    }

    bool isEmpty() {
        return front == rear;
    }

    int size() {
        return rear - front;
    }
};

이건 간단한 버전이고 linked list로 구현할 수도 있다.

근데 C++에는 Queue STL이 있기 때문에 그걸 이용하기로 결정했다.

include <queue>

queue<int> que;
que.push(i);
que.pop();
...

 

2. 접근 방법

그래서 queue를 사용할건데, 다리의 길이를 어떻게 어떻게 표현할 것인가? → 큐의 크기를 다리 길이만큼의 제한하면 된다!

이런 느낌으로 문제를 풀어볼 예정이다. 큐에 한 트럭이 진입할 때마다 최대 하중보을 초과하는지 체크하고, 만약 최대하중보다 많이 나간다면 큐에는 0을 넣는다.

그리고 마지막 트럭 다리에 올라와도 빠져나가는데 시간이 걸리기 때문에 다리의 길이만큼 0을 더 넣어준다.

 

3. 구현 코드

#include <iostream>
#include <queue>

using namespace std; 

int main() {
    int n, w, L; // w=다리 길이, L=최대 하중
    int truck[1000];

    cin >> n >> w >> L;
    for (int i = 0; i < n; i++) cin >> truck[i];

    queue<int> que;

    int count = 0; // 최단 시간
    int current_weight = 0; // 현재 다리에 있는 트럭 무게의 합
    int ti = 0; // truck array 접근하는 index 

    // 일단 que의 원소들을 다 0으로 초기화
    for (int i = 0; i < w; i++) que.push(0); 

    while (ti < n) {
        count++; 

        // 다리의 앞에서 원소 하나씩 빠지기 
        current_weight -= que.front(); 
        que.pop(); 

        // 다음 트럭 진입하기
        if (current_weight + truck[ti] <= L) {
            que.push(truck[ti]); 
            current_weight += truck[ti];
            ti++;
        }
        else { // 최대하중 이상으로 다음 트럭 진입할 수 없는 경우 
            que.push(0); 
        }
    }

    // 마지막 트럭이 다리를 다 빠져나오는 시간
    count += w; // 다리 길이 만큼 더하기 

    cout << count << endl; 
    return 0; 
}

---

 

Ⅱ. 1759

1. 접근 방법

처음에는 단순하게 for문을 중첩하는 생각을 해보았으나, L의 최대인 15개를 for문으로는 절대 못 찾을 것 같았다.

그래서 이 문제는 가능한 암호를 dfs로 깊게 탐색하고 조건에 맞는지 판단하는 식으로 풀어야 한다고 생각했다.

일단 사용자에게 입력을 받으면서 입력을 알파벳순으로 정렬해두고, 암호를 뽑을 때 항상 현재 인덱스보다 뒤의 것을 선택하면 된다고 생각했다.

2. 구현 코드

#include <iostream>
#include <algorithm>

using namespace std;

int L, C; // 3 ≤ L ≤ C ≤ 15
char arr[20]; //　입력받는 알파벳들 
char pw[20]; 

bool check() {
    int vowel = 0; 
    int consonant = 0; 
    for (int i = 0; i < L; i++) {
        if (pw[i] == 'a' || pw[i] == 'e' || pw[i] == 'i' || pw[i] == 'o' || pw[i] == 'u') vowel++;
        else consonant++;
    }
    if (vowel >= 1 && consonant >= 2) return 1;
    else return 0; 
}

void dfs(int index, int depth) {
    if (depth == L) {
        if (check()) {
            for (int i = 0; i < L; i++) cout << pw[i];
            cout << endl;
        }
        return;
    }
    for (int i = index; i < C; i++) { 
        // arr에 담긴 알파벳을 하나씩 꺼내와서 암호의 depth에 넣음 -> 오름차순 보장
        pw[depth] = arr[i]; 
        dfs(i + 1, depth + 1); 
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> L >> C; 

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

    sort(arr, arr + C); 

    dfs(0, 0); 

    return 0; 

}

---

 

Ⅲ. 5052

1. 첫 번째 시도

백터와 string STL을 사용하여 find 메소드를 사용하는 방식의 알고리즘이 먼저 떠올랐다.
그래서 처음에 느낌이 따라 작성한 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <vector>

using namespace std; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t, n; 
    bool flag = 1; 
    string input_string ;
    vector<string> numbers = {}; 

    cin >> t; 

    for (int i = 0; i < t; i++) {
        cin >> n; 
        for (int j = 0; j < n; j++) {
            cin >> input_string;

            // 일관성 없는 전화번호가 있는 체크 
            vector<string>::iterator itor = numbers.begin();
            for (; itor != numbers.end(); itor++) {

                // 지금 입력받는 전번이 벡터 안에 있는 string과 일치하는지 확인
                // str.find("문자열") -> 문자열이 포함된 부분의 첫번째 index반환
                // 반환받은 인덱스가 0이라면 다른 번호가 자기의 접두어인 거임
                if (input_string.find(*itor) == 0) { 
                    flag = 0; 
                }
                // 반대로 원래 있던 전번에서 input_string이 접두어로 있는지 확인
                if ((*itor).find(input_string) == 0) {
                    flag = 0; 
                }
            }

            // 그리고 현재 번호를 벡터에 push 
            numbers.push_back(input_string);
        }

        // 출력 
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
        flag = 1;

        // 벡터 초기화
        numbers.clear(); 
    }

    return 0; 
}

n개의 전화번호를 입력받으면서 `.find(*itor)`를 사용해서 벡터 내 문자열과 비교하고, 반환된 인덱스가 0인지 판단하여 접두어인지 확인하고자 했다.

그리고 현재 전화번호에서만 접두어를 체크하면 벡터에 있는 전화번호 중 현재 전화번호를 접두어로 하는 전번이 확인을 할 수 없기 때문에 (*itor).find(input_string) == 0로 양방향 체크를 하였다.

하하.... 하지만 바로 시간초과 나버렸다.😭 아마도 위의 코드는 n번의 for문을 돌면서 벡터에 있는 전화번호들도 확인하기 때문에 시간복잡도가 O(n^2)이기 때문이다.

 

2. 두 번째 시도

💡 자! 정렬을 합시다!

그렇다ㅎㅎ 정렬을 하면 전화번호들도 순서대로 정렬되고 같은 접두어가 있다면 길이가 짧은 전번부터 정렬되기 때문에 시간복잡도를 O(n log n)로 줄일 수 있다.

그래서 완성된 코드는 다음과 같다!

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

using namespace std; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t, n; 
    bool flag = 1; 
    string input_string ;
    vector<string> numbers = {}; 

    cin >> t; 

    for (int i = 0; i < t; i++) {
        cin >> n; 
        for (int j = 0; j < n; j++) {
            cin >> input_string;
            numbers.push_back(input_string);
        }

        // 정렬 -> 정렬하면 순서대로 + 길이가 낮은 순으로 정렬됨
        // 인전합 2개의 전번들만 비교하면 접두어인지 찾을 수 있음 
        sort(numbers.begin(), numbers.end()); 

        for (int j = 0; j < n - 1; j++) {
            if (numbers[j + 1].find(numbers[j]) == 0) {
                flag = 0; 
                break; 
            }
        }

        // 출력 
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
        flag = 1;

        // 벡터 초기화
        numbers.clear(); 
    }

    return 0; 
}