코딩테스트 복기 - 당장 필요한 값을 구하지 않고 나중에 필요할 때 값을 구하는 테크닉2

1. 문제

 

n명의 아이는 연속 A[i]일 이내 칭찬을 듣지 못하면 기분이 안좋아진다. (i = 1,2,3,...,n)

 

선생님이 1일부터 m일까지 매일 1명의 아이 B[i]번 아이에게 칭찬을 해준다. (i = 1,2,...,m)

 

이미 기분이 안좋아진 아이에게 칭찬을 해줘도 아이는 기분이 좋아지지 않는다.

 

1일부터 m일까지 각 날마다 기분이 좋은 아이의 수를 구하고자 한다.

 

0일차에는 모든 아이에게 칭찬을 해줘서 기분이 좋은 상태라고 가정한다.

 

예를 들어 4명의 아이는 2일, 3일, 1일, 2일 이내에 칭찬을 들어야한다.

 

선생님이 6일 동안 3번, 1번, 2번, 1번, 4번, 1번 아이에게 칭찬을 해줬다.

 

1일차에는 3번 아이에게 칭찬을 해줬다.

 

2일차에는 1번 아이에게 칭찬을 해줬는데, 2일 이내에 칭찬을 못들은 4번, 1일 이내에 칭찬을 못들은 3번 아이는 기분이 나빠졌다.

 

3일차에는 2번 아이에게 칭찬을 해줬다.

 

4일차에는 1번 아이에게 칭찬을 해줬다.

 

5일차에는 4번 아이에게 칭찬을 해줬지만 이미 기분이 나빠졌으므로 칭찬을 들어도 기분이 좋아지지 않는다.

 

6일차에는 1번 아이에게 칭찬을 해줬는데, 3일 이내에 칭찬을 못들은 2번은 기분이 나빠졌다.

 

그러므로 [4,2,2,2,2,1]을 return해야한다.

 

제한

 

n,m은 30만 이내

 

 

2. 풀이

 

설명대로 그대로 시뮬레이션하면 $O(N^{2})$이 가능하다.

 

매일마다 칭찬을 들은 아이 번호를 순회한 다음, 마지막으로 칭찬을 받은 날짜를 기억해둔다.

 

그리고 칭찬을 들은 아이 번호를 제외하고 나머지 번호들을 순회해서 현재 날짜와 마지막으로 칭찬 받은 날짜를 비교하면..

 

현재 기분이 나쁜 상태인지 아닌지 알 수 있을 것이다.

 

하지만 N,M이 30만 이내라... $O(N^{2})$은 시간초과

 

---------------------------------------------------------------------------------------------------------------------------------------------------------

 

놀랍게도 O(N)에 해결할 수 있는 방법이 있긴 있다

 

핵심은 "매일마다 기분이 나쁜 아이 수를 구할 생각을 하지 말자"이다

 

(이 생각을 벗어나지 못하면... 절대로 해결 못함)

 

매일마다 기분이 나쁜 아이 수를 구할 생각을 해버리는 순간 O(N)에 절대로 못푼다

 

https://deepdata.tistory.com/1108

코딩테스트 복기 - 당장 행동하지 않고 나중에 필요할 때 행동하는 그리디 알고리즘 테크닉

 

 

여기서 배운 테크닉처럼, "일단 값을 모두 구해놓고 필요할때 한번에 구하자는 마인드"

 

 

2번째로는 "각 아이는 몇일차까지 칭찬을 받아야 기분이 안나빠지는지 제한시간을 구해놓자"이다

 

각 아이가 몇일차안으로 칭찬을 받아야 기분이 안나쁜지 알고있다면,

 

i번째 날에 어떤 아이가 칭찬을 받았다고 한다면, 그 아이가 j일 안으로 칭찬받아야하는 아이인지, j를 알고 있으므로

 

i가 j보다 큰 경우라면 이미 기분이 나쁜 아이이므로, 그대로 둔다.

 

여기서 기분이 나쁜 아이도 갱신해버리면 나중에 망한다

 

 

하지만 i가 j이하라면 제한시간 안에 칭찬을 받았으므로, 언제까지 칭찬을 받아야하는지 날짜를 새로 갱신할 수 있다.

 

이렇게 한다면 1일부터 m일까지 순회하면

모든 아이의 언제까지 칭찬을 받아야하는지 제한시간이 구해져있다.

 

 

이제 다시 이 제한시간 배열을 순회하면, 각 아이가 기분이 나빠진 상태인지 아닌지 알 수 있게 된다.

 

제한시간이 m일보다 크다면 그 아이는 m일 이내에는 기분이 나빠진 상태가 아니다.

 

m일 이하라면, 그 아이는 m일 이내에 기분이 나빠진 상태이다.

 

 

따라서 이렇게 하면 각 날짜 1일,2일,...,m일에 기분이 나빠진 아이 수를 O(N)으로 구할 수 있다.

 

 

이제 매일 기분이 좋은 아이 수 배열에 기분이 나빠진 아이 수 배열을 빼주면, 

 

매일마다 기분이 좋은 아이 수를 구할 수 있다.

 

 

A = [2,3,1,2] #아이가 연속해서 언제까지 칭찬을 받아야하는지 단위 제한시간

B = [3,1,2,1,4,1] #선생님이 매일마다 칭찬을 준 아이 번호

n = len(A)
m = len(B)

answer = [n]*(m+1) #1일부터 m일까지 기분이 좋은 아이 수

#최초 0일차에는 모든 아이가 칭찬받았다
#각 아이는 (A배열의 원소) 일 이내 칭찬받아야한다
C = [0]*(n+1)

for i in range(1,n+1):

    C[i] += A[i-1] #C는 각 아이가 칭찬받아야하는 제한 시간

#이제 선생님이 매일 칭찬을 주는데
for i in range(m):

    p = A[i] #칭찬을 준 아이 번호
    
    #현재 i+1일차, p번의 제한시간 C[p]보다 작거나 같다면..
    #제한시간 이내에 칭찬을 들었으므로 제한시간을 갱신
    #i+1일차에서 단위 제한시간 A[p-1]만큼 늘어난다
    if i+1 <= C[p]:

        C[p] = i+1+A[p-1]

#이제 각 날 1,2,3,..,m일에 기분이 나빠진 아이 수를 구한다
D = [0]*(m+1)

#만약 제한시간 C[i]가 m일 이하라면, m일 이내에 기분이 나빠진 아이이다.
for i in range(1,n+1):

    if C[i] <= m:

        D[C[i]] += 1

#기분이 나빠진 아이는 계속해서 기분이 나쁘므로, 
#i일차에 기분이 나쁜 아이는 i+1,i+2,i+3,...,m일에도 기분이 나쁘다
#그래서 기분이 나빠진 아이 수 배열 누적합을 구해준다 
for i in range(m):

    D[i+1] += D[i]

#각 날에 기분이 좋은 아이 수 answer[i]에 각 날에 기분이 나쁜 아이 수 D[i]를 빼준다
for i in range(m+1):

    answer[i] -= D[i]

print(answer[1:])
[4, 2, 2, 2, 2, 1]