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

Jeuk Oh·2021년 9월 9일
0

ㅋㅅㅋ

목록 보기
1/10

1번

set을 이용해서 쉽게 풀 수 있었다. 넘어가자.


2번

정해진 규칙대로 격자를 진행할 때 사이클이 되는 경우의 수와 경로 추적

처음에 bfs나 dfs로 풀어야하나 고민했는데 그냥 구현으로 풀었다.


3번

여기서 풀다가 시간을 다 쓰고 막혔다.

간략한 문제 설명

도시에 필요한 금 a와 은 b가 주어지고

광산 i개에 대해 i번째 광산의 금의 량, 은의 량 g[i],s[i]가 주어지고,

도시에서 i번째 광산을 왕복하면서 물자를 나르는 i번째 트럭의 무게한도 w[i]와 편도 시간 t[i]가 주어질 때,

a, b를 채우기 위해서 드는 최소 시간.

접근

처음엔 저번 다리 건너기 처럼 모든 트럭을 보내고 도착하는 순서를 빨리오는 순대로 처리하면서 a와 b를 줄이는 문제라 생각하였으나 i가 10510^5까지 있고, a, b나 t도 10810^8 정도 높은 숫자라 그렇게 접근하면 시간초과가 날 것이라고 생각하였다.

극단적인 예제로 a=10^8,

w[0] = 1 t[0] = 1,
w[1] = 10^8 t[1] = 10^6

막 이렇다면 1번째 트럭이 왔다갔다하는동안 t[0] 왔다갔다 연산을 10^6번을 해야한다. 따라서 구현보다는 산술적으로 해결해야한다고 생각하였다.


얼마 전 풀었던 프로그래머스 문제, 입국심사 에서 아이디어를 얻었다. 광산의 광물을 다 빼는데 걸리는 시간을 각각 계산해서 그 중 최대 시간 Tmax를 구하고 최소 시간 1을 생각한 다음에 이분탐색으로 a,b를 채울 수 있는 최소 시간을 찾아가는 것으로 접근하였다.

다만 여기서 문제가 있었는데, 주어진 시간이 조건을 만족할 수 있는지에 대한 계산이었다. 금과 은이라는 다른 량에 접근해야하고, 광산의 금, 은의 량도 무한하지 않아서 이분 탐색 시에 정확한 계산을 하는 것이 어려웠다.

주어진 시간이 클 때는 a,b를 넉넉하게 채우므로 문제가 없었지만, 최소 시간과 근접하게되면 모든 트럭들이 유기적으로 다른 트럭을 위해서 금과 은을 가져오는 비율을 맞춰야한다. 이 부분을 일단 그리드로 (a > b면 금을 일단 최대한 가져오고 b > a 면 은을 최대한 많이 와!) 짰는데 당연히 실패.

이 부분에서 알고리즘적 아이디어가 떠오르지 않아 결국 시행착오만 하다가 시간을 다 쓰고 말았다.

마지막으로 생각한 것은 (g[i]-s[i], i)를 저장하는 최대힙을 만들어서 은 대비 골드가 많은 광산부터 금을 없애도록 해서 금이 많은 친구로 금부터 빨리 없애고 뒤에선 은만 없애는 것이었는데, 이제 생각해보니 금과 은이 균형적인 테스트 케이스라면 그닥 의미가 없다.

10분만에 푸신 분도 있으시던데 존경합니다. 풀이 구합니다 ㅜ


4번

3번 푸느라 시간을 다 써서 문제만 슬쩍 읽고 넘어갔다. 다른 분들 풀이를 보니 다들 4번이 더 오래걸리던데 훨씬 어렵나보다 ㅎㄷㄷ


느낀 점

입사 코테는 아니지만 개발 쪽으로 진로를 잡기로 마음 먹고 처음으로 봐본 공식적인 코테였는데, 역시 어렵기도 하고 2번까지 풀면서 100위권이길래 오오 했다가 3번만 하루종일 풀면서 우우 했습니다. 마지막까지 시험보다가 테스트가 닫힌 경험은 정말 오랜만인 것 같습니다. 영 시험 칠 일도 없어서... ㅋㅅㅋ

결과를 보니 리더보드에 이름이 있어서 깜짝 놀랐습니다. 헤헤 사실 이거 자랑하려고 쓴 글입니다.

profile
개발을 재밌게 하고싶습니다.

1개의 댓글

comment-user-thumbnail
2021년 9월 26일

https://prgms.tistory.com/101

풀이가 나왔습니다. 3번은 아쉽게도 이분탐색 까지만 접근이 맞았네요. 더 정진해야겠습니다.

답글 달기