문제 출처 : 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.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의 자바(Java)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 코딩테스트에서 가장 많이 출제되는 Top 10 Topic을 다루고 있습니다. 주제와 연동하여 기초문제부터 중급문제까지 단계적으로 구성 www.inflearn.com 문제 8 : 임의의 N개 숫자 입력으로 주어진다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 ..
문제 출처 : 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..
문제 출처 : https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 ) 객체 간 비교를 가능하게 해주는 Comparable 인터페이스 이용해서 비교해주면 된다. 여기선 사전식 오름차순 정렬이라 Comparable 인터페이스를 사용했지만, String 사전 역순이였을 경우에는 Comparable이 아니라 Comparator를 사용하는 것이 좋을 것이다. 소스코드 ) import java.util.*; class Words impleme..
