[내일배움캠프 23일차 TIL] 백준 10989번 수 정렬하기 3, 16951번 미로 탐색 with python

백준 10989번 수 정렬하기

 

다들 생각하듯이 처음엔 sort()함수 사용했다가 메모리 초과가 떴다...

이 문제를 풀기 위해서는 계수 정렬(Counting Sort)을 사용하는 방법이 있다

계수정렬은 정렬 알고리즘 중 하나로, 특정 범위 내의 정수를 정렬할 때 매우 효과적인 알고리즘이다.

주로 정수로 이루어진 배열을 정렬하는 경우에 사용된다

 

계수정렬은 다음과 같은 순서로 진행된다

1. 정렬하려는 배열의 최댓값을 기준으로 한 카운트 배열을 생성
   - 배열의 크기는 정렬하려는 배열의 최댓값+1이 된다
2. 카운트 배열을 사용하여 각 요소의 등장 횟수를 카운트하고 누적합을 구한다
3. 원래 배열을 순회하면서 각 요소를 카운트 배열을 참조하여 정렬된 위치에 배치한다

 

이러한 로직을 이용해서 코드를 작성하면 다음과 같다

import sys

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

num =[0]*100001 # 키운트 배열 생성
for _ in range(N):
    n = int(sys.stdin.readline())
    num[n] += 1 # 각 요소의 등장 횟 카운트 및 누적합

# 배열을 순회하면서 각 위치별 카운트만큼 숫자 출력
for i in range(10001):
    if num[i] != 0:
        for j in range(num[i]):
            print(i)

 

 

 

 

---

백준 16951번 블록 놀이

 

 

블록쌓기 문제를 여러 방법으로 시도해 보았지만

결국은 모든 경우를 탐색해보고 최솟값을 도출해야 했다

블록은 등차 수열을 만족해야 하는데

블럭의 모든 경우의 수를 탐색하며 기준이 되는 블럭에서 등차가 만족하지 않는 블럭이 몇 개 인지 알아내야 한다

먼저 각 경우에 대해 등차를 만족하지 않는(수정해야 하는) 블록의 수를 출력하는 함수는 다음과 같이 작성하였다

# n = 가준 인덱스 , 등차 = k, 블록 배열 = block
def change_block(n, k, block): 
    c = 0 # 바꾸어야 하는(쌓거나 빼야하는) 블럭의 수
    for b in range(len(block)):
        if b < n: # 기준 인덱스보다 낮은 경우
            if block[b] != block[n]-k*(n-b): c +=1 # 기준 인덱스와의 등차가 일치하지 않는 경우
        else: # 기준 인덱스보다 크커나 같은 경우
            if block[b] != block[n]+k*(b-n): c +=1
    return c

 

 

그리고 모든 블럭을 돌아다니며 등차를 만족하지 않는 블럭이 최소가 되는 개수를 찾아야 한다

코드는 다음과 같이 작성하였다

for n in range(N): # 모든 블럭을 탐색
    if block[n] - K*n < 1: # 첫 번째 항이 1보다 작은 경우
        continue # 해당 블럭을 기준으로 등차를 생성 할 수 없음
    change = min(change, change_block(n, K, block)) # 수정해야 하는 블럭의 최소 개수

 

 

전체 코드는 여기로!

 

---

 

오늘도 코드카타 문제가 너무 어려웠다,,,, 로직을 생각해내는 것부터 너무 어렵다...

여러번 하다 보면 좋아지겠지... 잘 할수 있겠지...