[S5] 7785. 회사에 있는 사람

https://www.acmicpc.net/problem/7785

7785번: 회사에 있는 사람

문제는 무난하다.

다만 새로운 자료구조를 만나서 작성한다. 

문제를 보고 나는 생각했다.

삽입과 삭제의 비용이 적은 자료구조는 무엇일까?

 

우선 list 삽입의 경우 O(1)이지만 삭제는 O(n)이다.(연결구조이기 때문에 순차접근이다.)

vector의 경우 삽입은 O(1), 삭제는 O(n)이다. (배열형태로 삭제를 하면 뒤에있는 요소를 댕겨줘야 한다)

list의 삽입이 O(1), 삭제가 O(n)이므로 queue와 stack도 동일할 것이다.

가장 친근한 자료구조의 비용이 O(n)으로 꽤 높은 편이다.

 

그렇다면 더 빠르게 할 수 있는 자료구조는 없을까? 

나는 이전에 학교에서 자료구조수업을 들었었기 때문에 생각이 난게 있다.

set과 map이다.

set과 map은 서로 구조가 비슷합니다. 서로 균형 이진 트리로 이루어져 있습니다. 

삽입과 동시에 정렬이 되어 삽입을 하는데 정확한 위치에 삽입하기 위한 비용이 듭니다. 삭제도 해당 원소를 찾아가기 위한 비용이 듭니다.

하지만, 그 비용은 이진트리를 사용하기 때문에 이진트리의 높이와 같습니다. 게다가 균형이진트리를 사용하기 때문에 그 비용은 O(logn)입니다.

즉, 삽입과 삭제가 O(logn)의 비용이 듭니다.

list, vector, stack, queue와 다르게 삽입과 삭제의 비용이 크게 들지 않는 것을 알 수 있습니다.

그렇기 때문에 저는 set과 map을 활용해서 문제를 해결하였습니다.

다른 분들의 코드를 보면 배열을 이용해서 해결을 하여 시간과 메모리를 단축시켰지만, 알고리즘 분류에도 set과 map으로 되어 있어 저는 set과 map을 활용하여 문제를 해결하였습니다.

코드를 확인하기 전 set과 map에 대해 이해를 하고 들어갑시다.

 

https://jhcard.tistory.com/34

[C++] set 라이브러리

https://jhcard.tistory.com/71

[C++] map 라이브러리

다음은 set을 활용하여 문제를 해결한 것이다.

read()와 readInt()함수는 speedIO를 위한 것으로 무시하고 봐도 무방하다.

#include <cstdio>
#include <set>
#include <string>
#include <iostream>
#include <algorithm>

char buf[1<<20];

inline char read(){
    static int idx = 1 << 20, nidx = 1 << 20;
    if(idx == nidx){
        nidx = fread(buf, 1, 1<<20, stdin);
        if(!nidx) return 0;
        idx = 0;
    }
    return buf[idx++];
}

inline std::string readString(){
    std::string tmp;
    char now = read();
    while(now <= 32) now = read();
    while(now >= 65) {
        tmp += now;
        now = read();
    }
    return tmp;
}

int main(void) {
	std::set<std::string, std::greater<std::string>> s;
	int n; scanf("%d", &n);

	std::cin.tie(0); std::ios_base::sync_with_stdio(false);
	std::cout.tie(0);
	std::string name, record;
	while (n--) {
		name = readString();
        record = readString();
		if(record == "enter") s.insert(name);
        else s.erase(name);
	}

	for (auto it = s.begin(); it != s.end(); it++) {
		std::cout << *it << '\n';
	}
}

다음은 map을 활용한 방법이다.

#include <cstdio>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>

char buf[1<<20];

inline char read(){
    static int idx = 1 << 20, nidx = 1 << 20;
    if(idx == nidx){
        nidx = fread(buf, 1, 1<<20, stdin);
        if(!nidx) return 0;
        idx = 0;
    }
    return buf[idx++];
}

inline std::string readString(){
    std::string tmp;
    char now = read();
    while(now <= 32) now = read();
    while(now >= 65) {
        tmp += now;
        now = read();
    }
    return tmp;
}

int main(void) {
	std::map<std::string, int, std::greater<std::string>> m;
	int n; scanf("%d", &n);

	std::cin.tie(0); std::ios_base::sync_with_stdio(false);
	std::cout.tie(0);
	std::string name, record;
	while (n--) {
		name = readString();
        record = readString();
		if(record == "enter") m.insert({name, 1});
        else m.erase(name);
	}

	for (auto it = m.begin(); it != m.end(); it++) {
		std::cout << it->first << '\n';
	}
}

fastIo에 대해서는 다음 글을 참고하라.

https://jhcard.tistory.com/52