https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net [풀이] 처음에는 ArrayList를 선언해서 수업의 끝나는 시간을 기준으로 정렬을 하여 add / remove 메소드를 통해 해결하려했습니다. 이렇게 푸니..시간초과가 발생했습니다. 우선순위큐를 구현하여 정렬을 이용한 문제였습니다. 우선순위큐에는 끝나는 시간을, 배열에는 시작 시간을 기준으로 정렬을 했습니다. 첫 수업은 우선순위큐를 기본적으로 넣어줍니다. 이후, 반복문에서 만약, 시작시간이 우선순위큐의 끝나는 시간과 비교하여 시작시간이 더 작..
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net [풀이] 'ㅜ'자 모양은 DFS로 탐색하는 것이 불가능 하지만, 그 외의 모양은 DFS로 탐색이 가능합니다. 그렇기에, 'ㅜ'자는 별개의 메소드로 값을 구하고, 다른 모양들은 DFS를 통해 값을 구했습니다. total 변수가 4일 경우에는 탐색을 멈추도록 했습니다. 별개의 메소드로 'ㅜ'를 구할 때 모양이 돌아가는 경우도 고려해서 조건문을 구현했습니다. N과 M , x와 y에 헷갈리지 않도록 메소..
https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net [풀이] BFS를 이용해서 풀었습니다. 시작점을 큐에 넣은 이후, dis 배열에 거리에 대한 최소값을 저장하면서 계산합니다. 입력값을 받을 때 1이 있는 곳이 아기상어가 있는 칸이므로, 처음에 이 부분에 대해서만 큐에 담습니다. [코드] import java.io.BufferedReader; import java.io.IOException; import java.io...
https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net [풀이] dfs를 이용한 브루트포스형의 문제입니다. 처음 입력 받는 값은 숫자를 재배치 해야하므로, 값을 하나씩 저장하기 위해 배열로 선언, 비교가 되는 변수 b는 정수형으로 선언합니다. 출력해야하는 answer 변수는 -1로 초기화합니다. dfs를 구현할 때 배열의 해당 인덱스를 사용했는지 파악하기 위해 visited라는 boolean형의 배열 변수를 선언했습니다. dfs..
https://www.acmicpc.net/problem/10798 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net [풀이] 구현과 관련된 문제였습니다. 2차원 char형 배열의 인덱스에 대한 이해가 필요한 문제였습니다. null에 해당하는 아스키코드인 '\0' 그리고, 공백을 구분할 수 있어야 했습니다. [코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class M..
https://www.acmicpc.net/problem/1527 1527번: 금민수의 개수 첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] 기본적으로 반복문을 하면, 메모리 초과가 발생합니다. 그렇기에 저는 재귀적인 방법을 이용해서 문제를 접근했습니다. 4와 7이 있는 숫자는 4와 7에 10을 곱한후 각 숫자를 더한 값을 확인해야 합니다. 입력 숫자가 범위가 크기에 long형으로 선언했습니다. [코드] import java.io.BufferedReader; import java.io.IOException; import ja..
