스택 수(stack number)란 다음 장치의 왼쪽 큐 LQ에 들어 … | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 12년 1회차
스택 수(stack number)란 다음 장치의 왼쪽 큐 LQ에 들어 갈 수 있는 숫자열을 말한다. 오른쪽 큐 RQ로부터 데이터가 하나씩 중간에 있는 스택 MS를 거치거나 바로 LQ로 입력될 수 있다. 즉, 데이터가 LQ에 입력될 때 RQ에서 직접 입력되거나 MS에서 한 데이터를 삭제해서 LQ에 추가할 수 있다. 다음 장치에서 생성할 수 있는 스택 수는?
문제 이미지
1
1 8 5 6 7 4 9 3 10 2
2
3 4 6 7 8 5 9 2 1 10
3
3 4 8 5 6 7 2 9 1 10
4
9 4 7 5 6 3 8 1 2 10
해설

이 장치는 1부터 10까지 순서대로 들어오는 입력을 스택 하나로 재배열하는 것이므로, 출력열이 유효한 스택 순열이어야 하며 3 4 6 7 8 5 9 2 1 10만 가능하다.

판정 요령은 어떤 수가 나올 때 그보다 작은데 아직 안 나온 수는 스택에 쌓여 있으므로, 이후에는 큰 수부터 역순으로만 나올 수 있다는 것이다. 정답열은 1·2를 쌓고 3·4를 바로 보내고, 5를 쌓은 뒤 6·7·8을 보내고 5를 꺼내며, 9를 보낸 뒤 2·1을 꺼내고 10을 보내면 만들어진다.

  • 1 8 5 6 7 4 9 3 10 2: 8이 나올 때 스택 top은 7인데 다음에 5가 나와야 하므로 불가능하다.
  • 3 4 8 5 6 7 2 9 1 10: 8이 나올 때 스택에 5·6·7이 쌓여 top이 7인데 5가 먼저 나오므로 불가능하다.
  • 9 4 7 5 6 3 8 1 2 10: 9가 나올 때 1~8이 모두 스택에 있어 top이 8인데 4가 나오므로 불가능하다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 12년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기