[Lv5] 무지의 먹방 라이브

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

무지의 먹방 라이브

* 효율성 테스트에 부분 점수가 있는 문제입니다.

평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.

그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.

회전판에 먹어야 할 N 개의 음식이 있다. 
각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 
무지는 다음과 같은 방법으로 음식을 섭취한다.

• 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
• 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
• 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
  • 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
• 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.

무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다.
무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다. 
각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.

제한사항

• food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
• k 는 방송이 중단된 시간을 나타낸다.
• 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.

정확성 테스트 제한 사항

• food_times 의 길이는 1 이상 2,000 이하이다.
• food_times 의 원소는 1 이상 1,000 이하의 자연수이다.
• k는 1 이상 2,000,000 이하의 자연수이다.

효율성 테스트 제한 사항

• food_times 의 길이는 1 이상 200,000 이하이다.
• food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
• k는 1 이상 2 x 10^13 이하의 자연수이다.

입출력 예

food_times	k	result
[3, 1, 2]	5	1

 

입출력 예 설명

입출력 예 #1

• 0~1초 동안에 1번 음식을 섭취한다. 남은 시간은 [2,1,2] 이다.
• 1~2초 동안 2번 음식을 섭취한다. 남은 시간은 [2,0,2] 이다.
• 2~3초 동안 3번 음식을 섭취한다. 남은 시간은 [2,0,1] 이다.
• 3~4초 동안 1번 음식을 섭취한다. 남은 시간은 [1,0,1] 이다.
• 4~5초 동안 (2번 음식은 다 먹었으므로) 3번 음식을 섭취한다. 남은 시간은 [1,0,0] 이다.
• 5초에서 네트워크 장애가 발생했다. 1번 음식을 섭취해야 할 때 중단되었으므로, 장애 복구 후에 1번 음식부터 다시 먹기 시작하면 된다.

 

---

 

애증의 효율성 문제가 돌아왔습니다.

통과하면 기분째지고, 이래도 저래도 막히면 화가 나는;

 

k초까지 모든 음식을 먹을 수 있다면 -1을 반환,

아니라면 다음에 먹을 음식 번호 반환.

 

즉, 순서값을 기억해둬야 나중에 써먹을 수 있습니다.

 

문제대로의 프로세스라면, LinkedList로 앞에거 빼서 1빼고 0보다 크면 뒤에 추가, 아니면 버림 이나

int[] 로 순서를 1씩 줄이면서 -1대신 최대값넣고 등등이면 되겠지만

 

이래선 정확성은 통과해도 효율성은 통과하지 못합니다.

또 수학적으로 한 번 봅시다.

 

 

[6,2,4,7,8,3]을 봅시다.

이 배열에서 한 순환(cycle)은 6개입니다.

여기 중 제일 작은 수는 2군요.

2*6=12번을 돌면 2만 사라진 채 나머지는 원래 순서를 유지합니다. 아래에서 보여드립니다.

 

12번을 돌았다 생각해봅시다.

6,2,4,7,8,3, 5,1,3,6,7,2 해서

[4,0,2,5,6,1] 이겠네요. 사실 0은 뒤에 붙지 못하고 이전에 사라졌을테니

[4,2,5,6,1]로 줄었겠죠. (남은 애들은 초기값에서 각각 2씩 줄어든 것에도 주목합니다.)

만약 k=12였다면 이대로 4의 음식번호가 답이 될겁니다.

 

만약 k=13이라면? 2의 음식번호. k=14라면? 5의 음식번호.

뭐 이건 그렇다치고.

 

 

[4,2,5,6,1]에서 다시 봅시다.

이 배열에서 한 순환(cycle)은 5개입니다.

여기 중 제일 작은 수는 1이군요.

1*5=5번을 돌면 1만 사라진 채 나머지는 원래 순서를 유지합니다. 아래에서 보여드립니다.

 

5번을 돌았다 생각해봅시다.

4,2,5,6,1 해서

[3,1,4,5,0] 이겠네요. 사실 0은 뒤에 붙지 못하고 이전에 사라졌을테니

[3,1,4,5]로 줄었겠죠.  (남은 애들은 초기값에서 각각 1씩 줄어든 것에도 주목합니다.)

만약 k=12+5였다면 이대로 제일 첫번째 음식번호가 답이 될겁니다.

 

 

[3,1,4,5]에서 다시 봅시다.

이 배열에서 한 순환(cycle)은 4개입니다.

여기 중 제일 작은 수는 1이군요.

1*4=4번을 돌면 1만 사라진 채 나머지는 원래 순서를 유지합니다.

그런데 남은 k가 1,2,3이라고 생각해봅시다.

 

k가 1이면 3만 2로 줄인채, [1,4,5,2]가 되어 1의 숫자번호가 답입니다.

