심화 과정 11 일차

1. 자료구조 및 알고리즘 11일차 수강하기

 

 -  정렬

 

2. 새롭게 알게된 지식

 

 - O(n^2) 정렬 : 선택 / 버블/ 삽입 정렬

 

- 최대 O(n^2) 정렬 평균 O(NlogN): 퀵 정렬

 

- O(NlogN) 정렬 : 병합 / 힙 정렬  

 

- 병합 정렬

 

   절반씩 나누면서 원소가 1개가 남을 때까지 분리

 

 

 

   나눈 과정을 반대로 병합 하면서 작은 순대로 정렬

 

 

 

과제 1 : 수 정렬하기 2 : https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

 

- 접근 : 

 

 병합 정렬로 정렬

 

 

 - 코드 구현 : 

 

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번: 나이순 정렬

 

 - 접근 : 

 

 나이를 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

 

 -접근 : 

문자열의 입력이 들어오면 만들 수 있는 수 중 큰 순서대로 병합 정렬

 

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번: 통계학

 

 - 접근 : 

문제에서 주어진 조건 그대로 구현

 

 - 코드 구현 : 

 

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번: 전화번호 목록

 

 - 접근 : 

 

파이썬 문자열 정렬은 사전식으로 정렬되는 것을 이용

 

 - 코드 구현: 

 

```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()
```