Melody Coding

Silver III문제(출처: https://www.acmicpc.net/problem/17952) 문제 풀이  Stack을 사용해서 0이 입력될 때는 stack에서 값을 pop해와 시간을 -1 시켜 다시 stack에 넣어주며 만약 시간이 1이라면 과제를 끝낼 수 있으므로 점수를 총합에 더해준다. 만약 1이 입력될 때는 stack에 값을 넣어준다.   my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Stack;import java.util.StringTokenizer;public class _17952_ { // 과제는 끝나지 않아..

Silver IV문제(출처: https://www.acmicpc.net/problem/3986) 문제 풀이  Stack을 사용해서 A끼리 또는 B끼리 쌍을 지어 연달아 있는지 확인한다.   my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Stack;public class _3986_ { // 좋은 단어 public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.i..

Gold III문제(출처: https://www.acmicpc.net/problem/2812) 문제 풀이  Stack을 사용해서 다음 숫자가 현재 숫자보다 크다면 현재 숫자를 stack에서 pop 해준다. 예를 들어 예제에서 주어진 입력이라면4 21924위의 그림과 같이 처음에 1을 stack에 넣어준다. 그다음 값이 9일 때 stack에 들어있는 값이 1 이므로 1을 빼고 9를 넣으면 더 큰 값을 만들 수 있다. 2는 9보다 작으므로 stack에 넣어준다. 마지막으로 4가 들어올 때 2보다 크므로 2를 빼주고 4를 넣어준다.   my solution (Java)import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOExc..

Silver I문제(출처: https://www.acmicpc.net/problem/2841) 문제 풀이  기타 줄마다 stack을 만들어서 눌러야 하는 프렛보다 전에 누른 프렛 번호가 큰지 작은지에 따라 판단하여  문제를 해결했다.   my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Stack;import java.util.StringTokenizer;public class _2841_ { // 외계인의 기타 연주 public static void main(String[] args)..

Gold IV문제(출처: https://www.acmicpc.net/problem/23294) 문제 풀이  Deque 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.ArrayDeque;import java.util.Deque;import java.u..

Silver IV문제(출처: https://www.acmicpc.net/problem/28279) 문제 풀이  Deque를 사용해서 문제를 해결했다.   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.ArrayDeque;import java.util.Deque;import java.util.StringTokenizer;public class _28279_ { // 덱 2 public static void main(St..

Gold IV문제(출처: https://www.acmicpc.net/problem/2617) 문제 풀이  ArrayList 2개를 사용해서 n번 구슬보다 무거운 구슬 번호를 저장하고, n번 구슬보다 가벼운 구슬 번호를 저장한다.그 후 n번 구슬보다 무거운 구슬이 몇 개인지, 가벼운 구슬이 몇 개인지 dfs를 활용하여 구한다. 각 개수가 총 구슬의 개수의 절반이 넘으면 무게가 중간이 될 가능성이 없다.   my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;pu..

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 처음부터 끝까지 탐색하며 연산..