정렬

(Python) 백준 2751번 - 수 정렬하기 2

문제 출처 : https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 합병 정렬을 사용한 풀이이다. O(NlogN)의 시간복잡도를 가지는 합병 정렬이기에 시간 초과가 발생하지 않을 것으로 기대했으나 시간 초과가 일어나서 상당히 당황했었다. 하지만 sys.stdin.readline()이 아닌 input()을 사용해서 시간초과가 발생한 것이었다. import sys def mergesort(arr): # 분할과 정복을 활용한 합병정렬 if..

(Python) 백준 1181번 - 단어 정렬

문제 링크 : https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 arr = [] for _ in range(int(input())): m = input() if m in arr: continue if len(arr) == 0: arr.append(m) for i in range(len(arr)): if len(arr[i]) > len(m): arr.insert(i, m) break elif len(arr[i]) == len(m):..

(Python) 백준 10989번 - 수 정렬하기 3

문제 링크 : https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 원래 브론즈 문제는 포스팅하지 않으려 했으나 문제와 관련하여 정리할 개념들이 많이 있어서 풀이를 적어보려고 한다. 메모리 제한과 시간 제한이 있어 단순하게 python의 sort함수로는 이 문제를 풀 수 없어서 계수정렬을 이용하여 풀었다. count = [0] * 10001 for _ in range(int(input())): count[int(input())] += 1 for i in range..