chaetudy

(5/19 - O)

https://school.programmers.co.kr/learn/courses/30/lessons/42586

구현

Queue를 이용하여 풀이.

queue는 이터레이터가 없으므로 순회 X, 정 탐색하고 싶다면 Deque를 사용할 것.

Queue

https://chae-d-2.tistory.com/153?category=1098972 

코드

// 각 배포마다 몇 개의 기능이 배포되는가
// 배포는 하루에 한 번만, 하루의 끝에 이루어짐
// 예를 들어 진도율 95%이고 속도가 하루에 4인 작업은 배포가 2일 뒤에 이루어짐

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int sz = progresses.size();
    queue<pair<int, int>> q;
    for (int i = 0; i < sz; i++) {
        q.push({ progresses[i], speeds[i] });
    }

    int day_cnt = 0;
    int out = 0;
    while (!q.empty()) {
		day_cnt++;
		int jindo = q.front().first + (q.front().second * day_cnt);
		if (jindo >= 100) {
			q.pop();
            out++;
			while (!q.empty()) {
				jindo = q.front().first + (q.front().second * day_cnt);
				if (jindo >= 100) {
					q.pop();
					out++;
				}
				else {
					break;
				}
			}
            answer.push_back(out);
            out = 0;
		}

	}


    return answer;
}

int main()
{
    vector<int> p = { 95, 90, 99, 99, 80, 99 };
    vector<int> s = { 1, 1, 1, 1, 1, 1};
    solution(p, s);
}

(5/18) - X 어엄청 오래 걸려서 풀었음

(5/19) - O

https://school.programmers.co.kr/learn/courses/30/lessons/42577

방법 1. binary_search

phone_book의 원소를 꺼내서, 그 원소를 substr()로 한 글자씩 조각내면서 (1234라면 1, 12, 123으로. 중복된 원소가 없다고 했으니 1234는 제외), Binary_Search()로 phone_book에 존재하는지 검사한다. phone_book의 원소 처음부터 끝까지 이렇게 검사한다.

bool solution(vector<string> phone_book) {
    bool answer = true;
    sort(phone_book.begin(), phone_book.end());
    for (string& s : phone_book) {
        int st_len = s.length();
        string des = s;
        for (int i = 1; i < st_len; i++) {
            // des의 접두어 찾기
            if (binary_search(phone_book.begin(), phone_book.end(), des.substr(0, i))) {
                return false;
            }
        }
    }

    return answer;
}

방법 2. map::find

vector에 담겨 있던 phone_book을 map 컨테이너에 옮긴 다음, 1번에서 했던 것처럼 조각 낸 string들을 map::find를 통해서 찾는다.

bool solution(vector<string> phone_book) {
    bool answer = true;
    map<string, int> m;

    for (string& s : phone_book) {
        m.insert({ s, 0 });
    }

    for (auto& p : m) {
        int len = p.first.length();
        for (int i = 1; i < len; i++) {
            if (m.find(p.first.substr(0, i)) != m.end()) {
                return false;
            }
        }
    }

    return answer;
}

결론

모든 테스트 케이스에서 속도와 메모리 차이가 크지 않았다. 그런데 효율성 테스트 3, 4번에서 map::find가 속도와 메모리 측면에서 조금 더 비효율적이었다.

https://school.programmers.co.kr/learn/courses/30/lessons/42748

코드

// 배열 arr의 i부터 j까지 자르고 정렬했을 때 k번째에 있는 수 구하기

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    for (auto& i : commands) {
        vector<int> v;
        for (int j = i[0] - 1; j < i[1]; j++) {
            v.push_back(array[j]);
        }
        sort(v.begin(), v.end());
        answer.push_back(v[i[2] - 1]);
    }
   

    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/42576

코드

22.04.30 첫 번째 풀이 - map 이용

#include <string>
#include <vector>
#include <map>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    map<string, int> m;
    for (auto& i : participant) {
        auto iter = m.find(i);
        if (iter == m.end()) {
            pair<string, int> p(i, 1);
            m.insert(p);
        }
        else {
            iter->second++;
        }
    }
    for (auto& i : completion) {
        map<string, int>::iterator iter = m.find(i);
        (iter->second)--;
    }
    string answer = "";
    for (auto& i : m) {
        if (i.second == 1) {
            answer = i.first;
        }
    }
    return answer;
}

22.04.30 두 번째 풀이 - unordered_map 이용

* map과 unordered_map에 대해서는 다음 글 참고.

https://chae-d-2.tistory.com/190