220912 월 Algorithms TIL

프로그래머스 2021 KAKAO BLIND RECRUITMENT 광고 삽입 lev3

• 문제
• 코드-파이썬
• 코드-자바
  • 주의. 누적합의 자료형은 logs는 크기가 300,000 이하라 누적합을 구할 때 시간 최대값이 360000초 * 300000 이 될 수 있어 long으로 잡아줘야 한다.
• 카카오풀이

in, out이 구간으로 주어질 때 각 초마다 몇 개의 구간이 포함되는지 구할 때, 누적합을 이용한다는 풀이를 배울 수 있다

• 구간합을 구할 때 투 포인터를 이용할 수 도 있고 누적합을 이용할 수도 있다

카카오 풀이 - 누적합

해당 구간에 재생한 사람 수를 초마다 곱하게 되므로, 해당 초에 몇명이 듣고 있는지를 각각 구한 다음에 어차피 1초 기준이므로 누적합을 시간범위(광고시간) 안의 누적합(광고끝시간의 누적합 - 광고시작시간 누적합)을 구하면 구하고자 하는 값을 구하는 방식이다

• 1) 해당 초 ~ 초+1에 재생하는 수 구하기
  • time 배열에 시작된 수 - 끝난 수를 기입
  • 다시 time 배열을 돌면서 누적합을 구해서 해당 초에 재생이 되고 있는 수를 구함
• 2) 해당 초 ~ 초+1dp 재생하는 수에 대한 누적합 구하기
• 3) time배열을 돌면서 해당 시간을 끝나는 시간 기준으로 삼았을 때 시간범위(광고시간)있는 것의 최대 누적합을 구하는 것으로 정답을 구하는 방식

투포인터 이용하기

해당 초에 재생하는 수들을 구하는 것까지는 똑같으나 누적합을 구하지 않고(위에서 1)까진 똑같고), 투 포인터로 이동하면서 누적합을 구하는 방식

• 투포인터로 구했을 때 (파이썬)

• 카카오풀이로 누적합으로 구했을 때(파이썬)

  • 누적합으로 구해야 하므로 누적합을 구하는 구간의 끝점은 play_time이 되어야 한다.

자바 - String.format 을 이용하자

String.format("%02d")
%: 명령의 시작
0: 채울 문자
2: 총 자리수
d; 정수