[2021 Dev Carnival] 데브카니발 2021 코딩테스트 금손 배지 후기 (문제 복기)
study/problemsolving

[2021 Dev Carnival] 데브카니발 2021 코딩테스트 금손 배지 후기 (문제 복기)

goorm.io에서 진행하는 2021 Dev Carnival : 데브 카니발에 참가했다 ! 5월 22일에 진행됐던 코딩테스트였는데, 얼마 전에 테스트 결과가 메일로 날아왔다. 잊고 있었는데 다시 생각나서 글을 쓴다. 테스트를 하면서 작성한 코드를 따로 저장해두지는 않아서 정확한 코드를 가지고있지는 않다. 기억나는 대로 문제를 복기해봐야겠다.

 


 

1번 문제는 단순구현 문제였다. 사람마다 먹을 수 있는 음식 양이 정해져 있고, 음식을 순서대로 먹으며 양을 넘는 사람들의 순서를 출력하는 문제였다. 배열 돌려가면서 빠르게 해결했었다.

 

2번은 구현이 조금 힘들어보여서 3, 4번을 먼저 봤었다. 3번은 보자마자 DP라는 생각이 들어서 도망쳤고, 4번 문제를 붙잡았다.

단방향 그래프가 주어지고, 한 번 정점을 방문할 때마다 방향이 역방향으로 바뀐다. 그래프를 두 가지를 만들어서 (정방향 / 역방향) 모든 정점에 대해서 BFS를 돌리고, 방문할 수 있는 최대 정점 개수를 구했다. 테스트케이스만 몇 개 만들고 맞는 거를 확인하고 제출했다.

 

사실 이 부분이 제일 아쉽다. 참가자는 제출한 코드가 AC를 받았는지, WA를 받았는지 알 수가 없다. 제출해놓고도 변수 초기화나 반복 부분에서 실수한 게 있나 계속 확인하게 됐다.

 

1, 4를 풀고, 3번은 도저히 방법이 생각이 나지 않아서 2번을 붙잡고 늘어졌다. 한 번의 조종에 두 개의 유닛을 모두 움직일 수 있었다. 탈출구도 두 개였고, 탈출구에서는 유닛이 겹쳐도 된다. 이 부분에서 상당히 애를 많이 먹었다. 본문에 유닛이 겹칠 수 있다는 내용이 탈출구에 한정돼 있었기 때문에, 유닛이 겹칠 수 있는지에 대한 여부가 정답을 판가름했었다.

백준의 구슬 탈출과 같은 문제라고 생각해서 유닛이 겹치지 않는다고 생각했다. 두 유닛 중 주어진 움직임에 대해서 어떤 유닛이 먼저 움직여야 하는지를 판단하는 함수를 짰다. 추가로 BFS를 돌면서 1번 유닛, 2번 유닛의 탈출구를 향한 경로를 따라가며 두 유닛의 탈출여부를 판단했다.

 

사실 겹친다고 판단하면 문제가 상당히 쉬워졌다. 주어진 움직임에 대해서 유닛의 행동을 강제할 필요 없이 두 유닛을 움직여주면 됐으니 훨씬 널널했을 텐데. 아쉬운 문제였다. 문제에 대한 문의도 했으나 너무 늦은 시간에 문의를 드려 검토 후 답변을 주겠다는 말만 듣고 테스트가 종료됐다. 제출은 겹칠 수 있다고 판단하고 코드를 짠 걸로 냈다.


 

다행히 결과는 괜찮은 듯했다. 금손과 은손이라는 배지를 성적에 따라 부여했는데, 금손 배지를 받았다~!

여전히 결과가 궁금해서 테스트 페이지에 접속해봤지만 따로 문제별 정답여부를 공개해두지는 않았다. 직접 채용과 연계돼 그런 걸지도 모르겠다. 3번 보자마자 DP라는 생각은 들었지만 해결책이 안 떠오르는 건 공부가 답이겠지,,

데브 카니발 결과 통보 메일