Melody Coding

Gold III문제(출처: https://www.acmicpc.net/problem/17616) 문제 풀이  입력을 받을 때 ArrayList 2개를 사용해서 자신보다 더 잘한 사람과 자신보다 더 못한 사람을 저장한다.dfs를 활용하여 자신보다 잘 한 사람의 수와 자신보다 못한 사람의 수를 구해 가능한 가장 높은 등수와 가능한 가장 낮은 등수를 구한다.   my solution (Java)import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.ArrayLis..

Gold III문제(출처: https://www.acmicpc.net/problem/12764) 문제 풀이  우선순위 큐 2개와 ArrayList, boolean 배열을 사용해서 문제를 해결했다. 우선순위 큐 a에는 컴퓨터 이용 시작 시간과 종료 시간을 입력받아 저장하여 우선순위를 이용 시작 시간이 빠른 순으로, 시작 시간이 같다면 종료 시간이 빠른 순으로 정렬했다.우선순위 큐 b에는 컴퓨터 종료 시간과 컴퓨터 번호를 저장하여 우선순위를 종료 시간이 빠른 순으로, 종료 시간이 같다면 번호가 빠른 순으로 정렬했다. 문제에서 비어있는 자리 중에서 번호가 가장 작은 자리에 앉는 것이 규칙이라 했으므로 먼저 다음 사람이 들어왔을 때 종료되는 컴퓨터들을 우선순위 큐 b에서 poll 해준다. 그 후에 비어있는 자리..

Silver III문제(출처: https://www.acmicpc.net/problem/18917) 문제 풀이  문제에서 배열을 사용한다고 해서 당연하게 ArrayList를 사용해서 문제를 해결했었다.하지만 최대 500000번의 add와 remove를 수행하면 시간초과가 발생한다는 것을 알게 되었다. 또한, sum과 xor 연산을 값이 들어오고 나갈 때마다 계산해 주면 따로 값들을 저장할 공간이 필요 없었다.  * 1000000000을 최대 500000번 더한다고 하면 Integer 범위를 벗어나므로 long을 써야 한다.  시간초과 코드 (Java)더보기처음에는 값이 제거될 때 xor 연산을 어떻게 해야 하는지 몰라 xor 연산을 위해 4가 입력될 때마다 ArrayList 처음부터 끝까지 탐색하며 연산..

Gold III문제(출처: https://www.acmicpc.net/problem/1379) 문제 풀이  우선순위 큐 2개를 사용해서 문제를 해결했다.우선순위 큐 a에는 [강의 시작 시간, 강의 끝나는 시간, 강의 번호] 배열을 저장해서 우선순위를 강의 시작시간이 빠른 순으로, 시작 시간이 같다면 끝나는 시간이 빠른 순으로 정렬했다.다른 우선순위 큐 b에는 [강의 끝나는 시간, 강의실 번호]를 저장해서 우선순위를 강의 끝나는 시간이 빠른 순으로, 강의실 번호가 작은 순으로 정렬했다. a의 값을 순서대로 b에 저장하는데, b의 젤 앞에 값의 강의 끝나는 시간보다 a에서의 강의 시작 시간이 같거나 크다면 b의 맨 앞의 강의가 끝난 후에 그 강의실을 사용할 수 있다는 뜻이므로 b의 값을 poll 한 후 저장..

Gold V문제(출처: https://www.acmicpc.net/problem/1374) 문제 풀이  우선순위 큐 2개를 사용해서 문제를 해결했다.우선순위 큐 하나에는 [강의 시작 시간, 강의 끝나는 시간] 배열을 저장해서 우선순위를 강의 시작시간이 빠른 순으로, 시작 시간이 같다면 끝나는 시간이 빠른 순으로 정렬했다.다른 우선순위 큐에는 강의 끝나는 시간을 저장한다. 이때, 이 우선순위 큐 젤 앞에 있는 값이 새로 들어오는 값 보다 작거나 같다면 강의가 끝난 후 다음 회의를 시작할 수 있는 것이므로 poll해준 후 넣어준다.   my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputSt..

Gold V문제(출처: https://www.acmicpc.net/problem/19598) 문제 풀이  우선순위 큐 2개를 사용해서 문제를 해결했다.우선순위 큐 하나에는 [회의 시작 시간, 회의 끝나는 시간] 배열을 저장해서 우선순위를 회의 시작시간이 빠른 순으로, 시작 시간이 같다면 끝나는 시간이 빠른 순으로 정렬했다.다른 우선순위 큐에는 회의 끝나는 시간을 저장한다. 이때, 이 우선순위 큐 젤 앞에 있는 값이 새로 들어오는 값 보다 작거나 같다면 회의가 끝난 후 다음 회의를 시작할 수 있는 것이므로 poll해준 후 넣어준다. * 11000번 강의실 배정 문제와 거의 똑같은 문제였다.https://melody-coding.tistory.com/367 [Baekjoon] 11000_강의실 배정Gold ..

Gold V문제(출처: https://www.acmicpc.net/problem/11000) 문제 풀이  우선순위 큐 a에 [수업 시작 시간, 끝난 시간] 배열로 저장한다. 이때 우선순위는 수업 시작시간이 빠른 순으로, 시작 시간이 같다면 끝나는 시간이 빠른 순으로 정렬한다. 우선순위 큐 a 앞에 들어있는 값부터 뽑아내어 또 다른 우선순위 큐 b에 끝나는 시간만 저장한다. 이때, b 젤 앞에 들어있는 값이 저장하려는 값 보다 작거나 같다면 수업이 끝난 후 다음 수업을 시작할 수 있으므로 b에서 poll 한 후 넣어준다.   my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamR..

Silver III문제(출처: https://www.acmicpc.net/problem/24511) 문제 풀이  Queue와 Stack을 사용해서 문제를 해결했다.Stack은 값을 넣은 것을 바로 pop 하므로 자료구조가 Stack인 것은 고려하지 않기로 했다.  my solution (Java)import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.LinkedList;import java.util.Queue;import java.util.Stack;impo..

Silver V문제(출처: https://www.acmicpc.net/problem/26042) 문제 풀이  Queue를 사용해서 학생이 대기할 때마다 대기하는 학생 수와 맨 뒤에 줄 서 있는 학생 번호를 비교하여 답을 찾는다.  my solution (Java)import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class ..

Silver I문제(출처: https://www.acmicpc.net/problem/28107) 문제 풀이  우선순위 큐 2개를 사용해서 문제를 해결했다.1) 손님의 주문 목록 저장하는 우선순위 큐 [초밥 종류, 손님 번호]2) 요리되는 초밥 종류 저장하는 우선순위 큐  my solution (Java)import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.Comparator;import java.util.PriorityQueue;import java.uti..