JAVA - 백준 [BAEK JOON]/정렬
[백준] 18870번 : 좌표 압축 - JAVA [자바]
[백준] 18870번 : 좌표 압축 - JAVA [자바]
2021.12.11https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 이 번엔 단계별 풀이가 아닌 다른 문제를 한 번 풀어보려 한다. 알고보니 정렬 파트에 추가된 문제였다.. 알고리즘 [접근 방법] 위 문제를 보니 좌표 압축이라고는 되어있긴 하지만, 정확히는 좌표 압축 알고리즘을 활용한 ranking list를 만드는 문제라고 보는 것이 좀 더 직관적이지 않나.. 생각을 한다. 여튼, 위와 같은 문제 부류를 c..
[백준] 10814번 : 나이순 정렬 - JAVA [자바]
[백준] 10814번 : 나이순 정렬 - JAVA [자바]
2020.06.20www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 � www.acmicpc.net 문제 ※ 주의할 점 나이순 정렬을 기준으로 하되, 나이가 같을경우 주어진 입력순으로 정렬한다. 알고리즘 [접근 방법] 이 문제의 경우 정말 다양한 방법이 있다. 1. 먼저 가장 간단한 방법은 String[][] 2차원 배열을 통해 각 배열에 나이와 이름을 저장한 뒤, 나이 순으로 정렬하는 방법이다. 이때 정렬방법은 Arrays.sort()에 Comparator 의 compare 메소드를 구현하여 사용자 정렬을 사..
[백준] 1181번 : 단어 정렬 - JAVA [자바]
[백준] 1181번 : 단어 정렬 - JAVA [자바]
2020.06.19www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 이전 좌표정렬하기 문제를 풀어보았다면 이 문제 또한 매우 간단한 문제다! ※ 주의할 점 단어 길이순으로 정렬한 뒤, 길이가 같을 경우 사전순으로 정렬해야한다. 중복되는 단어가 있을경우 한 번만 출력한다. 알고리즘 [접근 방법] 이전 포스팅에서도 말했지만 배열을 특정한 규칙에 의해 정렬하고 싶은 경우 Arrays.sort 메소드에 Comparator 을 구현하면 된다고 했다. (만약 보지 못한 분들을 위..
[백준] 11651번 : 좌표 정렬하기 2 - JAVA [자바]
[백준] 11651번 : 좌표 정렬하기 2 - JAVA [자바]
2020.06.17www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 문제 좌표 정렬하기 (11650번) 문제를 풀었다면 매우 쉬운 문제다. 알고리즘은 따로 설명 안할테니 아래 링크를 참고해주시면 된다. st-lab.tistory.com/110#알고리즘 [백준] 11650번 : 좌표 정렬하기 - JAVA [자바] www.acmicpc.net/problem/11650 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주..
[백준] 11650번 : 좌표 정렬하기 - JAVA [자바]
[백준] 11650번 : 좌표 정렬하기 - JAVA [자바]
2020.06.10www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 문제 이번 문제는 람다식(lambda)만 쓸 줄 알면 그리 어렵지 않게 풀 수 있다. (오랜만입니다..) 알고리즘 [접근 방법] 보통 문제를 보면 가장 먼저 생각하는 것이, 아! 2차원 배열을 사용해야겠다! 일 것이다. 아쉽게도 Arrays.sort() 자체는 2차원 배열의 정렬을 할 수가 없다. 그렇기 때문에 람다식을 사용하여 Arrays.sort() 확장..
[백준] 1427번 : 소트인사이드 - JAVA [자바]
[백준] 1427번 : 소트인사이드 - JAVA [자바]
2020.06.03www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 오랜만에 매우 쉬운 문제가 나왔다. 알고리즘 [접근 방법] 이 문제의 경우 접근 방법이 정말 무궁무진하다. 먼저 정렬 알고리즘으로 배열을 이용하여 Arrays.sort 를 사용하는 방법부터 카운팅정렬을 사용하는 방법, 이렇게 크게 두 가지가 있을 것이다. 또한 각 자릿수의 값을 정렬하는 것이다보니 입력방법도 다양하게 할 수 있다. Scanner 을 사용하여 입력받는 방법, BufferedReader 로 입력받는 방법, InputStream 으로 입력받는 방법 등 매우 많다. 각 자릿수를 값으로..
[백준] 2108번 : 통계학 - JAVA [자바]
[백준] 2108번 : 통계학 - JAVA [자바]
2020.06.01www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제 그리 어렵지 않은 문제지만 약간의 함정이 있으니 주의해야한다. ※ 주의할 점 동일한 최빈값이 있을경우 '두 번째로 작은 값'을 출력해야 한다. 알고리즘 [접근 방법] 기본적으로 이 문제를 풀기 위해서는 Counting Sort(카운팅 정렬)을 사용할 것이다. 물론 정렬을 쉽게 하기 위해 Arrays.sort 로 풀 수도 있지만 최빈값을 구하는 과정에 있어 '두 번째로 작은 값'을 출력해야하다보니 조금 복잡해진다. (사실상 중앙값 때문에 정렬..
[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]
[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]
2020.05.31www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 드디어 그동안의 기본정렬을 끝맺는 끝판왕 문제다! ※ 주의할 점 Java 의 시간 제한은 3초다. (원래 자바의 경우 언어 보너스가 있어 주어진 시간의 ×2 + 1 초가 주어지지만 이번에는 3초를 넘길 수 없다) (2021. 01. 10 기준 Java → Java8로 명칭이 바뀌었다.) Java 의 메모리 제한은 512MB 이다. 알고리즘 [접근 방법] 이전의 수 정렬하기 문제 포스팅을 보셨다면 이 문제는 쉽게 풀 수 있을..
[백준] 2751번 : 수 정렬하기 2 - JAVA [자바]
[백준] 2751번 : 수 정렬하기 2 - JAVA [자바]
2020.05.30www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 수 정렬하기에 이은 두 번째 문제다. 차이점이라면 데이터도 이전 문제에 비해 1000배 많아졌고, 수의 범위도 1000배 넓다. ※ 주의할 점 Java기준 Arrays.sort 로 쓰면 시간초과가 날 가능성이 높다. (2021.01.11 Java → Java8 명칭이 변경됨) 알고리즘 [접근 방법] 이 문제를 풀기 전에 참고했으면 하는 글 두 개를 넣겠다. 문제를 푸는데 있어 매우 도움이 될 ..
[백준] 2750번 : 수 정렬하기 - JAVA [자바]
[백준] 2750번 : 수 정렬하기 - JAVA [자바]
2020.05.29www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 정렬의 가장 기초적인 문제다! 9가지 방법을 이용하여 풀이한다. 먼저 정렬 방법은 여러가지가 있지만 가장 쉽게 쓸 수 있는 방법은 크게 3가지가 있다. 먼저, 선택정렬이다. 첫 번째 인덱스부터 시작하여 뒤의 인덱스들의 값들과 비교하여 최솟값들을 차곡차곡 쌓아나가는 방법이다. 가장 구현하기 쉽다는 장점이 있으나 시간복잡도가 O(n2) 으로 그리 좋은 성능의 알고리즘은 아니다. 아마 정렬을 구현해보거나 접해본 분들..