import java.util.PriorityQueue;
public class PccpTest1_4 {
// PCCP 모의고사 1회 4번 운영체제
public static long[] solution(int[][] program) {
long[] answer = {};
long callTime = 0; // OS 호출 시각
int runningTime = 0; // OS 수행 시간
long totalRunningTime = 0; // 전체 OS 종료까지 총 소요 시간
long blankTime = 0; // OS가 실행중이지 않은 시간
answer = new long[11]; // 크기 11 고정
// STEP 1. ORDER BY 호출 시각, 점수인 우선순위 큐 만들기(전체 OS 담을 우선순위 큐)
PriorityQueue<Os> osQ = new PriorityQueue<>();
// STEP 2. 1번 우선순위 큐에 program 배열의 OS 담기
for (int i = 0; i < program.length; i++) {
osQ.add(new Os(program[i][0], program[i][1], program[i][2]));
}
// STEP 3. ORDER BY 점수, 호출 시각인 우선순위 큐 만들기(호출 시각 지난 OS 담을 우선순위 큐) => 호출 시각이 지난 OS들은 점수가 낮은 순서대로 실행된다.
PriorityQueue<WaitingOs> waitingOsQ = new PriorityQueue<>();
// STEP 4. 시간 계산에 사용될 임시 Os, WaitingOs 변수 선언
Os tempOs = null;
WaitingOs tempWaitingOs = null;
// STEP 5. 제일 처음 실행될 OS 꺼내기
Os os = osQ.poll();
callTime = os.getCallTime();
runningTime = os.getRunningTime();
blankTime = callTime; // 0초에 바로 실행되지 않는 경우도 있을 수 있기 때문에 blankTime 계산해주기
totalRunningTime += blankTime; // 총 소요 시간에 blankTime 더하기
totalRunningTime += runningTime; // 총 소요 시간에 수행 시간 더하기
// STEP 6. 두 개의 큐가 모두 비워질 때까지 반복
while (!osQ.isEmpty() || !waitingOsQ.isEmpty()) { // 두 개의 큐 중 어느 하나라도 OS가 담겨있다면 반복
// osQ에 OS가 담겨있다면
if (!osQ.isEmpty()) {
// 실행 중인 OS로 인해 호출 시각이 지난 OS가 있다면 waitingOsQ(호출 시각이 지난 OS들만 모여있으며, 이 경우 점수가 낮은 OS가 우선적으로 실행될 수 있게 배치)로 보내기
if (totalRunningTime >= osQ.peek().getCallTime()) {
tempOs = osQ.poll();
waitingOsQ.offer(new WaitingOs(tempOs.getGrade(), tempOs.getCallTime(), tempOs.getRunningTime()));
continue; // 더 있다면 반복 수행되도록 처리
}
// 이 곳으로 내려왔다는 것은 osQ에 OS가 남아 있으며, waitingOsQ로 보낼 조건에 부합하는 OS가 없다는 것을 의미
// 여기서 waitingOsQ가 비어있다면 => 즉, 다음 실행될 osQ의 OS가 바로 이어서 실행되지 않기 때문에 waitingOsQ에 보내지 못한 거라면
if (waitingOsQ.isEmpty()) {
// blankTime과 runningTime 계산
tempOs = osQ.poll();
blankTime = (tempOs.getCallTime() - totalRunningTime); // blankTime이 있다는 것을 의미하므로 blankTime 계산해주기
totalRunningTime += (blankTime + tempOs.getRunningTime()); // 총 소요 시간에 blankTime과 수행 시간 더하기
}
}
// waitingOsQ에 OS가 담겨있다면
if (!waitingOsQ.isEmpty()) {
tempWaitingOs = waitingOsQ.poll();
answer[tempWaitingOs.getGrade()] += (totalRunningTime - tempWaitingOs.getCallTime()); // 해당 점수의 대기 시간 더하기
totalRunningTime += tempWaitingOs.getRunningTime(); // 총 소요 시간에 해당 점수의 수행 시간 더하기
}
}
answer[0] = totalRunningTime; // answer[0]에는 총 소요 시간을 넣어준다.
for (int i = 0; i < answer.length; i++) {
System.out.print(answer[i] + " ");
}
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] program = {{2, 0, 10}, {1, 5, 5}, {3, 5, 3}, {3, 12, 2}}; // 점수, 호출 시각, 수행 시간 // 20, 5, 0, 16, 0, 0, 0, 0, 0, 0, 0 // 종료 시각, 점수 1 ~ 10 총 대기 시간
// int[][] program = {{3, 6, 4}, {4, 2, 5}, {1, 0, 5}, {5, 0, 5}}; // 19 0 0 4 3 14 0 0 0 0 0
// int[][] program = {{3, 6, 4}, {4, 2, 5}, {1, 0, 5}, {4, 1, 10}, {5, 0, 5}, {2, 0, 8}}; // 37 0 5 7 41 32 0 0 0 0 0
System.out.println(solution(program));
}
}
public class Os implements Comparable<Os> { // 호출 시각, 점수 기준
private int grade = 0; // 점수
private long callTime = 0; // 호출 시각
private int runningTime = 0; // 수행 시간
public Os(int grade, long callTime, int runningTime) {
this.grade = grade;
this.callTime = callTime;
this.runningTime = runningTime;
}
public int getGrade() {
return this.grade;
}
public long getCallTime() {
return this.callTime;
}
public int getRunningTime() {
return this.runningTime;
}
@Override
public int compareTo(Os otherNode) { // ORDER BY callTime, grade
// TODO Auto-generated method stub
if (this.callTime == otherNode.callTime) { // callTime이 같을 경우
if (this.grade - otherNode.grade >= 0) { // grade 기준 오름차순 정렬
return 1;
} else {
return -1;
}
} else { // callTime이 같지 않을 경우
if (this.callTime - otherNode.callTime >= 0) { // callTime 기준 오름차순 정렬
return 1;
} else {
return -1;
}
}
}
}
public class WaitingOs implements Comparable<WaitingOs> { // 점수, 호출 시각 기준
private int grade = 0; // 점수
private long callTime = 0; // 호출 시각
private int runningTime = 0; // 수행 시간
public WaitingOs(int grade, long callTime, int runningTime) {
this.grade = grade;
this.callTime = callTime;
this.runningTime = runningTime;
}
public int getGrade() {
return this.grade;
}
public long getCallTime() {
return this.callTime;
}
public int getRunningTime() {
return this.runningTime;
}
@Override
public int compareTo(WaitingOs otherNode) { // ORDER BY grade, callTime
// TODO Auto-generated method stub
if (this.grade == otherNode.grade) { // grade가 같을 경우
if (this.callTime - otherNode.callTime >= 0) { // callTime 기준 오름차순 정렬
return 1;
} else {
return -1;
}
} else { // grade가 같지 않을 경우
if (this.grade - otherNode.grade >= 0) { // grade 기준 오름차순 정렬
return 1;
} else {
return -1;
}
}
}
}
제출 후 채점하기에서 실패로 뜨는 테스트 케이스들이 많았고, solution 메소드에 문제가 있는 것인지 여러 차례 확인했다.
결론은 solution 메소드에는 문제가 없었고 WaitingOs의 정렬 기준을 '점수'로만 했던 것이 원인이었다.
호출 시각이 지난 OS들은 '점수'가 낮은 순서대로 실행되는 것이 맞지만, '호출 시각' 또한 고려해야 했다는 것을 뒤늦게
깨닫고 WaitingOs의 정렬 기준을 '점수', '호출 시각'으로 변경하여 문제를 해결하였다.
public class PccpTest1_2 {
// PCCP 모의고사 1회 2번 체육대회
public static int[][] studentAbility;
public static int studentCnt = 0;
public static int sportsCnt = 0;
public static int[] exceptCmbMax;
public static int getMaxAbility(int studentCmbNum, int sportsIndex) { // studentCmbNum : 선택된 학생 또는 학생들의 조합, sportsIndex : 종목 // sportsIndex가 0일 때 1명의 학생 조합, sportsIndex가 1일 때 2명의 학생 조합, sportsIndex가 2일 때 3명의 학생 조합 생김
int maxScore = 0;
int score = 0;
int checkNum = 0;
if (sportsIndex == sportsCnt) { // sportsIndex 0 ~ 2까지만 체크하도록 함
return 0;
}
if (exceptCmbMax[studentCmbNum] == 0) { // exceptCmbMax[studentCmbNum] 값이 0일 경우에만 체크하도록 함
for (int i = 0; i < studentCnt; i++) { // 0 ~ 4
checkNum = (1 << i); // 1, 2, 4, 8, 16
if ((studentCmbNum & checkNum) > 0) { // 앞서 선택된 학생이라면 continue
continue;
}
score = studentAbility[i][sportsIndex] + getMaxAbility((studentCmbNum | checkNum), sportsIndex + 1); // 반복문을 돌며 선택되지 않은 학생들의 다음 종목 점수를 확인(종목은 0, 1, 2 순서로 고정 => 학생에 대한 선택만 고려)
if (score > maxScore) {
maxScore = score;
}
exceptCmbMax[studentCmbNum] = maxScore; // 최종 : {210, 170, 170, 100, 170, 100, 100, 0, 130, 100, 100, 0, 100, 0, 0, 0, 100, 70, 70, 0, 70, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0}
}
}
return exceptCmbMax[studentCmbNum];
}
public static int solution(int[][] ability) {
int answer = 0;
studentCnt = ability.length; // 학생 수 // 5
sportsCnt = ability[0].length; // 종목 수 // 3
exceptCmbMax = new int[1 << studentCnt]; // 2 ^ 5 크기의 배열 생성
studentAbility = ability;
answer = getMaxAbility(0, 0);
// exceptCmbMax[0] : 전체에서 고르는 경우 중 최대인 값(studentAbility[0][0] + exceptCmbMax[1] OR studentAbility[1][0] + exceptCmbMax[2] OR studentAbility[2][0] + exceptCmbMax[4] OR studentAbility[3][0] + exceptCmbMax[8] OR studentAbility[4][0] + exceptCmbMax[16])
// exceptCmbMax[1] : (0, 0) 고른 후 나머지 고르는 경우 중 최대인 값(studentAbility[1][1] + exceptCmbMax[3] OR studentAbility[2][1] + exceptCmbMax[5] OR studentAbility[3][1] + exceptCmbMax[9] OR studentAbility[4][1] + exceptCmbMax[17])
// exceptCmbMax[2] : (1, 0) 고른 후 나머지 고르는 경우 중 최대인 값
// exceptCmbMax[3] : (0, 0), (1, 1) 고른 후 나머지 고르는 경우 중 최대인 값(studentAbility[2][2] OR studentAbility[3][2] OR studentAbility[4][2])
// exceptCmbMax[4] : (2, 0) 고른 후 나머지 고르는 경우 중 최대인 값(studentAbility[0][1] + exceptCmbMax[5] OR studentAbility[1][1] + exceptCmbMax[6] OR studentAbility[3][1] + exceptCmbMax[12] OR studentAbility[4][1] + exceptCmbMax[20])
// exceptCmbMax[N] : N은 선택된 학생 또는 학생들의 조합, exceptCmbMax[N]는 그 조합을 제외했을 때 최대가 되는 값 // 종목은 0, 1, 2 순서로 고정했기 때문에 학생에 대한 선택만 고려
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] ability = {{40, 10, 10}, {20, 5, 0}, {30, 30, 30}, {70, 0, 70}, {100, 100, 100}};
System.out.println(solution(ability)); // 40(0, 0) + 100(4, 1) + 70(3, 2) // 210
}
}
import java.util.*;
public class PccpTest1_1 {
// PCCP 모의고사 1회 1번 외톨이 알파벳
public static String solution(String input_string) {
String answer = "";
char tempChar;
int tempCnt = 0;
int repeatCnt = 0;
Queue<Character> q = new LinkedList<>();
HashMap<Character, Integer> originHm = new HashMap<>();
HashMap<Character, Integer> repeatChkHm = new HashMap<>();
ArrayList<Character> list = new ArrayList<>();
for (int i = 0; i < input_string.length(); i++) {
q.offer(input_string.charAt(i)); // e d e a a a b b c c d
}
while (!q.isEmpty()) {
tempChar = q.poll();
if (originHm.get(tempChar) == null) { // originHm에는 key값으로 알파벳이, value값으로 해당 알파벳의 총 카운트가 들어갈 것이다.
originHm.put(tempChar, 1);
repeatChkHm.put(tempChar, 1);
} else {
tempCnt = originHm.get(tempChar) + 1;
originHm.put(tempChar, tempCnt);
}
if (!q.isEmpty()) { // AABBAA일 경우 // originHm A : 4, B : 2 // repeatChkHm A : 3, B : 2
if (tempChar == q.peek()) { // 연속되는 알파벳이라면
repeatCnt = repeatChkHm.get(tempChar) + 1;
repeatChkHm.put(tempChar, repeatCnt);
}
}
}
for (char key : originHm.keySet()) {
if (originHm.get(key) != repeatChkHm.get(key) && originHm.get(key) > 1) {
list.add(key);
}
}
if (list.size() == 0) {
answer = "N";
} else {
Collections.sort(list);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < list.size(); i++) {
sb.append(list.get(i));
}
answer = sb.toString();
}
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String input_string = "edeaaabbccd";
System.out.println(solution(input_string));
}
}
