고양이 두 잔

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 풀이 문제 소개에 카운팅 정렬을 사용하면 된다고 해서 순수하게 구현해놓은 카운팅 정렬을 써보았다. 단 한 문제도 통과하지 못하고 메모리 초과. 어떻게든 스텝을 줄여보려고 for문을 합쳐보기도 하고 리스트의 요소 개수를 조절해봐도 여전히 메모리 초과와 시간 초과. 그래도 도전해보겠다고 한시간 내내 매달리다가 포기하고 그냥 카운팅 정렬의 아이디어만 응용하기로 했다. 풀이 단계..

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 풀이 카운팅 정렬은 대상 배열의 크기 N과 원소중 최댓값 k에 따라 O(N + k)의 시간 복잡도를 가진다. 이는 배열의 크기가 작고, 수의 범위가 좁을수록 무시무시한 속도를 자랑하는데, 이번 문제는 그 카운팅 정렬을 구현해보라는 문제이다. 다른 글에서 구현했으므로, 여기서는 그냥 가져다 쓴다. 2022.12.27 - [Development/Java] - [Algorith..

으로 구현한 다른 정렬: [Java+Python]삽입 정렬(Insert Sort) [Java+Python]버블 정렬(Bubble Sort) [Java+Python]선택 정렬(Selection Sort) [Java+Python]병합 정렬(Merge Sort) [Java+Python]힙 정렬(Heap Sort) [Java+Python]퀵 정렬(Quick Sort) 카운팅 정렬은 말 그대로 세어서 정렬하는 방식이다. 그래서 무엇을 세느냐 하면, 아래에서 보겠지만 정렬 대상이 대는 원소의 등장 횟수를 전부 센다. 이후 원소의 최댓값에 따라 누적합을 보유한 배열을 만든 뒤, 그 배열의 원소를 근거로 대상 배열을 정렬하는 식이다. 카운팅 정렬의 시간 복잡도는 O(N + k)로, 여기서 k는 타깃이 되는 배열 원소의..