[210513] 프로그래머스 월간 코드 챌린지 시즌2 5월 후기

프로그래머스에서 월간 코드 챌린지 시즌2를 4월, 5월에 걸쳐 진행한다길래

접수해서 응시한 챌린지이다!

 

4월 4문제, 5월 4문제가 출제되고, 두 번의 대회 중 4문제 이상 맞출 경우에

경품 이벤트 응모가 가능하대서 한번 재미삼아 응시한 챌린지이다.

턱걸이로 4문제 맞춰서 이벤트 응모!

개인적으로 프로그래머스 굿즈, 배민 상품권 (2만원권)을 받고 싶은데,

이번에 4문제 이상 맞힌 사람이 꽤 많을 듯 하여 경쟁률이 치열할 듯 하다.

 

나의 시즌2 4월 후기는 아래 포스팅에서 볼 수 있다.

https://kth990303.tistory.com/38

[210415] 프로그래머스 월간 코드 챌린지 시즌2 4월 후기

 

이번 5월 챌린지를 접수한 개발자는 총 6,546명이었으며,

400점 만점은 전체에서 4명이다.

300점 이상은 75명, 

200점 이상은 737명이다. (199점도 한 분 있던데...)

아래 링크에서 순위를 볼 수 있다! (1등은 ps 괴물로 유명하신 ainta님... 4문제 46분 실화인가..)

https://programmers.co.kr/competitions/1078/monthly-code-challenge-s2

프로그래머스 월간 코드 챌린지 시즌2

 

나는 이번 5월 대회에선 두문제를 100점을 받고,

세 번째 문제에서 4.8점 부분점수를 긁어 215등을 기록하였다~

내 성적은 아래와 같다.

이번에는 우리 학교 과동기이자, 내가 예전부터 대단하게 지켜봤던 분인

aru0504님도 응시하셨다고 한다.

aru0504님은 3번 문제를 정확하게 solve하셔서 300점으로 53등을 기록하셨다고 한다.

---

문제 및 해설 링크

문제와 해설은 아래 링크에서 확인할 수 있다.

https://programmers.co.kr/learn/challenges?tab=all_challenges 

코딩테스트 연습

https://prgms.tistory.com/57

[월간 코드 챌린지 시즌 2] 5월 문제 해설

---

문제 소개

아래부터는 문제에 대한 스포일러가 있습니다.

문제	프로그래머스 레벨	Solved.ac 예상티어	정해 알고리즘
약수의 개수와 덧셈	1	Silver V	수학, 구현
2개 이하로 다른 비트	2	Gold V	수학, 비트마스킹
110 옮기기	3	Gold II	스택, 그리디
중력 작용	5	Diamond V	HLD, Splay tree, Treap

프로그래머스 스킬 체크는 레벨3을 패스했으나,

4월, 5월 연속으로 레벨3 문제를 해결하지 못해 조금 속상하긴 하다.

그래도 이번 "110 옮기기" 문제 덕분에 스택에 대한 공부의 필요성을 절실하게 느꼈다.

 

또한, 4번 문제의 난이도를 보고 경악했다.

HLD 알고리즘은 aru0504님께 듣기만 한 알고리즘인데,

여기서 나올 줄은 상상도 못했다.

프로그래머스 레벨5 문제는 정말 상상 이상으로 어렵다는 것을 깨닫게 된 챌린지이다.

---

(Level 1) 1. 약수의 개수와 덧셈

코딩테스트 연습 - 약수의 개수와 덧셈

제곱수인 경우는 약수의 개수가 홀수이다.

따라서 반복문으로 1, 4, 9, .. 등 제곱수를 따로 bool형 변수에 true로 체크해두고, 제곱수가 1000이 넘어가면 반복문을 break해주었다.

 

처음에 소수일 때 또한 고려해야 하는 줄 알고, 에라토스테네스 체 슈도코드를 세웠는데 필요가 없었다.

여기까지 걸린 시간은 5분이다.

---

(Level 2) 2. 2개 이하로 다른 비트

코딩테스트 연습 - 2개 이하로 다른 비트

잘 보면 범위가 1<=Numbers<=10^15가 아니라 0<=Numbers<=10^15이다....

 

비트마스킹을 이용해 제일 큰 1을 기준으로 오른쪽에 0이 하나도 없으면, 왼쪽에 새로 1을 만들어주고, 자기 자신을 0으로 만들어준다.

(ret & 1LL<<j)의 결과에 따라 2^j의 비트가 1인지, 또는 0인지 확인할 수 있으며,

현재 비트를 0에서 1로 만드는 방법은 ret|=1LL<<j,

1에서 0으로 만드는 방법은 ret^=1LL<<j를 이용하였다. long long 범위임에 주의하자.

 

주의할 점은 0일 때이다!

