log 2021-09-09

---

• sport
  • kakao 2019 다시풀기 2
    • 무지의 먹방 라이브
• project
  • pseudo

sport

kakao 2019 다시풀기 2

무지의 먹방 라이브

hint

회전하며 배열에서 음식을 1씩 소비한다고 했을 때, k번째 소비하게 되는 음식 (인덱스) 찾기

n 20만, 원소 10억이므로, 반드시 효율적으로 풀어야 한다. O(nlgn) 수준 이하로 해야 함.

어떻게?

ㅁㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁ ㅁㅁㅎㅁㅁㅁ ㅁㅁㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁ

어떤 수에 대해, 나온 전체 수를 알 수 있지 않나? 정렬한 다음, 이분탐색으로 위치를 찾으면, 그 수 이하의 수가 몇개인지 알 수 있으므로, 어떤 수에 대해 총합 얼마가 나왔는지 알 수 있다. 그 총합이 k이하 어떤 수가 되도록 한 후, 남은 컬럼들 중에서 %N 만큼 이후의 컬럼을 선택하면 된다.

과정:

ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ (1, 10) ㅁㅁㅁㅁ (2, 4) ㅁㅁㅁㅁㅁ (3, 5) ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ (4, 11) ㅁㅁㅁㅁㅁㅁㅁㅁ (5, 8)

ㅁㅁㅁㅁ (2, 4) ㅁㅁㅁㅁㅁ (3, 5) ㅁㅁㅁㅁㅁㅁㅁㅁ (5, 8) ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ (1, 10) ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ (4, 11)

k=23이라 하면, 먼저 k보다 작은 최대의 합을 만드는 수 p를 찾아야 한다. p=3 -> 15 p=4 -> 20 p=5 -> 29

따라서 p=4, 남은 수 l=k-p=3이고, 열이 남은 컬럼들은 3,5,1,4이므로 세 번째인 (1,10)이 답이 된다.

문제는, 이분탐색으로 p를 찾는 구현이 좀 복잡할 듯하다.. 또, p가 주어졌을 때 합을 어떻게 찾는가..

아니면, 정렬해놓고, 각 컬럼간 차이들을 구해서, 이를 이용해서 구할 수 없을까.. 첫 높이 h1 -> h1*n만큼 커버됨. 그 다음 높이 h2 -> (h2-h1)*n … 만큼씩 커버가 된다.

그러면, 앞에서부터 k를 빼가면서 비교하면 된다. 그러다가, k가 모자란 시점에, 그 높이에서 남은 컬럼의 수…

다시 해당 높이에서 이분탐색…? p개의 cols 중에 k번째..

ㅁㅁ ㅁㅁ ㅂㅂㅂㅁㅁ ㅂㅂㅂㅎㅁㅁ ㅂㅂㅂㅁㅁㅁㅁㅁ

이 경우, 높이가 최소 보장이 되므로, xH < k인 최대 정수 x를 찾아서, xH+i=k라 할 때 i가 답이 된다. 다만, 높이를 N을 곱해야 하나 아니면 N-cur를 해야 하나?

남은 컬럼들에 대한 계산이므로, cur를 빼야 한다. 또한 N==cur즉 남은 음식이 없는 경우 처리도 필요

추가: 알고보니 저렇게 복잡하게 계산할 것 없이, k % (높이) 만 계산하면 되는 것이었다.

py solution

def solve(food_times, k):
    cur = -1
    left = 0
    N = len(food_times)
    cols = []
    for i,v in enumerate(food_times):
        left+=v
        cols.append((v, i+1))

    cols.sort()
    diffs = [cols[0][0]]
    for i in range(N-1):
        diffs.append(cols[i+1][0] - cols[i][0])
    cur = 0
    while True:
        if(cur == N):
            break
        nextv = diffs[cur]

        if(k>=nextv * (N-cur)):
            k -= nextv * (N-cur)
            cur+=1
        else:
            break
        pass

    cols = cols[cur:]
    
    cols.sort(key=takeSecond)

    if(N==cur):
        return -1
    x = math.floor(k/(N-cur))

    k -= x*(N-cur)
    
    return cols[k][1]

ㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁㅁㅎㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ

x * (N-cur) + k

project

pseudo

다음 항목들에 대한 통계 업데이트 필요. 어떻게 할 것인가? 주기적 업데이트로 유저의 해당 항목들 조사.

  post: Joi.number().default(0),
  vote: Joi.number().default(0),
  comment: Joi.number().default(0),
  study: Joi.number().default(0),
  answer: Joi.number().default(0),
  question: Joi.number().default(0)

---