k가 2이면 3,1만 2,0으로 줄인채, [4,5,2]가 되어 4의 숫자번호가 답입니다.

k가 3이면 3,1,4만 2,0,3으로 줄인채, [5,2,3]이 되어 5의 숫자번호가 답입니다.

k가 4이면 3,1,4,5를 한순환 줄인채, [2,3,5]가 되어 2의 숫자번호가 답입니다.

 

k가 한순환 이상이 못되어 미만이면(k=1~3)

현재 배열에서 첫째다음/둘째다음/셋째다음 애의 번호가 각각 답이 됩니다.

k가 한순환 이상이면, 가장적은수만 날리고 나머지번호가유지.

 

 

규칙성을 찾으셨나요.

 

1. 배열의 한 순환(cycle, 배열크기)을 구한다.

2-1. k가 만약 배열에서 제일 적은수*순환 이상이라면 배열 수 전체는 그 수만큼 줄어들고, 그 수는 사라진다. 나머지 순서는 유지.

2-2. k가 만약 배열에서 제일 적은수*순환 미만이라면 k%cycle번째의 이후의 음식번호를 반환.

 

1 , 2-1 / 1 , 2-1 / 1 , 2-1 / 1 , 2-2 처럼 순환가능하면 빼고 아니면 나머지를 구해서 반환하면 끝입니다.

 

 

class Food {
    int index;
    int time;
    Food (int index, int time) {
        this.index = index;
        this.time = time;
    }
}

위의 순환에서 가장 time이 적은 순으로 정렬하면서 순서정보를 버리게 될테니,

미리 순서정보를 저장해둘 수 있는 클래스로 진행합니다.

 

 

long total = 0;
Comparator<Food> cmp_time = (a,b)->{
    return a.time-b.time;
};
PriorityQueue<Food> que_time = new PriorityQueue<>(cmp_time);
Comparator<Food> cmp_index = (a,b)->{
    return a.index-b.index;
};
PriorityQueue<Food> que_index = new PriorityQueue<>(cmp_index);
for(int i=0;i<food_times.length;i++) {
    total+=food_times[i];
    que_time.add(new Food(i+1,food_times[i]));
}
if(total<=k) return -1;

시간이 적은 애를 우선하는 우선순위큐와, 기존순서 정보대로 우선하는 우선순위큐를 각각 만듭니다.

 

total에는 시작 전 음식들의 총 시간을 더해줍니다.

시간기준으로 오름차순 정렬이 되기 위해 시간 우선순위큐에 몰아줍니다.

 

만약 total이 k보다 작다면 k시간 안에 모든 음식을 다 먹었을테니 -1을 반환합니다.

 

 

long cycle = food_times.length;
long time = 0;
int end = 0;
while(true) {
    long remains = k - time;
    Food min = que_time.peek();
    min.time-=end;
    if(remains>=cycle*min.time) {
        que_time.poll();
        if(remains==cycle*min.time) {
            que_index.addAll(que_time);
            return que_index.peek().index;
        } else {
            time+=min.time*cycle;
            end+=min.time;
            cycle--;
        }
    } else {
        que_index.addAll(que_time);
        remains%=cycle;
        while(true) {
            Food answer = que_index.poll();
            if(remains==0) return answer.index;
            remains--;
        }
    }
}

시간 큐에서 가장 시간이 적은 애의 정보를 가져옵니다.(min)

 

남은시간(remain)이 min.time*cycle 이상이라면? 그 애를 지워야겠죠.

공교롭게 남은시간이 딱 그 순환만큼이면, 바로 원래순서큐에 정보를 넣어서 맨 앞의 애를 데려오면 끝입니다.

남은시간이 그 초과라면 다음 계산을 위해, time에는 min.time*cycle만큼 진행되었고, 모든 수는 min.time만큼 줄어야함을 기록합니다.

 

남은시간(remain)은 k에서 아까 time만큼 진행된걸 빼주면 됩니다.

min을 가져올 때에도 아까 end만큼 빼주는걸 빼고 시작합니다.

여전히 남은시간(remain)이 짱짱하면 위 과정이 반복되고, 미만이라면 cycle의 나머지번째 이후의 음식번호가 나와야합니다.

원래순서큐에 정보를 넣어서 제일 앞의 애를 빼면서 remains를 소모하는데,

remains가 0이었다면 그 애가 제일 앞에서 멈추는 애가 맞으니 그 애의 번호를 반환합니다.

 

 

 

처음에 ArrayList<Food>에 Food를 다 넣고 마지막에 정렬했다가, 기존순서가 필요할 때 다시 기존순서로 정렬하는 것 보다,

우선순위큐에 Food를 넣으면서 바로바로 순서로 정렬되는 것이 빠릅니다. 위의 방식으로는 한꺼번에 전체를 정렬하는 것이 느려서 효율성을 만족하지 못합니다.