[백준 | BOJ] 가희와 함께 하는 1회 코딩 테스트 후기

요즘 백준에서 문제를 좀 풀고 있다. 어려운 고급알고리즘보다는 대회나 코딩테스트에서 자주 보이는 알고리즘 위주로 연습하려고 한다. Codeforces의 Round나, 백준의 대회나, Atcoder의 Contest 모두 참 좋지만, 신분이 군인인지라 쉽게 응시하지 못하고 있다.

 

가희와 함께 하는 1회 코딩 테스트

오늘 괜찮은 시간대에 대회가 열려서 참가하게 됐다. 문제들은 재밌었고, 다양한 알고리즘들이 문제셋에 녹아있어서 이렇게저렇게 풀어보기도 했다. 공지사항에서 미리 "빠른 입출력"을 사용하라고 조언했었는데, 꽤 테스트케이스들이 무거운 모양이다. 파이썬으로 힘겹게 돌아갔다.

 

대회 결과, 스코어보드는 프리징돼서 정확한 등수는 확인하지 못하지만, 10-12등정도 한 것 같다 !

 

저번 숙명여대 SMUPC에서는 2문제만 풀고 대회를 마무리했었는데, 이번 대회에서는 8문제 중에서 6문제를 해결해서 뿌듯했다.

 

 

---

 

1. 가희야 거기서 자는 거 아니야

단순 브루트포스 문제였는데,, 이상하게 풀어서 처음에 런타임 에러 먹고 2번으로 넘어갔었다.

정신차리고 다시 와서 보니 전체 $P$ 개수를 세서 $R_p * S_p$와 같은지만 확인하면 됐다.

 

2. 가희의 고구마 먹방

범위가 작으면 일단 브루트포스부터 생각하게 된다.  $T <= 10$ 이니까 열칸 내려가는 3차원 visited 배열을 처음에 만들고 BFS를 돌렸었는데, 직접 테스트케이스를 만드는 족족 틀려버려서 엎었다. 고구마가 있는 곳을 다른 루트로 방문했을 때도 있어야 하는데, 그 조건을 해결하기에는 BFS로는 안 됐었다.

DFS로 갈아탔다. visited도 안 만들고 상하좌우와 가만히 있는 경우까지 총 5가지 경우를 완전탐색했다. 시간복잡도 $O(5^{10})$이 된다.

$T = 10$ 인 경우 값을 갱신하게 하니 꾸역꾸역 돌아갔다. 재귀로 짜니 파이썬에서는 시간초과, PyPy에서는 메모리초과를 따냈다. 스택으로 하니 PyPy에서 통과.

 

3. 가희와 프로세스 1

한 프로세스가 실행되는 동안 그 프로세스를 제외한 전부의 Priority가 증가한다는 이야기는, 상대적으로 봤을 때 실행되는 프로세스의 Priority가 감소한다는 것과 같은 의미이다. 그렇게 하면 뽑아놓은 것 하나만 감소시키고 다시 집어넣으면 되니까, $O(lgN)$의 왕자 우선순위 큐를 이용한다.

정해진 시간만큼 돌면서, 우선순위 큐에서 뽑고, 뽑은 프로세스의 시간과 우선순위를 감소시킨 뒤 다시 큐에 집어넣는다. (프로세스가 종료되면 큐에 넣지 않는다) 뽑고 넣는데 $O(lgN)$, 최대 T번 뽑고 넣으니까 전체 시간복잡도는 $O(TlgN)$ 이다.

 

4. 가희와 로그 파일

지옥의 파싱 문제였다.. 2020-05-23 21:00:00#1 같은 형태로 입력이 들어오니 어질어질하다.

구분자 세 개 모두 replace 로 공백으로 바꾼 뒤에 split 해서 datetime 에 넣어버렸다. datetime 클래스는 대소구분이 가능하고, 주어지는 로그 목록은 모두 비내림차순이므로 이분탐색도 사용할 수 있었다.

우선순위에 따라 1~6까지의 배열을 만들어 각 우선순위의 로그를 저장하고, 이분탐색을 주어진 수 ~ 6까지 돌렸다. 돌리면서 범위에 해당하는 로그가 있으면 +1.

