박카스러버

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 저는 해당 문제를 우선순위 큐 두개를 통해서 해결하였습니다. 하나의 우선순위 큐(1)는 작은 것들을 모아두고 맨 꼭대기에는 그 중 제일 큰 값을 가지게 만들었습니다. 다른 하나의 우선순위 큐(2)는 큰 것들을 모아두고 맨 꼭대기에 그 중 제일 작은 값을 가지게 만들었습니다. 우선순위 큐(1)은 비어있거나 현재 들어온 값이 맨 위에 있는 값 보다 작으면 넣어주었고, 나머지의 경우에는..

https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 저는 해당 문제를 LIS를 이용하여 문제를 해결하였습니다. 함수 lis를 이중 for문을 통해 구현하였습니다. 이때 시간복잡도는 O(n^2) 이 됩니다. 함수 listBinarySearch는 이분탐색을 통해 구현하였습니다. 이때는 O(nlog(n))이 됩니다. package BOJ.ETC; import java.io.BufferedReader; import java.io.Inp..

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 저는 해당 문제를 우선순위큐를 이용하여 문제를 해결하였습니다. 배열 리스트를 통해 각각의 기간에 대한 값을 넣어주고 기한에 할 수 있는 과제를 q에 넣어서 점수가 가장 큰 것부터 나오도록 하여 문제를 해결하였습니다. package BOJ.ETC; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util...

https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 저는 해당 문제를 조합을 이용하여 각각의 시험을 사용하는 것과 안하는 것을 dfs로 구현하고 다 뽑았다면 조건들이 맞는지 확인하고 각각의 조건들이 모두 충족한다면 1을 반환하여 가능한 결과값의 개수를 찾았습니다. package BOJ.ETC; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.function.Function; public class BOJ..

https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 저는 해당 문제를 sum이라는 배열을 통해 이전까지의 요소들의 합을 구하였습니다. 출력은 해당 각 인덱스에 대한 sum의 차를 출력하여 해결하였습니다. package BOJ.ETC; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util..

https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 저는 해당 문제를 BFS를 이용해서 문제를 해결하였습니다. 저는 낮에는 벽에 있으면 뚫고 없으면 해당 점으로 가고, 밤에는 뚫려있으면 가고 벽이라면 해당 좌표를 다시 집어 넣어 해당 좌표를 낮에 뚫고 가도록 구현하였습니다. (낮에도 제자리에 있는 로직을 구현하게 된다면 시간초과가 나오는 것 같습니다.) 따라서 visited배열도 3차원으로 구성하였습니다. vis..

https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 저는 해당 문제를 map을 통해서 해결하였습니다. map을 통해 해당 종류가 몇개있는지를 판단하였습니다. 그리고 각각의 종류의 개수를 곱하였습니다. 이때 각각의 종류는 없는 것도 생각하여 +1을 하였습니다. 마지막으로 다 없는 경우도 존재하기 때문에 -1을 하였습니다. package BOJ.ETC; imp..

https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 저는 해당 문제를 이분탐색으로 문제를 해결하였습니다. 문제는 이분탐색 API를 쓸때 문제가 있었습니다. 같은 수가 존재할 때 어떤 값의 인덱스를 줄 지 모른다는 것입니다. 그래서 저는 찾았을 때는 제일 낮은 인덱스의 값이 나오도록 구현하였습니다. package BOJ.ETC; import java.io.BufferedReader; import j..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 저는 해당 문제를 위상정렬과 우선순위 큐를 이용해서 문제를 해결하였습니다. 위상정렬을 사용하면서 Queue를 우선순위큐를 이용해 낮은 숫자가 먼저 나오도록 하였습니다. package BOJ.ETC; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; im..

https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 저는 해당 문제를 위상정렬을 이용하여 문제를 해결하였습니다. 저는 각각의 노드에 사직 시간을 구하였습니다. 각각의 노드와 연결된 부분들에서 끝나는 시간의 최대 값을 구해 그 노드에 가장 나중의 값을 구하였습니다. 그리고 각각의 시작시간에 각각의 건물 짓는 시간을 더해 결과값을 구하였습니다. package BOJ.ETC; import java.io.BufferedReader; import..