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

저번에 재밌게 풀었던 시리즈 대회가 열렸다. 1회때와 같이 문제들이 재밌다. 처음 생각한 풀이와는 다르게 생각하는 문제들도 있었다.

1시부터 바짝 참여하지는 못했지만, 5문제를 풀었다. 풀이는 아래.

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

 

뭐야 내 페널티 돌려내요

---

 

1. 가희와 파일 탐색기

문자열 관련 문제를 풀 때면 파이썬밖에 못 하는 나를 조금은 이해할 수 있게 된다.. 단순 정렬 세 번으로 문제를 해결했다. 우선순위의 반대순서대로 정렬을 진행하면, 우선순위를 모두 만족하게끔 정렬할 수 있다.

파일명과 확장자로 나눠 입력받고, 지원하는 확장자들을 dict 를 통해 관리한 뒤, key 를 각각 확장자, 지원 여부, 파일명 순서대로 정렬을 세 번 한다.

 

2. 가희와 키워드

이 문제도 브루트포스로 해결했다. dict 를 통해서 사용해야 하는 키워드 목록을 1로 저장한다. 모든 포스팅의 키워드들에 대해서, 딕셔너리 탐색했을 때 딕셔너리에 없는 경우이거나, 이미 포스팅한 경우는 넘어간다. 딕셔너리에 1로 저장된 키워드의 경우에는 정답을 N에서 1씩 빼주면서 각 포스팅별로 정답을 출력해주면 된다. 처음에는 키값의 합을 모두 구해가면서 정답을 출력했다. 시간 초과 한 번 맛보고 코드를 고쳐서 맞았다.

 

3.  가희와 은행

단순 시뮬레이션 문제. 지문이 길어서 해석하는 데 시간이 꽤 걸렸다.

손님은 업무에 필요한 시간이 각각 있고, 카운터는 한 손님에게 최대 $T$ 시간만을 소비할 수 있다. 한 손님의 필요시간이 카운터의 능력 밖이면, 일단 $T$ 시간만큼 작업한 뒤에 다시 줄의 맨 뒤로 돌려보내는 식이다.

이 때, 추가로 새로운 사람이 특정 시간에 들어올 수 있다. 따라서, 구현할 때 순서가 중요하게 작용한다. 사람을 앞으로 빼고, 뒤에서 추가해야 하므로 덱을 사용한다. 기본 줄과 나중에 올 사람들을 덱으로 구현하는데, 나중에 올 사람들은 시간에 따라 정렬해 둔다.

처음에, 줄에서 사람을 한 명 뽑아와서 그 사람의 남은 시간, 또는 카운터의 소비 가능 시간을 비교해서 쓸 시간을 정한다. 이후에 그 사이 들어온 사람이 있는지를 먼저 확인해야 한다. 작업을 하는 도중에 사람이 들어오지만, 편의상 작업을 완료한 뒤에 사람을 추가하기 때문이다.

초 단위로 안 하고, 손님 단위로 해결했다. 훨씬 빠르기도 하고 직관적이기도 하다. 다만 이 경우에는 줄이 비는 경우가 생길 수 있다.

처음 구현만 신경써서 해주면 어렵지 않게 풀 수 있다. 사실 지문이 길어서 뒤로 미뤄두다가 마지막에 풀었다.

 

4. 가희와 btd5

풍선타워디펜스에서 영감을 받은(?) 문제. 중요한 사실을 놓치면 안 되는데, 모든 풍선은 개틀링 거너에서 쐈을 때 한 번에 터질 수 있도록 배치돼 있다. 즉 풍선은 일직선상에 있으며, 같은 사분면에 위치해 있고, 풍선을 지나는 직선은 원점을 지난다.

우리가 구해야하는 것은 남은 풍선의 개수이므로, 풍선의 순서는 중요하지 않다. 따라서 내가 원하는 대로 섞어다가 써도 된다. (대부분 이런 유형의 경우 binary search를 이용한다)

풍선의 좌표와 순서 또한 중요하지 않으므로 체력만을 저장한 뒤 정렬해둔다.

개틀링 거너가 풍선을 바라보고 있는지 여부만 파악한 뒤, 바라보고 있지 않다면 넘어간다. 풍선이 일직선상에 위치하기 때문에 어떤 풍선도 맞지 않을 것이다.

풍선을 바라보고 있다면, (지금까지 쐈던 힘 + 현재 힘)을 체력 배열에서 이분탐색해주면 된다. 이분탐색한 값이 곧 사라진 풍선의 개수이므로 전체 풍선 개수에서 뺀 뒤 출력해주면 된다.

문제 똑바로 안 읽으면 큰일날 뻔 했다. 사실 지문의 처음에 개틀링건의 알고리즘을 소개할 때, 공격하고자 하는 목표물의 방향으로 공격 방향을 바꾼다고 쓰여져 있어서 풍선을 바라보는 것이 보장되는 줄 알았다.

놓친 부분이 두 군데 있었다. 하나는 $(1, 1)$ 에 위치한 풍선이 $(-1, -1)$ 을 바라보면 쏠 수 없다는 점과, 축과 평행한 경우의 예외처리였다. 좌표계의 기울기로 헤매다가 CCW를 데려와서 해결했다.

 

6. 가희와 비행기

2, 4, 6, 8, 10까지 그려보고 카탈란 수를 확인했다(...) 처음에는 격자 형태로 만든 뒤에 전체 경로의 수를 하나하나 세어야하나 했는데 그리고 보니 그렇게 됐다. $\lfloor \frac{N} {2} \rfloor-1$ 번째 수를 구하면 된다.

 

 

5번 기차 문제는 지문 해석하는거랑 그래프 모델링이 너무나도 귀찮아서 넘겼다. 7, 8번은 내 실력 부족.

7번은 거북이들이 움직이는 것보다 집이 상대적으로 움직이면 되겠다는 생각까지는 했다. 근데 장애물이 있는 예제 2번 입력의 경우를 해결하지 못했다.

문제푸는 데 삽질을 너무 많이 한다. 일단 제출하고 보자라는 게 참 안 좋은 습관이다.. 그렇다고 내가 틀리기 전까지는 틀린 게 아니니까(?) 일단 낸다.. 엄밀한 증명과 풀이와는 사이가 안 좋은 것 같다.

시간내로 문제를 해결하는 건 재미있다. SCPC랑 UCPC 지원 못 한게 정말 아깝다. SCPC는 파이썬 못 쓰니까 그러려니 해도..

문제 푼 거 꾸준히 올려야지, 요즘 블로그를 너무 안 해