문제 출처 : https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 : 풀이 : 항상 그렇듯이 억지로 풀 수는 있다. for문으로 돌리면 0에 가장 가까운 값 찾을 수 있다. 시간초과가 날뿐.. 투포인터를 잡으면 된다. 잡아도 되나? 어떻게 O(N)으로 0에 가장 가까운 두 값만을 서치할 수 있지? 일단 Arrays.sort(arr) 해주고 투포인터의 국룰(?) lt와 rt를 양 끝으로 잡아본다. 쓸모없는 움직..
문제 출처 : https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 : 풀이 : 직접 뒤집는 것 보다 Deque를 이용해 Reverse 유무를 체크하며 앞과 뒤에서 삭제하는 것이 좋다. 소스코드 : import java.util.*; import java.io.*; public class Main { public StringBuilder solution(String funcArr, int arrSize, Deque dq) { StringBuilder sb = new StringBuilder(); bo..
문제 출처 : https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 : 풀이 : 입력받은 원래 값들의 배열을 그대로 저장하는 arr 배열, 오름차순으로 정렬할 sortArr 배열을 만들고 두 배열에 입력받는 좌표를 저장한다. 이후 sortArr 배열을 오름차순 정렬하고, 압축 전의 값과 압축 후의 값을 각각 key와 value로 저장하는 HashMap을 생성한다. 그리고 arr 배열에서 for문..
문제 출처 : https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 : 풀이 : Parametric Search 알고리즘 통해 간단하게 문제를 해결할 수 있다. 우선 Arrays.sort(arr) 하면 1 2 4 8 9 lt = 1 , rt = 9(arr에서 최대값) , mid = 5 mid = 5로 잡은 것은 가장 가까운 두 공유기 최대 거리가 5라고 가정하고 넣어보는 것이다. 따라서 cou..
문제 출처 : https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 : 풀이 : Parametric Search 알고리즘으로 간단히 해결되는 문제인데 왜 정답률이 25% 밖에 안되는걸까 생각하며 문제를 제출하였지만 틀려버렸다. 문제를 다시보니 자료형의 범위를 초과해서 발생한 문제였다. 자료형의 범위를 잘 생각하자는 교훈을 얻게 되었다. 자바 소스코드 : import java.util.*; public cl..
문제 출처 : https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 : 풀이 : 1부터 n까지의 수를 스택에 넣었다가 뽑으면, 즉 stack.push()되고 stack.pop()되면 수열로 들어간다는 것이다. 1부터 n까지의 수를 push()와 pop() 해서 입력된 수열로 만드는 것이니 우선 입력된 수열을 int[] arr로 저장하고 n와 arr 배열을 solu..
문제 출처 : 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 문제 : 풀이 : T만큼 반복하는 반복문 안에서 N, M과 각 배열 입력받는다. 그리고 각 케이스마다 정답 리턴하는 함수 작성하고 사용한다. arrA, arrB 정렬한 다음 arrA 기준으로 for문 돌리고 그 안에서 이분 탐색 알고리즘 이용해 arrA[i]보다 작은 arrB 개수들 계산해서 구하고자 하는 값 리턴시킨다. 소스코드 ..
문제 출처 : https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 출처2 : https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 출처3 : htt..
