[211007] 프로그래머스 월간 코드 챌린지 시즌3 10월 후기

이번 달에도 어김없이 프로그래머스에서 주최하는 월간 코드 챌린지가 열렸다.

오늘은 어떤 문제가 나올지, 그리고 이번엔 어떤 성적을 얻을지 기대하면서 응시해보았다.

https://programmers.co.kr/competitions/1581

JetBrains x 프로그래머스 월간 코드 챌린지 시즌3

 

시즌3 9월 후기는 아래 포스팅에서 볼 수 있다.

https://kth990303.tistory.com/132

[210909] 프로그래머스 월간 코드 챌린지 시즌3 9월 후기

---

처음 10월 챌린지를 응시했을 때, 리더보드가 뜨지 않아 좀 당황했다.

월간 코드 챌린지는 실시간 순위 보는 재미로 하는 것도 없지 않아 있는데, 리더보드가 뜨지 않으니 재미가 조금 식는 느낌?

 

그런데 20시에 공지가 내려왔다.

이번 10월 챌린지에는 리더보드를 대회시작 30분 후인 20시부터 공개한다는 공지였다.

마치 백준 스코어보드 프리즈 시스템을 역으로 돌린 느낌이랄까... 아무튼 신기했다.

결과부터 먼저 말해보자면,

9월에 2문제, 10월에 3문제를 AC받으면서 이벤트 응모 자격을 얻었다!

이번 챌린지에선 100등 이내에 들어 풀스크린 스코어보드에서 나의 이름을 확인할 수 있었다!

시즌2 때에는 500등대, 300등대를 하다가,

시즌3에는 100등대, 50등대를 기록하니 

나름 성장한 것 같아 기분이 좋다.

 

그들만의 스코어보드...

상위권에 계신분들은 이름과 이메일이 가려져있지만,

ps를 하는 사람들이라면 누구나 아는 그분들...

(이번 ICPC 2021 월파에서 서울대가 전세계 2등을 차지했는데 역시 서울대 자랑스럽습니다.)

---

점수 분포

400점 이상: 4명

300점 초과: 14명, 300점 이상: 73명

200점 초과: 386명, 200점 이상: 667명

100점 초과: 866명, 100점 이상: 950명

0점 초과: 959명

 

총 959명이 응시하였다.

4번 문제는 지난 9월 챌린지보다 상당히 어려웠으나,

3번 문제가 지난 9월 챌린지보다 약간 쉽거나 비슷한 난이도라고 볼 수 있을 듯하다. 개인적으론 이번 3번문제가 지난번 챌린지의 3번보다 다소 쉬웠다.

2번 문제는 어려운 듯 쉬운 듯 애매했다. 지난번 2번문제보단 쉬운 듯하다.

 

시즌2때보단 이벤트 응모 자격을 획득한 사람 수가 적을 듯하다.

 

아무튼 간단하게 밑에 문제에 대한 후기를 작성해보겠다.

 

*프로그래머스 정책에 따라 이번 챌린지 포스팅에서는 지문, 풀이 코드, 테스트케이스 공유를 하지 않는다.*

 

따라서 간단한 후기 및 느낀점 위주로 포스팅을 하려 한다.

---

문제	예상 난이도	사용 알고리즘
1번	Bronze III	수학
2번	Silver III	수학, 구현
3번	Platinum V	이분탐색
4번	?	?

1번.

9월 챌린지와 마찬가지로 굉장히 쉽게 나왔다.

N의 범위도 작은데다, 단순 계산 문제였기 때문에 쉽게 해결할 수 있을 것이다.

실제로 대부분의 사람들이 1번에서는 1~3분 정도의 시간만 소요했으며,

랭커분들은 15~30초의 시간을 소요했다.

 

2번.

범위가 상당히 크다. 이 문제부터는 시간복잡도를 고려해서 생각해야한다.

이차원 배열을 일차원 배열로 옮기고, 일차원 배열의 [left, right]에 해당하는 원소를 출력하는 문제였는데, 일일이 일차원배열로 옮겨주는 시뮬레이션 작업을 거치면 시간초과를 겪는다.