생각보다 시간복잡도가 안 나오는 것 같은데, stdin.readline 만 써서 그런지 모르겠다. 문제 열리면 stdout.write 도 써서 시간이 얼마나 차이나는지 봐야겠다.

 

5. 가희와 자원 놀이

단순구현 문제였다. 5번에 구현 문제가 있어서 오잉? 했었다.

보드 위의 20억개의 카드를 하나하나 저장할 수는 없는 노릇이니 사용한 카드를 딕셔너리에 저장하고 삭제했다.

next , release , acquire 와 같은 세 가지 방법으로 자신의 턴을 지낼 수 있다.

next 의 경우는 그냥 넘겨주면 된다.

release 도 딕셔너리에서 빼버리면 된다.

acquire 가 문제였는데, 보드상에 $N$ 이 없을 경우 다음 턴에도 강제로 사용하게 된다는 점이었다. 길이 $N$의 배열을 만들어서 가져오지 못했다면 저장해서, 다음 턴에 다시 시도하는 방법으로 해결했다. 카드의 id 를 출력해야 하니 그것도 같이 저장해줬다.

 

 

6. 가희와 읽기 쓰기 놀이

문제 제한을 보고 너무 작아서 오잉2? 했다. 이번에도 완전탐색 문제였다. 문제를 이해하는 데 꽤 걸렸다. 5번하고 6번 문제에서 지문을 읽고 예제 입출력과 비교하는데만 시간을 많이 썼었다.

$N$ 명의 사람들과 $C$ 개의 카드가 있다. 턴마다 사람들은 문자열에 행동을 한다.

한 사람이 여러 장의 카드를 들고있을 수 있다. 하지만 카드는 순서대로 낸다. 예를 들어 2, 5, 6번 카드를 들고 있었다면 행동은 2 - 5 - 6 순서가 돼야 한다. 턴은 조작될 수 있는 항목이지만 사람들의 턴이 정해지면 행동은 고정된다.

만들 수 있는 문자열의 목록들을 중복없이 오름차순으로 출력하는 문제다. A가 1, 2번 카드를 들고 있고, B가 3번 카드를 들고 있다면, 할 수 있는 행동은 AAB, ABA, BAA가 된다. 카드는 순서대로 내니까, 각 행동에서의 앞 A는 1번 카드의 행동을, 뒤 A는 2번 카드의 행동을 할 것이다.

문제를 이해할 수 있게 쪼갰으니 구현을 했다. 들고있는 카드 수만큼 플레이어 숫자를 넣어주고, 넣어둔 리스트(제출한 코드에는 str형식으로 했다. python에서는 str도 iterable하다)의 순열을 모두 구했다. 중복되는 순열은 set으로 배제했는데, 다른 방법이 있었을 것 같다.

플레이어마다 몇 번째 카드를 써야하는지를 기록한 배열과, 카드더미를 덱(deque)으로 구현했다. ADD/DEL은 문제에서 주어진 대로.

처음에는 중복을 생각못해 틀렸다. 지문을 제대로 이해했다고 생각했는데, 구현하느라 앞에서 중요하다고 생각했던 걸 놓쳤다.

개인적으로 제일 재밌게 풀었던 문제다. 문자열 + 순열 + 완전탐색 + 어느정도의 구현이 잘 버무려진 것 같다.

 

7. 리버스 가희와 프로세스 1 / 8. 가희와 프로세스 2

이거는 시간이 모자라서 문제를 못 봤다. 7번은 3번의 답이 주어졌을 때 거꾸로 프로세스들의 id, 중요도, 시간을 출력하는 문제였는데 쉽게 답이 떠오르지 않았다. 8번은 문제를 열어보지도 못 했다(..)

 

 

시간 안에 푸는 문제치고는 꽤 좋은 성과를 보여준 것 같다 뿌듯했다. 두 문제는 공개되면 한 번 풀어 봐야지. 코드도 문제가 공개되면 다듬어서 다시 올려야겠다.