https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 이번 문제는 HashMap 자료구조를 사용하여 문제를 해결했다. 주어진 N크기의 배열을 만들고, 입력값을 배열에 담은 후 그 배열을 복사한 새로운 배열을 만든다.(rank 배열) 그리고 rank 배열을 오름차순으로 정렬한 후, 순차적으로 반복문을 돌리며 map에 좌표 X 값과 그 값에 대한 순위 값을 더해준다. (중복값은 허용하지 않아야 한다는 것..
https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 이번 문제는 나이와 이름을 저장하고 입력 순서에 따라 정렬을 해야하는 문제이다. 여러 가지 방법이 있겠지만, 나이와 이름을 저장하기 위한 객체를 생성하고 그 객체를 정렬하면 손쉽게 해결할 수 있다. 그리고 객체에 저장된 변수들을 출력하기 위해 Object 클래스의 메서드 toString() 을 오버라이딩하였다. import java.io.BufferedReader; import java.io.IOExc..
https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 직전 문제와 거의 비슷한 문제이지만 문제를 살펴보면 단어의 중복 제거라는 고민해야 할 부분이 있다. 이를 위해 자바 8 이후부터 권장되는 Stream을 사용해 중복을 제거해 보자. Stream에서 제공되는 API를 사용하기 위해서는 먼저 String[] 배열을 Stream 객체로 변환시켜 주어야 한다. 그리고 Stream API를 사용하여 중복을 제거하고 다시 String[] 배열로 변..
https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 이번 문제는 좌표 정렬하기1 에서 조금 더 응용한 문제이다. 기존에는 x 좌표가 증가하는 순으로 정렬하였지만, y좌표가 증가하는 순으로 조건을 바꾸어 적용하면 쉽게 풀 수 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader..
https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 이번 문제는 Comparator인터페이스의 compare() 메서드를 오버라이딩하여 Arrays.sort를 사용하면 풀 수 있는 문제이다. Arrays.sort()는 매개변수로 정렬 조건을 추가할 수 있는데 이 정렬 조건을 우리 입맛에 맞게 compare() 메서드를 오버라이딩해 추가해준다. 코드는 다음과 같다. import java.io.IO..
https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 couning 정렬을 사용하면 아주 쉽게 풀 수 있는 문제이다. 각 자리수를 값으로 입력받기 위해 정수를 입력받아 10으로 나누어 나머지값을 사용하는 방법이 있고, 문자열로 값을 입력받아 각 문자의 아스키값을 통해 정렬해도 된다. 나는 문자열을 입력받아 아스키값을 이용해 각 자리수 값을 구하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; publi..
https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 이번 문제는 수의 범위가 4000을 넘지 않기 때문에 자바 API에서 제공하는 정렬 알고리즘으로도 풀 수 있는 문제이다. 하지만 보다 빠른 결과를 위해 counting sort를 적용해 보겠다. findAvg() 첫째로 산술평균값을 구하는 메서드 findAvg() 를 보면, 문제에 소수점 이하 첫째 자리에서 반올림한 값을 출력해야한다고 명시되어있다. 따라서 자바 API 에서 제공하는 소수 첫째 자리 반올림해 주..
https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 이전 문제에 이어 counting sort만 안다면 쉽게 풀 수 있는 문제이다. 따로 설명이 필요하지 않은 쉬운 문제이니 코드를 보고 이해해보자. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[]..