0일 때는 그냥 1을 리턴해주도록 예외처리를 해주어야 한다.

이 예외처리 때문에 이 문제를 108분 쯤에 정답처리되었으며,

무려 85분 정도를 날렸다....

이 예외처리를 안할 경우 72.7점을 받는다. 나와 비슷한 사람들이 10명대 정도 보였는데... 힘내세요 ㅜㅜ

 

문제랑 범위를 진짜 잘읽자...

---

(Level 3) 3. 110 옮기기

코딩테스트 연습 - 110 옮기기

나는 처음에 3번을 봤을 때, KMP로 "110"과 "111"의 위치를 모두 확인한 후,

서로 swap해주는 방식을 이용했고,

swap하여 문자열이 바뀌면 while문으로 반복하는 알고리즘을 짰다.

"110"과 "111"을 서로 swap하는 경우도 많은데, 이 때마다 kmp (o(N))을 적용하니 당연히 시간초과를 받을 수 밖에 없었으며, 아무리 잘 처리한다해도 예외케이스가 많이 나올 수 밖에 없었다.

 

aru0504님께서 3번 해결방법을 알려주시고 있다.

알고보니 스택을 이용한 그리디였는데,

그냥 "111"의 위치는 전부 파악할 필요 없이,

"111" 바로 앞에 "110"의 개수만큼 110으로 끼워넣어주기만 하면 된다.

 

또는, 결국 변형된 문자열은 "110"이 전부 빠진 상태이므로 "111"을 제외한 나머지 세글자는 "110"보다 사전순으로 앞에 위치한다. 따라서 변형된 문자열에서 마지막 "0" 뒤에 "110"의 개수만큼 110으로 끼워넣어주는 방법을 이용해도 된다. 개인적으로 이 방법이 더 편한 듯하다.

 

"110"의 개수만큼 "111" 앞에 생긴다는 것은 코드를 짜면서 관찰로 확인할 수 있다.

(다만 나는 이 점에서 그리디를 의심하지 않고 문자열을 이동하다보니 자연스럽게 생기는 결과인 줄 알았다...)

 

"110"을 뽑아내는 방법은 스택을 이용하면 된다. 

예를 들어 "111111000" 같은 경우는?

"110"을 지울 때 문자열에 변화가 생기는데 어떻게 뽑아내냐고?

스택을 이용하기 때문에 "110"이 지워지면 그 이전 "11" 과 그 이후 "0"이 만나 "110"이 돼 결국은 "110"을 계속 뽑아낼 수 있다. 나처럼 멍청하게 kmp를 계속 돌릴 필요가 없었던 것이다.

 

참고로 나는 문자열 폭발에 이용되는 자료구조를 stack이 아닌 vector로 하였다.

stack이나 vector이나 push_back, pop_back 성질은 같으며, 

vector이 임의의 index 접근을 허용하기 때문에 

문자열에서 임의의 index 접근이 필요한 경우여서 vector로 이용하였다.

문자열 폭발 코드는 아래와 같다.

for (int j = 0; j < s[i].size(); j++) {
	st.push_back(s[i][j]);
	while (st.size() >= p.length() && string(st.end()-p.length(), st.end()) == p) {
		cnt++;
		for (int k = 0; k < p.length(); k++) {
			st.pop_back();
		}
	}
}

위와 같이 '문자열 폭발' 방법이 아닌, KMP 코드 이용하는 방법으로 이용한 나와 비슷하게 해결하신 분들은 (아마도) 4.8점을 받았을텐데, 은근 나와 비슷한 케이스가 많았다 ㅎㅎ....

---

(Level 5) 4. 중력 작용

코딩테스트 연습 - 중력 작용

대회 중엔 문제를 살펴보지도 않았다.

나중에 살펴보니 트리 형태에서 lazy propagation을 적용해야 해서 HLD 알고리즘이 필요해보인다.

그 뒤로는 고민 안해봤다.

스택 공부해보고 여유가 된다면 HLD 알고리즘도 공부해봐야겠다.

---

aru0504님 덕분에 챌린지 후기에 대해 서로 얘기를 나눠보기도 했고 4월때보다 훨씬 재밌었다.

'문자열 폭발' 문제도 아루님 덕분에 알게 됐는데, 한 번 재밌게 해결해보면서 내가 공부를 소홀히 여겼던 스택 자료구조에 대한 이해도를 높이는 시간을 가져봐야겠다. 

 

개인적으로 2번 문제는 4월에 비해 어렵다고 판단된다.

그래서 그런지, 5월의 2번 정답자가 4월의 2번 정답자에 비해 많이 적었다.

 

공부 방향을 얻은 것도 기쁘지만, 이벤트 응모 대상자에 속한 것도 기쁘다.

과연 나는 경품에 당첨될 수 있을까?

이번 달은 운이 좋길 기대해봐야겠다.