1. 자료구조 및 알고리즘 11일차 수강하기
- 정렬
2. 새롭게 알게된 지식
- O(n^2) 정렬 : 선택 / 버블/ 삽입 정렬
- 최대 O(n^2) 정렬 평균 O(NlogN): 퀵 정렬
- O(NlogN) 정렬 : 병합 / 힙 정렬
- 병합 정렬
절반씩 나누면서 원소가 1개가 남을 때까지 분리
나눈 과정을 반대로 병합 하면서 작은 순대로 정렬
과제 1 : 수 정렬하기 2 : https://www.acmicpc.net/problem/2751
2751번: 수 정렬하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
- 접근 :
병합 정렬로 정렬
- 코드 구현 :
import sys
class Solution:
def __init__(self):
self.input = sys.stdin.readline
self.output = sys.stdout.write
def _merge(self, arr1, arr2):
"""오름차순으로 정렬하며 두개의 배열을 병합
"""
result = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
# 왼쪽과 오른쪽의 배열의 크기가 다른 경우 남은 원소 결과에 추가
while i < len(arr1):
result.append(arr1[i])
i += 1
while j < len(arr2):
result.append(arr2[j])
j += 1
return result
def mergeSort(self, arr):
"""pivot 을 중간으로 설정하고 \n
오름차순으로 병합 정렬
"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
return self._merge(self.mergeSort(L), self.mergeSort(R))
def answer(self):
N = int(self.input())
res = []
for _ in range(N):
res.append(int(self.input()))
self.output('\n'.join(str(i) for i in self.mergeSort(res)) + '\n')
s = Solution()
s.answer()
과제 2 : 나이순 정렬 : https://www.acmicpc.net/problem/10814
10814번: 나이순 정렬
온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을
www.acmicpc.net
- 접근 :
나이를 KEY 값으로 이름을 들어오는 순대로 연결한 리스트를 값으로 설정
KEY를 리스트로 만든 후 오름차순 정렬 후 해당 키의 값들을 출력
- 코드 구현 :
import sys
class Solution:
def __init__(self):
self.input = sys.stdin.readline
self.output = sys.stdout.write
def _merge(self, arr1, arr2):
"""오름차순으로 정렬하며 두개의 배열을 병합
"""
result = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
# 왼쪽과 오른쪽의 배열의 크기가 다른 경우 남은 원소 결과에 추가
while i < len(arr1):
result.append(arr1[i])
i += 1
while j < len(arr2):
result.append(arr2[j])
j += 1
return result
def mergeSort(self, arr):
"""pivot 을 중간으로 설정하고 \n
오름차순으로 병합 정렬
"""
if len(arr) <= 1:
return arr
pivot = len(arr)//2
L = arr[:pivot]
R = arr[pivot:]
return self._merge(self.mergeSort(L), self.mergeSort(R))
def answer(self):
N = int(self.input())
data_dict = {}
for _ in range(N):
idx, val = self.input().split()
i = int(idx)
if i in data_dict:
data_dict[i].append(val)
continue
data_dict[i] = [val]
for i in self.mergeSort(list(data_dict.keys())):
for name in data_dict[i]:
self.output(f'{i} {name} \n')
s = Solution()
s.answer()
과제 3 : 가장 큰 수 : https://leetcode.com/problems/largest-number
Largest Number - LeetCode
Can you solve this real interview question? Largest Number - Given a list of non-negative integers nums, arrange them such that they form the largest number and return it. Since the result may be very large, so you need to return a string instead of an int
leetcode.com
-접근 :
문자열의 입력이 들어오면 만들 수 있는 수 중 큰 순서대로 병합 정렬
EX> 2 10 -> 210, 102(만들 수 있는 수중에서 작으므로 제외)
2 10 순서가 크므로 [2, 10] 으로 정렬 후 출력 '210'
- 코드 구현 :
class Solution:
def _merge(self, arr1, arr2):
result = []
i = j = 0
while i < len(arr1) and j < len(arr2):
str_i = str(arr1[i])
str_j = str(arr2[j])
#만들 수 있는 숫자 중 큰 순으로 정렬
if str_i + str_j > str_j + str_i:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
while i < len(arr1):
result.append(arr1[i])
i += 1
while j < len(arr2):
result.append(arr2[j])
j += 1
return result
def mergeSort(self, arr):
if len(arr) <= 1:
return arr
pivot = len(arr)//2
L = arr[:pivot]
R = arr[pivot:]
return self._merge(self.mergeSort(L), self.mergeSort(R))
def largestNumber(self, nums: list[int]) -> str:
sorted = self.mergeSort(nums)
return '0' if sum(nums) == 0 else ''.join(str(n) for n in sorted)
과제 3 : 통계학 : https://www.acmicpc.net/problem/2108
2108번: 통계학
첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.
www.acmicpc.net
- 접근 :
문제에서 주어진 조건 그대로 구현
- 코드 구현 :
import sys
class Solution:
def __init__(self):
self.input = sys.stdin.readline
self.output = sys.stdout.write
def _merge(self, arr1, arr2):
result = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
while i < len(arr1):
result.append(arr1[i])
i += 1
while j < len(arr2):
result.append(arr2[j])
j += 1
return result
def mergeSort(self, arr):
if len(arr) <= 1:
return arr
pivot = len(arr)//2
L = arr[:pivot]
R = arr[pivot:]
return self._merge(self.mergeSort(L), self.mergeSort(R))
def run(self):
N = int(self.input())
arr = []
arr_dict = {}
sum = 0
max_cnt = 1
for _ in range(N):
n = int(self.input())
arr.append(n)
sum += n
if n in arr_dict:
arr_dict[n] += 1
max_cnt = max_cnt if max_cnt > arr_dict[n] else arr_dict[n]
continue
arr_dict[n] = 1
sorted_arr = self.mergeSort(arr)
if len(arr) == 1:
min_count_value = arr[0]
else:
temp = []
for n in arr_dict:
if arr_dict[n] == max_cnt:
temp.append(n)
if max_cnt == 1:
min_count_value = sorted_arr[1]
elif len(temp) == 1:
min_count_value = temp[0]
else:
min_count_value = self.mergeSort(temp)[1]
self.output(str(round(sum/len(arr))) + '\n')
self.output(str(sorted_arr[len(arr)//2]) + '\n')
self.output(str(min_count_value) + '\n')
self.output(str(sorted_arr[-1] - sorted_arr[0]) + '\n')
s = Solution()
s.run()
과제 4 : 전화번호 목록 : https://www.acmicpc.net/problem/5052
5052번: 전화번호 목록
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가
www.acmicpc.net
- 접근 :
파이썬 문자열 정렬은 사전식으로 정렬되는 것을 이용
- 코드 구현:
```python
import sys
class Solution:
def __init__(self):
self.input = sys.stdin.readline
self.output = sys.stdout.write
def run(self):
t = int(self.input())
for _ in range(t):
n = int(self.input())
p_nums = []
for _ in range(n):
p_num = self.input().rstrip()
p_nums.append(p_num)
p_nums.sort()
res = 'YES'
for i in range(len(p_nums)-1):
if p_nums[i] == p_nums[i+1][:len(p_nums[i])]:
res = 'NO'
break
self.output( res + '\n')
s = Solution()
s.run()
```
'개발일지' 카테고리의 다른 글
심화 과정 13 일차 (1) | 2024.02.24 |
---|---|
심화 과정 12 일차 (0) | 2024.02.23 |
심화 과정 10 일차 (1) | 2024.02.23 |
심화 과정 9 일차 (0) | 2024.02.23 |
3주차 WIL (0) | 2024.02.18 |