정확성은 다 맞는데, 효율성이 떨어진다. 효율성 2번, 3번은 도대체 어떻게 할지 모르겠다. 또한 효율성 통과 기준이 너무 높다. 19ms는 충분히 빠르다. 반드시 이분 탐색으로 풀어야 효율성 테스트를 통과하는 듯 하다. 정확성은 좀 쉬운데, 효율성 테스트가 또 마의 영역이다.
이 문제에서 이분 탐색을 어떻게 활용해야되는지 모르겠다. 너무 많이 진행되어 엎을 수 없어 보완했다.
import java.util.Arrays;
public class Bugdet {
public static void main(String[] args) {
// TODO Auto-generated method stub
Solution sol = new Solution();
int[] budgets = { 120, 110, 140, 150 };
int M = 485;
int answer = 0;
answer = sol.solution(budgets, M);
System.out.println("테스트: " + answer);
}
}
class Solution {
public int solution(int[] budgets, int M) {
//배열을 오름차순 정렬.
Arrays.sort(budgets);
/*
* for (int i = 0; i < budgets.length; i++) System.out.println(budgets[i]);
*/
int t = budgets[budgets.length - 1];
int k = 0;
long answer = 0;
int tempSum = M + 1;
while (tempSum > M) {
answer = t;
tempSum = sum(budgets, k, t);
k = Arrays.binarySearch(budgets, t);
if (k < 0)
k = -(k + 1);
k = budgets.length - k;
if (sum(budgets, k + 1, budgets[budgets.length - k - 1]) >=M)
t = budgets[budgets.length - k - 1];
else
t = t - 1;
} //while
/*
* for (int i = 0; i < budgets.length; i++) { int tempSum = sum(budgets, k, t);
* if (tempSum <= M) { answer = t; break; } else { t = t - 1; k =
* Arrays.binarySearch(budgets, t); if (k < 0) k = -(k + 1); k = budgets.length
* - k; } answer = t; }
*/
return (int)answer;
}
public int sum(int[] budgets, int k, int t) {
int tempSum = 0;
for (int i = 0; i < budgets.length - k; i++) {
tempSum = tempSum + budgets[i];
}
// for (int j = 0; j < k; j++)
// tempSum = tempSum + t;
tempSum = tempSum + k * t;
return tempSum;
}
}
문제를 읽으면 어렵다. 출제자 기준에서 생각한다면, 답이 큰 수임을 보고 수열을 묻는 문제임을 알아야 한다. 이 바닥에서 유명한 피보나치 수열을 묻는 문제라고 눈치채야 한다.
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Solution sol = new Solution();
int n = 0;
for (int i = 0; i < 100; i++) {
n = sol.solution(i);
System.out.println("i는 " + i + ", n은" + n);
}
}
}
class Solution {
public static int solution(int n) {
int a = 1, b = 2, c = 0;
if (n == 0)
return 1;
else if (n < 2)
return n;
for (int i = 2; i < n; i++) {
c = b;
b = (a + b) % 1000000007;
a = c;
}
return b;
}
}
여기에서 배열을 한번에 읽는다. 첫번째 작업 순서를 읽을 때, 모든 작업 순서를 결정할 수 있다. 예제 [[0, 3], [1, 9], [2, 6]] 순서에 마지막 2개를 더 들어온다고 하자. [[0, 3], [1, 9], [2, 6], [24,4], [20,7]].
엑셀 Calc로 그림을 그리면 아래와 같다.
작업A부터 작업E까지 읽을 때, 필요한 작업 시간(checkBar)을 정해야 한다. 이 작업 시간안에 들어오면 작업 시간을 적은 순서대로 정렬한다. 작업 시간을 넘어가면 다음 턴에 정렬해야 한다.
입력을 읽을 때, 24초에 들어온 작업과 20초에 들어온 작업을 결정할 수 있다. 다음과 같이 조정할 수 있다. 24초에 들어온 작업을 20초에 먼저 실행하면 작업D, 작업E를 하는데 총 11초 걸린다.
만약 들어온 순서대로 하면 작업D, 작업E를 14초에 한다. jobs을 읽을 때 뒤쪽 배열에 시간이 빠른 작업을 어떻게 처리할까? 이런 경우를 보면 jobs을 순서대로 읽으면 안된다. 모두 읽어서 빠른 순서대로 정리해야 한다.
하드 디스크가 놀고 있을 때 먼저 들어온 순서대로 한다는 제한이 있다. jobs[][]이 대기열이다. 현재 시각이 0초이고, jobs[0] = [1,2], jobs[1] = [2,5], jobs[2] = [0,4]이라 하자. 위 제한에 따르면 jobs[2]는 조정할 수 없어 실핼할 수 없다. 문제 조건에 jobs[i]는 항상 시작 시각이 늘어난다는 조건을 추가해야 한다. 이 조건이 있었으면 내가 이런 개고생 안했을 수 있었다. 웹은 틀렸다지만 난 맞았다고 정당화시키고 끝낸다.
문제는 이 코드를 웹에 올리면 runtime error로 검증할 수 없다. 우선순위 큐 문제에 너무 많은 시간을 보냈다.
import java.util.Collections;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
// PriorityQueue<Student> ptrTestQ = new PriorityQueue<>();
// while (!sol.getQ().isEmpty())
// System.out.println(ptrTestQ.remove());
// 시작..
int[][] jobs = new int[5][2];
jobs[0][0] = 0;
jobs[0][1] = 3;
jobs[1][0] = 1;
jobs[1][1] = 9;
jobs[2][0] = 2;
jobs[2][1] = 6;
jobs[3][0] = 24;
jobs[3][1] = 4;
jobs[4][0] = 20;
jobs[4][1] = 7;
/*
* System.out.println("Jobs type은"+jobs.getClass().getTypeName());
*
*
*/
Solution sol = new Solution();
int answer = sol.solution(jobs);
System.out.println("여기");
System.out.println("답은 " + answer);
/*
* while (!sol.getQue().isEmpty()) System.out.println("sol.getQue내용은 " +
* sol.getQue().poll()); while (!sol.getQueOffset().isEmpty())
* System.out.println("sol.getQueOffset내용은 " + sol.getQueOffset().poll());
*/
}// void main
} // Main
class Solution {
public int solution(int[][] jobs) {
// 요청 대기시간이 보정된 큐.
PriorityQueue<Job> priqueJobsReversed = new PriorityQueue<>();
PriorityQueue<Job> priqueCheckReversed = new PriorityQueue<>();
// jobs을 class로 입력
for (int i = 0; i < jobs.length; i++) {
Job tmpJob = new Job(jobs[i][0], jobs[i][1]);
// timeStamp 기준 정렬
// setFlag와 세트로 같이 움직여야 됨.
priqueJobsReversed.add(tmpJob);
}
/*
* while (!priqueJobsReversed.isEmpty()) { System.out.println("timeStamp:" +
* priqueJobsReversed.peek().timeStamp + ", Duration: " +
* priqueJobsReversed.peek().duration); priqueJobsReversed.poll(); }
*/
PriorityQueue<Job> priqueJobs = new PriorityQueue<>(priqueJobsReversed.size(), Collections.reverseOrder());
priqueJobs.addAll(priqueJobsReversed);
// 복사..
PriorityQueue<Job> priqueJobsTmp = new PriorityQueue<>(priqueJobs);
boolean overlapped = false;
int startTime = 0;
int endTime = 0;
int preDuration = 0;
int preTimeStamp = 0;
int PolledDuration = 0;
int PolledTimeStamp = 0;
while (!priqueJobsTmp.isEmpty()) {
if (!overlapped) {
startTime = priqueJobsTmp.peek().timeStamp;
endTime = startTime + priqueJobsTmp.peek().duration;
}
preDuration = priqueJobsTmp.peek().duration;
preTimeStamp = priqueJobsTmp.peek().timeStamp;
priqueJobsTmp.poll();
if (!priqueJobsTmp.isEmpty()) {
PolledDuration = priqueJobsTmp.peek().duration;
PolledTimeStamp = priqueJobsTmp.peek().timeStamp;
} //if
else {
PolledTimeStamp = 0;
Job checkBar = new Job(startTime, endTime);
// 시간순으로 정렬
priqueCheckReversed.add(checkBar);
}
if (startTime + preDuration >= PolledTimeStamp) {
// overlapped를 true로 바꾸고, endTime을 연장
overlapped = true;
endTime = endTime + PolledDuration;
} //if
else {
// endTime 연장하지 않음.
// overlapped flag를 다시 false로 변경.
overlapped = false;
// 여기에서 priorityQueue에 넣음.
Job checkBar = new Job(startTime, endTime-1);
// 시간순으로 정렬
priqueCheckReversed.add(checkBar);
} // else
// System.out.println("현재 startTime" + startTime);
// System.out.println("현재 endTime" + endTime);
// Object[] testArry = priqueCheckReversed.toArray();
} // while
/*
* System.out.println("*****여기 확인*******"); while (!priqueJobsTmp.isEmpty())
* System.out.println(priqueJobsTmp.poll());
*/
// 거꾸로 만든 큐 순서를 뒤집음.
PriorityQueue<Job> priqueCheck = new PriorityQueue<>(priqueCheckReversed.size(), Collections.reverseOrder());
priqueCheck.addAll(priqueCheckReversed);
// System.out.println("큐 크기" + priqueCheckReversed.size());
int answer = 0;
PriorityQueue<Job> priqueJobsOder = new PriorityQueue<Job>();
int i = 1;
while (!priqueCheck.isEmpty()) {
// 시작시각 확인.
int startTimeCheck = priqueCheck.peek().timeStamp;
int endTimeCheck = priqueCheck.peek().duration;
int presentTime = priqueCheck.peek().timeStamp;
//check구간의 Jobs을 꺼낸 후, 우선순위 변경하여 다시 넣어줌.
while (!priqueJobs.isEmpty()) {
int tmpTimeStamp = priqueJobs.peek().timeStamp;
int tmpDuration = priqueJobs.peek().duration;
if (startTimeCheck <= tmpTimeStamp && tmpTimeStamp <= endTimeCheck) {
Job orderJob = new Job(tmpTimeStamp, tmpDuration);
orderJob.setFlag(true);
priqueJobsOder.add(orderJob);
priqueJobs.poll();
} // if
else
break;
} //while priqueJobs
//한턴 끝난 후 reverse order로 변경.
PriorityQueue<Job> priqueJobsOderNext = new PriorityQueue<>(priqueJobsOder.size(),
Collections.reverseOrder());
priqueJobsOderNext.addAll(priqueJobsOder);
while (!priqueJobsOderNext.isEmpty()) {
int delay = presentTime - priqueJobsOderNext.peek().timeStamp;
int tmpAnswer = delay + priqueJobsOderNext.peek().duration;
answer = answer + tmpAnswer;
System.out.println("answer = " + answer);
System.out.println("현재시각 = " + presentTime);
System.out.println("duration = " + priqueJobsOderNext.peek().duration);
System.out.println("delay = " + delay);
i++;
presentTime = presentTime + priqueJobsOderNext.peek().duration;
priqueJobsOderNext.poll();
priqueJobsOder.poll();
} //while (priqueHobsOrderNext)
priqueCheck.poll();
} //while priqueCheck
answer = answer / (i - 1);
return answer;
}// int solutions(int[][] jobs)
}
class Job implements Comparable<Job> {
int duration;
int timeStamp;
boolean flag;
// 기본 생성자.
Job() {
this.duration = 0;
this.timeStamp = 0;
this.flag = false;
}
// 생성자 작성.
Job(int timeStamp, int duration) {
this.timeStamp = timeStamp;
this.duration = duration;
this.flag = false;
}
@Override
public int compareTo(Job arg0) {
// TODO Auto-generated method stub
if (!this.flag)
// TimeStamp가 큰 순서대로 poll;
return this.timeStamp < arg0.timeStamp ? 1 : -1;
else
// Duration이 큰 순서대로 poll
return this.duration < arg0.duration ? 1 : -1;
}
@Override
public String toString() { // TODO Auto-generated method stub
return "시각" + this.timeStamp + ", 기간" + this.duration;
}
public void setFlag(boolean flag) {
this.flag = flag;
}
} // Job
