활자인쇄기(Type Printer) > 문제은행

본문 바로가기


알고리즘 문자열

1551 : 활자인쇄기(Type Printer)

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 28 회    시도횟수: 267 회    Special Judge



이번 문제의 목표는 가변 활자 인쇄기로 N개의 단어를 출력하는 것이다. 가변 활자 인쇄기란, 인쇄를 원하는 글자가 찍힌 작은 금속 활자들을 마음대로 끼웠다 빼면서 쓰던 과거의 재래식 인쇄기를 말한다. 사람이 넣어 준 활자들이 종이에 한꺼번에 찍힘으로써 단어가 완성된다. 이 인쇄기에다 취할 수 있는 동작은 아래와 같다.

  • 인쇄기에 들어있는 단어의 끝에다 글자(활자)를 추가한다.
  • 인쇄기에 들어있는 단어의 맨 마지막 글자를 빼낸다. (즉, 글자를 넣고 빼는 것은 일종의 스택 형태이다. 물론 글자가 최소한 하나 이상 있는 경우에만 가능한 동작)
  • 현재 인쇄기에 들어있는 단어를 그대로 출력한다.
  • 처음에는 인쇄기에 아무 활자도 들어있지 않다. 원하는 단어를 모두 인쇄한 직후에 인쇄기의 활자 배열이 어떤 상태가 되어 있든지 상관없다. 또한 지정된 단어들을 어떤 순서로 출력하든 그것도 상관없다.
 활자를 넣고 빼는 것은 시간이 소요되는 작업이다. N개의 단어를 입력 받아서 이 단어들을 모두 출력하는 데 필요한 최소한의 동작 횟수를 계산하고, 그 실제 동작 과정을 출력하는 프로그램을 작성하시오.

첫째 줄에는 출력하려는 단어의 개수 N(1≤N≤25,000)이 들어있다.
다음 N개의 줄에는 단어가 하나씩 들어있다. 단어는 소문자 a~z로만 구성되어 있으며 길이는 1자 이상 20자 이하이다. 
모든 단어들은 중복이 없이 서로 다 다르다.


첫째 줄에는 이 N개의 단어를 모두 출력하는 데 필요한 최소 동작 횟수 M을 출력한다.
다음 M개의 줄에는 각 줄마다 동작을 기술하는 한 글자를 출력한다.
ㆍ 활자를 끝에다 추가하는 것은 그 추가할 활자를 나타내는 소문자 알파벳(a~z)으로 나타낸다.
ㆍ 마지막 활자를 퇴장하는 것은 - (마이너스. 아스키 코드 45) 
ㆍ 지금 프린터에 들어있는 활자를 한 단어로 출력하는 것은 대문자 P

[Copy]
3
print
the
poem
[Copy]
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P


출처 : IOI 2008 day1



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.