본문 바로가기

sort5

[백준] 2108번 : 통계학(JAVA) https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 12단계 정렬의 카테고리에 포함되어 있는 문제이다. 정답률이 27.050%인 문제로 12단계의 정렬 카테고리에 포함된 문제 중 2번 째로 정답률이 낮은 문제이다. 나는 이 카테고리에서 이 문제를 가장 마지막에 풀었으며 정렬 카테고리 문제의 난이도 중에서 가장 어렵다고 생각한다. N개의 입력된 수로 산술평균, 중앙값, 최빈값, 범위 4가지를 구해야 하기 때문이.. 2019. 11. 30.
[백준] 10814번 : 나이순 정렬(JAVA) https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 12단계 정렬의 카테고리에 포함되어 있는 문제이다. 입력은 회원의 수가 입력되고 회원의 수 만큼 회원의 나이와 이름이 순서대로 입력된다. 입력된 값들을 나이 순서대로 정렬하는데, 나이가 같으면 먼저 입력받은 순서대로 정렬을 해야한다. 정렬을 해도 입력된 순서가 바뀌지 않은 정렬을 Stable sort라고 하며 대표적.. 2019. 11. 21.
[백준] 1181번 : 단어 정렬(JAVA) https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 12단계 정렬의 카테고리에 포함되어 있는 문제이다. 알파벳 소문자로 이루어진 N개의 단어가 들어왔을 때의 조건은 1. 길이가 짧은 것 부터 2. 길이가 같으면 사전 순으로 이 두개의 조건을 지켜서 문제를 제출하면 된다. Merge Sort로 구현을 하였으며 제출할 때 package를 지우는 것을 깜빡하고 3번이나 틀린 .. 2019. 11. 20.
[백준] 11650번 : 좌표 정렬하기(JAVA) 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 위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 12단계 정렬의 카테고리에 포함되어 있는 문제이다. 시간제한은 1초인데 좌표의 개수는 최대 10만개이니 시간복잡도가 O(NlogN)인 정렬방법으로 풀어야한다. 나는 자바 라이브러리에 포함된 정렬이 아닌 따로 합병정렬 클래스를 선언하여 만들었다. 4번의 도전끝에 성공하였는.. 2019. 11. 18.
[백준] 10989번 : 수 정렬하기 3(JAVA) https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 위의 문제는 Baekjoon Online Judge의 단계별로 풀어보기 중 12단계 정렬의 카테고리에 포함되어 있는 문제이다. 카운팅정렬(계수 정렬)을 이용하여 풀어야 하는 문제이며 수의 범위가 작을 때 더욱 빠르게 정렬할 수 있는 방법이 계수 정렬이다. 처음에는 입력을 Scanner로 썼을 때는 시간초과가 났었다. 그래서 더 빠르게 입력하고 출력하는 방법인 Buffer방법을 쓰니 통과가 되었다. 알고리즘은 나중에.. 2019. 11. 17.