JetBrains x 프로그래머스 월간 코드 챌린지 시즌3(10월) 후기

월간 코드 챌린지 시즌 3 : https://programmers.co.kr/competitions/1581?slug=monthly-code-challenge-s3 

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

문제와 해설은 2021.10.18(월)에 공개된다고 한다.

 

월간 코드챌린지에서 4 문제 이상 풀었어도 응모하기 버튼을 안누르면 응모가 안되는 거 같다.

응모 링크 : https://programmers.co.kr/events/monthly-code-challenge-s3

 

운 좋게 15명 뽑는 JetBrains 기념품 세트에 당첨되었다~

처음으로 알고리즘 대회할 때 입을 수 있는 옷이 생겨 뿌듯하다.

 

 

아래는 문제를 풀며 생각한 것들이다.

 

1번 문제

주어진 수를 어떠한 값으로 나눠서 나머지가 1이 되는 수를 구하는 문제였는데

이때 주어진 수의 범위가 100만으로 매우 작은 값이었기 때문에

2 부터 주어진 수까지 나눠보면서 나머지가 1이 되는 경우 해당 값을 리턴하도록 하면 되었다.

시간복잡도 : O(n)

 

 

2번 문제

n 값이 주어졌을때 n * n 칸의 테이블을 만들고

n 부터 1까지 순회하며 i번째일경우 (0, 0) 에서 (i-1, i-1) 까지 모두 i로 채운 후에

테이블을 행방향으로 모두 자르고 열방향으로 붙인 후의 배열을 출력하는 문제였다.

 

이때 좌표가 (y, x)일 경우 해당 좌표의 값은 Math.Max(y, x) + 1 이되게 된다.

이때 0부터 n*n-1까지 순회하며 

y 좌표 = i/n, x 좌표 = i%n 으로 구할 수 있고

위 공식에 따라 Math.max(y, x) + 1에 넣어주면 쉽게 풀 수 있다.

시간복잡도 : O(n^2) 

 

 

3번 문제

a와 b가 주어졌을때 a행 b열의 테이블을 만들고 각 칸에 공을 넣고

주어진 조건에 따라 이동 후에 y행 x열에 남게 되는 공의 개수를 출력하는 문제였다.

행과 열을 분리하여 생각하면 마지막에 y행 x열에 남게 되는 공의 수는

y행으로 가는 공의 수 * x열으로 가는 공의 수 가 되게된다.

 

x열의 경우 살펴보면

xcnt(xmin에 있는 구슬의 개수) = 1

xmin = 0, xmax = b-1로 초기화한다.

그러면 왼쪽과 오른쪽 두가지의 경우 밖에 없게 되는데

 

왼쪽으로 k칸 이동일 경우

xmin-k 가 음수일 경우 xcnt에 k-xmin을 더해준다.

xmin = Math.max(0,xmin-k);

xmax = Math.max(0,xmax-k);

 

오른쪽으로 k칸 이동일 경우

왼쪽과 다르게 오른쪽은 계산을 해주지 않는다(길이를 통해 개수를 알아낼 수 있으므로)

[길이 = xmax - xmin + 1]

xmin = Math.min(b-1,xmin+k);

xmax = Math.min(b-1,xmax+k);

 

xcnt의 값이 b보다 클경우 b로 수정해준다.

 

해당 쿼리가 끝날경우 x열에 남게 되는 구슬의 수는

x<xmin, x>xmax 일 경우 : 0 개

x==xmin이면서 x==xmax 일 경우 : b개

x==xmin이면서 x!=xmax 일 경우 : xcnt 개

x==xmax일경우 b - (xmax - xmin - 1) - xcnt

xmin<x, x<xmax 일 경우 : 1 개

 

y행의 경우도 x열에서 구한방법과 동일하게 계산하여 구한 값을 서로 곱하여 출력한다.

시간복잡도 : O(n) 

 

 

4번 문제

쿼리의를 날릴 수 있는 개수 q 가 주어지고 원하는 배열이 주어지며

처음에 0으로 가득찬 배열 A을 q(l,r,x)의 꼴로 쿼리를 날려

배열을 원하는 배열로 바꿀 수 있는 경우의 수를 구하는 문제였다.

 

이때 쿼리는 l 부터 r까지의 수를 Math.Max(A[i],x)로 바꿔주는 쿼리였다.

 

해당 문제를 풀면서 q와 A의 크기가 50정도로 작으므로 배열로 만들어 dp를 생각하였으나

아이디어가 떠오르지 않아 완탐으로 구현해본 결과 TLE를 맞았다.

 

결과

이번에는 꼭 첫페이지에 들어가보려고 하였으나 3번 문제에서 시간을 많이 사용해

아쉽게 첫페이지에는 들지 못하였지만 유지 할 수 있음에 감사한다.

첫페이지에 들려면 난이도가 높은 문제들을 빠르게 해결 하는 능력을 길러야 할 것 같다.