[백준] 1992, 2751 - Python3

2751. 수 정렬하기 2

https://www.acmicpc.net/problem/2751

내 풀이 - 성공

from sys import stdin

N = int(stdin.readline())

nums = []
for i in range(N):
    n = int(stdin.readline())
    nums.append(n)

nums.sort()

for n in nums:
    print(n)

nums 에 모두 저장 후 sort 하기

파이썬 기본 sort 는 O(nlog(n))

기본 sort 외에는 퀵 정렬이나 merge sort 등을 사용할 듯

다른 사람의 풀이

from sys import stdin

def merge_sort(array):
    if len(array)<=1:
        return array
    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])

    i,j,k = 0,0,0

    while i < len(left) and j <len(right):
        if left[i] < right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k+=1
    
    if i==len(left):
        while j < len(right):
            array[k] = right[j]
            j += 1
            k += 1
    elif j==len(right):
        while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1
    return array

N = int(stdin.readline())

nums = [0] * N
for i in range(N):
    n = int(stdin.readline())
    nums[i] = n

nums = merge_sort(nums)

for n in nums:
    print(n)

merge sort 이용
left, mid, right 로 구역을 나눠서 정렬

넘 느리다...

---

1992. 쿼드트리

https://www.acmicpc.net/problem/1992

내 풀이 - 성공

import sys
sys.setrecursionlimit(10**9)

N = int(sys.stdin.readline())

mat = []

for i in range(N):
    s = sys.stdin.readline().strip()
    tmp = []
    for c in s:
        tmp.append(int(c))
    mat.append(tmp)

def func(si, sj, ei, ej, n):
    val = mat[si][sj]
    flag = 1

    for i in range(si, ei):
        for j in range(sj, ej):
            if mat[i][j] != val:
                flag = 0
                break
    
    if flag == 1:
        return str(val)
    else:
        # 4등분
        s = "("
        if n//2 > 0:
            s += func(si, sj, si+n//2, sj+n//2, n//2) # 왼위
            s += func(si, sj+n//2, si+n//2, ej, n//2) # 오위
            s += func(si+n//2, sj, ei, sj+n//2, n//2) # 왼아
            s += func(si+n//2, sj+n//2, ei, ej, n//2) # 오아
        return s + ")"

ans = func(0, 0, N, N, N)
print(ans)

저번에 분할정복 했던 걸 생각하며 풀었다

우선 mat 에 영상에 대한 정보를 모두 담고 func 이라는 재귀함수를 만들어줬다

시작 인덱스 (si, sj)
끝 인덱스 (ei, ej)
4 등분 할 때 사용할 크기 n
을 매개변수로 함

현재 mat 의 시작 값과 비교해서 모두 같은 값이면 그 값 return
하나라도 다른 값이 있으면 n//2 길이만큼 4 등분 => 괄호 추가