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

문제 설명

주어진 수열 seq에서 오름차순 수열을 만들기 위한 알고리즘을 구현하시오. 수열은 정수로 이루어져 있으며, 오름차순으로 정렬된 수열을 얻기 위해 스택을 사용하는 방법을 보여주십시오. 이때 수열의 원소를 스택에 push하고 pop하는 방식으로만 조작할 수 있습니다.

예를 들어, 입력 수열이 [3, 2, 4, 1, 5]인 경우, 이를 오름차순으로 정렬하기 위해 스택을 어떤 식으로 사용해야 할까요? 이러한 수열을 스택을 통해 필요한 순서대로 출력하도록 만드세요.

입력 형식

  • 첫 번째 줄에 수열의 길이 n이 주어집니다. (1 ≤ n ≤ 1000)
  • 두 번째 줄에는 수열의 각 원소 a1, a2, ..., an이 주어집니다. (1 ≤ ai ≤ 1000)

출력 형식

오름차순으로 정렬된 수열을 출력하시오. 수열의 원소들은 스택이 pop되는 순서대로 나열되어야 하며, 각 원소는 한 줄에 하나씩 출력해야 합니다.

접근 방법

문제를 해결하기 위해 스택을 사용하여 오름차순으로 숫자를 정렬하는 과정을 설명하겠습니다. 스택은 LIFO(후입선출) 구조로, 가장 최근에 들어온 데이터가 가장 먼저 나가는 구조입니다. 이 특성을 활용하여, 우리는 주어진 수열에서 숫자를 조작할 수 있습니다.

  1. 입력된 수열을 읽는다.
  2. 스택을 초기화한다.
  3. 주어진 수열을 순회한다. 각 원소를 스택에 push하거나 pop하여 요구되는 오름차순 수열을 만든다.
  4. 최종적으로 스택에서 pop하여 결과를 출력한다.

구현

다음은 이 문제를 해결하기 위한 스위프트 코드입니다:

import Foundation

func makeAscendingSequence(seq: [Int]) {
    var stack = [Int]()
    var output = [Int]()
    var current = 1
    let n = seq.count

    for number in seq {
        while current <= n {
            stack.append(current)
            current += 1
        }

        if stack.isEmpty || stack.last! != number {
            print("Impossible") // 불가능한 경우
            return
        }

        output.append(stack.removeLast())
    }

    // 결과 출력
    for num in output {
        print(num)
    }
}

// 테스트케이스
let seq = [3, 2, 4, 1, 5]
makeAscendingSequence(seq: seq)

코드 설명

위의 스위프트 코드는 다음과 같은 방식으로 구현되어 있습니다:

1. 변수 초기화

  • stack: 스택의 역할을 할 배열입니다.
  • output: 최종 오름차순 수열을 저장할 배열입니다.
  • current: 현재 스택에 추가해야 할 숫자를 나타냅니다.

2. 수열 순회

입력된 수열을 순회하며 각 원소 number에 대해 다음의 작업을 수행합니다:

  1. 현재 current보다 n이하인 동안, stack에 current를 push합니다. 그리고 current를 1씩 증가시킵니다.
  2. 스택의 top 원소가 현재 number와 같지 않을 경우, “Impossible”을 출력하고 종료합니다.
  3. 스택의 top 원소를 output 배열에 추가합니다.

3. 결과 출력

최종적으로 output 배열에 저장된 모든 수를 출력합니다.

예외 처리

위 알고리즘에서 중요한 점은 stack가 비어있거나 stack의 top 원소가 현재 탐색하고 있는 number와 다를 경우에 대한 처리가 필요하다는 점입니다. 이때는 정렬이 불가능하므로 “Impossible” 메시지를 출력합니다.

결론

스택을 이용한 오름차순 수열 만들기 문제는 기본적인 스택 구조의 이론을 이해하는 데 매우 유용합니다. 이 알고리즘을 통해 스택의 LIFO 구조를 활용하는 방법과 숫자를 조작하는 기법을 익힐 수 있습니다. 코딩 테스트에서 출제될 수 있는 다양한 문제 유형에 대비하기 위해 스택을 활용한 다양한 예제를 연습해보시기 바랍니다.

추가 연습 문제

  • 주어진 수열의 원소를 역순으로 출력하는 프로그램 작성하기
  • 스택의 최대 크기를 설정하여 수행하는 스택 알고리즘 구현하기
  • 스택을 이용하여 중위 표기법을 후위 표기법으로 변환하기