파이썬 코딩테스트 강좌, 스택으로 오름차순 수열 만들기

작성일: 2023년 10월 10일

작성자: 알고리즘 강사

문제 설명

주어진 정수 N에 대해, 1부터 N까지의 수를 스택을 사용하여 오름차순으로 정렬된 수열을 만드세요. 당신은 다음과 같은 연산을 할 수 있습니다:

스택에 1부터 N까지의 수를 차례로 푸시(push)합니다.
스택의 가장 위에 있는 값을 팝(pop)하여 출력합니다.

입력으로는 두 개의 숫자를 받습니다:

정수 N (1 <= N <= 100,000)
정수 K (1 <= K <= N)

출력으로는 K개의 수를 오름차순으로 출력합니다. 스택을 사용할 수 있으며, 주어진 입력 수를 적절히 스택에 넣고 뺄 수 있습니다. 당신의 목표는 스택의 동작을 사용하여 오름차순의 수열을 생성하는 것입니다.

문제 접근 방법

이 문제는 스택의 Last-In-First-Out(LIFO) 특성을 활용하여 주어진 수를 오름차순으로 출력하는 문제입니다. 우선 1부터 N까지의 숫자를 스택에 푸시한 후, 필요한 수를 순서대로 팝하여 출력해야 합니다. 이 과정에서 우리는 주의해야 할 몇 가지 사항이 있습니다:

스택에 푸시할 수 있는 수는 1부터 N까지입니다.
스택에서 팝할 때는 항상 스택의 최상단에 있는 수부터 팝해야 합니다.
최종적으로 출력되는 수는 오름차순으로 정렬되어야 합니다.

알고리즘 구현

이제 문제 접근 방법을 기반으로 알고리즘을 구현해 보겠습니다. 알고리즘의 기본 로직은 다음과 같습니다:

N까지의 수를 차례로 스택에 푸시
스택에서 최상단의 수를 팝하며 원하는 수 K개를 출력

다음은 이를 파이썬으로 구현한 코드입니다:


def create_sorted_sequence(N, K):
    stack = []
    result = []
    num = 1
    
    for i in range(N):
        while num <= N:
            stack.append(num)
            num += 1
        
        if stack:  # 스택이 비어있지 않으면
            result.append(stack.pop())
        
        if len(result) == K:  # K개의 수가 출력되면 종료
            break
            
    return result

# 입력 예시
N = 5
K = 3
output = create_sorted_sequence(N, K)
print("오름차순 수열:", output)

위의 함수 create_sorted_sequence(N, K)는 N과 K를 입력으로 받아 K개의 오름차순 수열을 생성하는 함수입니다. 스택을 사용하여 수를 저장하고, 필요할 때마다 팝하여 결과 배열에 추가합니다.

코드 설명

코드의 각 부분을 상세히 설명하겠습니다:

스택과 결과 배열 초기화:

stack = []와 result = []를 사용하여 빈 스택과 결과 배열을 초기화합니다.
수 푸시 로직:

while num <= N: 조건을 활용하여 1부터 N까지 수를 스택에 푸시합니다. num 변수를 통해 다음에 푸시할 수를 결정합니다.
수 팝 로직:

if stack:를 사용하여 스택이 비어있지 않을 경우 최상단의 수를 팝하여 결과 배열에 추가합니다.
K개 출력 조건:

if len(result) == K: 조건을 체크하여 출력할 수의 개수가 K에 도달하면 반복문을 종료합니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 다음과 같습니다:

스택에 수를 푸시하는 과정: O(N)
스택에서 K개를 팝하는 과정: O(K)

따라서 전체 시간 복잡도는 O(N + K)입니다. 이는 효율적인 접근 방법이며, 충분히 빠르게 동작합니다.

결론

스택을 사용하여 수를 오름차순으로 정렬하는 문제는 창의적이고 체계적인 접근 방식이 필요한 문제입니다. 이 강좌를 통해 스택의 기본 원리와 이를 활용한 문제 해결 방법을 배웠습니다. 앞으로도 더 다양한 알고리즘 문제를 풀어보며 실력을 향상시키시길 바랍니다.

문제 설명

문제 접근 방법

알고리즘 구현

코드 설명

시간 복잡도

결론

관련