주어진 수열을 기차-스택-연산을 통해 기본수열로 변환하는 문제를 구현해봄으로써 스택의 활용법을 체험

소개

1. [문제] 아래 그림과 같은 기차 철로가 있다. 왼쪽에는 n개의 칸으로 구성된 기차가 들어
온다. 각 칸은 서로 다른 번호를 갖고 있는데, 1과 n 사이의 서로 다른 정수 번호이다.
그림에선 4번 칸이 가장 먼저, 다음엔 2번과 1번 칸이 들어오고 마지막으로 3번 칸이 들
어온다. 철로에 중간에 아래쪽에는 기차 칸이 잠시 머물 수 있는 곳이 있고, 이 곳이 스
택 S이다. 여러분은 이 스택 공간을 이용해서 칸들의 번호를 1, 2, 3, 4 순으로 정렬하여
오른쪽으로 빼내야 한다. 즉 1번 칸이 가장 먼저, 다음으로 2, 3, 4번 칸이 차례대로 나오
도록 해야 한다. (4,2,1,3)

2. 입력파일(sum.input)에 저장된 정수 수열을 읽어 일차원 정수 배열 A에 저장한다.
- 입력예: stack.input (위의 그림 예제에 해당되는 입력예제:)

4 // n = 입력 수열의 정수 개수

4 2 1 3 // 1부터 n까지의 수가 정확히 한번 씩 등장하는 수열

3. [10점] 스택 S에 k번 기차 칸을 집어 넣는 것을 PUSH(k)라 하고, 스택 S의 가장 위에 있는 기차를 빼 오른쪽 끝으로 내보내는 것을 POP이라 한다. 그럼 위의 그림 예제의 결과
를 위해선, PUSH(4), PUSH(2), PUSH(1), POP, POP, PUSH(3), POP, POP 스택연산을 연속해서 하면 된다. 그러나 입력이 3 4 1 2 이라면, 스택연산을 통해, 1, 2, 3, 4를 출력할
수 없다. 이 경우엔 IMPOSSIBLE을 출력하면 된다. 여러분은 입력파일 sum.input의 데이
터를 읽어들인 후, 필요한 스택연산을 출력해야 한다.

- 위에 주어진 stack.input에 대한 출력예: (standard output)
PUSH(4) PUSH(2), PUSH(1), POP, POP, PUSH(3), POP, POP

컴파일 실행환경

없음

본문내용

1. [문제] 아래 그림과 같은 기차 철로가 있다. 왼쪽에는 n개의 칸으로 구성된 기차가 들어
온다. 각 칸은 서로 다른 번호를 갖고 있는데, 1과 n 사이의 서로 다른 정수 번호이다.
그림에선 4번 칸이 가장 먼저, 다음엔 2번과 1번 칸이 들어오고 마지막으로 3번 칸이 들
어온다. 철로에 중간에 아래쪽에는 기차 칸이 잠시 머물 수 있는 곳이 있고, 이 곳이 스
택 S이다. 여러분은 이 스택 공간을 이용해서 칸들의 번호를 1, 2, 3, 4 순으로 정렬하여
오른쪽으로 빼내야 한다. 즉 1번 칸이 가장 먼저, 다음으로 2, 3, 4번 칸이 차례대로 나오
도록 해야 한다. (4,2,1,3)
2. 입력파일(sum.input)에 저장된 정수 수열을 읽어 일차원 정수 배열 A에 저장한다.
- 입력예: stack.input (위의 그림 예제에 해당되는 입력예제:)
4 // n = 입력 수열의 정수 개수
4 2 1 3 // 1부터 n까지의 수가 정확히 한번 씩 등장하는 수열
3. [10점] 스택 S에 k번 기차 칸을 집어 넣는 것을 PUSH(k)라 하고, 스택 S의 가장 위에 있는 기차를 빼 오른쪽 끝으로 내보내는 것을 POP이라 한다. 그럼 위의 그림 예제의 결과
를 위해선, PUSH(4), PUSH(2), PUSH(1), POP, POP, PUSH(3), POP, POP 스택연산을 연속해서 하면 된다. 그러나 입력이 3 4 1 2 이라면, 스택연산을 통해, 1, 2, 3, 4를 출력할
수 없다. 이 경우엔 IMPOSSIBLE을 출력하면 된다. 여러분은 입력파일 sum.input의 데이
터를 읽어들인 후, 필요한 스택연산을 출력해야 한다.
- 위에 주어진 stack.input에 대한 출력예: (standard output)
PUSH(4) PUSH(2), PUSH(1), POP, POP, PUSH(3), POP, POP

참고자료

· 없음