Algorithm/정렬

BOJ 15970 - 화살표 그리기

https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 아이디어 색깔이 같은 점들 중 가장 가까운 점끼리의 거리를 구해야 하니까 일단 색깔별로 ArrayList에 분류한 후 정렬해준다. 정렬의 특성을 생각해보면 정렬 후 각 원소마다 가장 가까운 원소는 자신의 양 옆 중에 있다는 것을 알 수 있다. 가장 가까운 원소를 찾는다는 문구를 보고 정렬의 특성을 떠올려 정렬로 접근할 수 있어야 한다. 가장 가까운 점끼리의 거리를 구해야 하므로 기준 점의..

BOJ 11652 - 카드

https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 1. 아이디어 Int 범위로는 부족하니까 long 자료구조를 사용해야 한다. 최빈값을 구해야 하는 문제이다. 정렬의 특성을 생각해보면 같은 정보들은 인접해있다는 것을 알 수 있으므로 이 특성을 이용해 최빈값을 구한다. 예를 들어 6 7 2 3 2 6 7 6 의 카드가 주어졌을 때 정렬을 하면 2 2 3 6 6 6 7 7 이 된다. 먼저 정렬을 한 후 같은 정보들은 인접해있다는 특성을 이용해 ..

BOJ 1015 - 수열 정렬

https://www.acmicpc.net/problem/1015 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 1. 아이디어 1. 주어진 배열을 인덱스와 함께 정렬 2. 정렬된 배열의 인덱스 값을 P 배열에 저장 2. 시간 복잡도 정렬만 해주면 바로 P 배열을 채워줄 수 있으므로 정렬의 시간복잡도인 O(N log N) 만큼 걸린다. N의 최댓값은 50이므로 1초안에 풀이가 가능하다. 3. 구현 import java.io.*; import java.uti..

[Algorithm] 정렬

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다. 출처 : https://github.com/rhs0266/FastCampus 정렬 어떤 자료들이 주어졌을 때 그 자료들에 대해서 오름차순 혹은 내림차순 등의 기준이 주어졌을 때 그 기준에 맞게 정렬하는 것 정렬의 조건 1. 정렬 조건이 필요 static class Elem implements Comparable { public int num, idx; @Override public int CompareTo(Elem other) { // 오름차순 -> return 음수 return num - other.num; // 내림차순 -> return 양수 // return other.num - num; // 같은 경우 -> return 0 } } re..