수학적 성질을 이용하여 /, % 연산자를 이용하여 범위를 구해준다.

그럼 / 연산자를 이용해서 나온 인덱스, % 연산자를 이용해서 나온 인덱스로 적절히 예외처리 및 max를 따져가면서 구해주면 된다. 이 과정에서 좀 헷갈려서 머리아플 수 있다.

 

3번.

부분점수 64.7점과 94.1점을 많이 받아서 꽤나 고통스러웠던 문제.

일단 N, M의 크기가 10억, 쿼리의 개수가 20만 개이기 때문에 BFS, 시뮬레이션으로는 어림도 없다.

완전탐색 또는 BFS를 이용할 경우 O(N*M*Q) 또는 O((N+M)Q)로 시간초과를 받는다. 애초에 N, M이 다항시간으로 존재하면 안된다. 시작점 또한 N*M 배열의 모든 칸을 전부 고민해야되는데, 어떻게 전부 탐색하지 않고 해결할 수 있을까 고민을 꽤 길게 했다.

 

처음엔 상하좌우로 이동하되, 벽에 부딪히면 이동을 하지 않으므로 상하좌우로 총 몇 칸 이동했는지 쿼리를 전부 더해봤다. 그 후, x, y를 적절히 이용하여 범위를 곱해보는 방식을 이용해봤다. 그러나, 이 방법은 중간에 어디에서 벽에 부딪히느냐에 따라 결과가 달라지기 때문에 정확하지 않을 수 있다.

 

그럼 정확한 방법은 무엇이냐?

이 문제는 잘 생각해보면 시작점에 따라 도착점에 도달할 수 있는 여부의 좌표가 단조증가하다가 단조감소하는 꼴이므로 이분탐색으로 O(Qlog(max(n + m)))에 판별이 가능하다.

만약 시작점을 단순히 주어진 x, y로 두고 이분탐색을 진행하면 64.1점의 점수를 얻을 것이다. 시작점 x, y에서 x, y에 도달할 수 있다는 보장이 없기 때문이다. 따라서 이분탐색으로 가능한 시작점 위치 또한 찾아주어야 한다.

 

그런데, 어떤 시작점에서도 x, y에 도달불가능할 수 있다! 이 경우를 놓쳤다면 94.1점을 받는다.

4번.

경우의 수를 구하는 확률 문제였는데, 너무 고려해야될 점이 많아서 조금 보다가 패스하고 시험을 종료했다.

1. 범위가 [idx1, idx2]라 할 때, [idx1, idx1+1], [idx1, idx1+2], ... ,[idx2-1, idx2] 까지 가능했으며,

2. query(idx1, idx2, k)라 할 때, query(idx1, idx2, 1), query(idx1, idx2, 2), ..., query(idx1, idx2, k) 까지 가능했다. 이 때 당연히 query(idx1, idx2, k)에서 1번도 함께 고려한다.

3. 이 수많은 쿼리 중 q개의 쿼리만 사용하는 경우의 수를 구해야 한다. 단, 쿼리를 사용할 때의 결과는 반드시 일정해야 하므로, 반드시 사용해야 하는 쿼리와, 사용하지 않아도 되는 쿼리를 구분해야 한다.

4. 순서는 막무가내로 바뀔 수 있다.

 

마치 수능 확통 고난도 킬러의 극상위호환 버전을 보는 것 같아 바로 런했다...

실제로 4번 만점자는 5명 이내에 불과했으며, 4번에서 부분점수를 긁은 사람은 총 10명 내외였던 것으로 기억한다.

 

---

기념품 세트나 굿즈 세트가 정말 받고싶다

이번엔 과연 이벤트 상품을 탈 수 있을까?

프로그래머스 굿즈를 정말 갖고 싶어 이벤트 응모 자격을 얻기 위해 2문제 이상은 풀겠다고 다짐했는데 다행히 응모할 수 있어서, 그리고 내 실력이 꾸준히 성장함을 보여주는 챌린지기도 해서 꽤나 만족스러운 챌린지였다.