백준 2606, 7785
1) 백준 2606 : 바이러스 (https://www.acmicpc.net/problem/2606)
전형적인 DFS문제 (BFS가 더 빠르다고는 하던거 같은데 아무튼 이게 손에 익어서)
1과 연결된 노드가 몇개인지 거르면 끗.
https://github.com/JangJuMan/2019-winter-PS/11_2606.cpp
2) 백준 7785 : 회사에 있는 사람 (https://www.acmicpc.net/problem/7785)
처음에 회사에 들어오고 나가고의 활동마다 업데이트를 하니 당연히 시간초과..
그래서 생각한 것이 벡터에 모든 기록을 다 때려박아넣고
sort(begin, end, grater)로 거꾸로 정렬한다.
일단은 회사에 들어와야 나갈 수 있다고 생각해서 짝수번 이름이 나온다면 회사에 없고, 홀수번 나온다면 회사에 있다고 판단함.
(그래서 사실 두번째 인자인 enter랑 leave가 안쓰임...)
이전 것이랑 비교해서 현재꺼랑 같으면 pop을 하는 식으로 result 벡터에 최종결과값을 저장.
예를들어
aaa enter
bbb enter
ccc enter
ddd enter
aaa leave
bbb leave
ddd leave
bbb enter
이런식이면 정렬후 결과는
aaa
aaa
bbb
bbb
bbb
ccc
ddd
ddd
이런식이 된다.
따라서 a는 집갔고 b는 남았고, c도 남았고 d는 집갔다.
는 결론이 나오는것.
- 원래 문제 의도는 map을 사용하는 것.
map.count(s) 하면 map에 s가 들어잇나를 확인 가능.
그래서 이것으로 판별 쉽게 함. (왜 빠른지는 나도 잘 모르겠네)
두 버전 다 코드에 써봣음
https://github.com/JangJuMan/2019-winter-PS/blob/master/11_7785.cpp
끗
