프로그램 명: boi_vim
제한시간: 2 초
어니스트 빈센트 라이트는 '위대한 개츠비'라는 소설을 알파벳 e없이 쓴 유명한 미국 작가였습니다.
빅터는 어니스트의 열렬한 팬이어서 그의 소설을 쓰는 방식을 모방하려고 노력을 하고 있습니다.
그는 오직 알파벳 첫 10자만 사용합니다(abcdefghij). 아이러니하게도 소설을 반 정도 쓰던 도중에 타자의 e키가 부서져 버렸습니다.
하지만 빅터는 자신이 지금까지 쓴 소설의 모든 글자중 e를 모두 없애기로 결심합니다.
빅터는 자신의 친구인 Vim에게 이 작업을 맡기려고 했으나
빅터는 Vim과 잘 알지 못하고 빅터 자신은 "x", "h," 그리고 "f"라는 명령어 밖에 모릅니다.
"x"는 커서에 위치한 글자를 지우는 역할을 합니다. 명령 수행 후 커서의 위치는 변하지 않습니다. 빅터는 커서가 글 맨 마지막에 있을 경우 이 명령을 수행하지 못합니다.
"h"는 커서를 한칸 뒤로 옮기는 역할을 합니다(왼쪽). 만약 커서가 글의 맨 처음에 위치할 경우 이 명령을 수행해도 아무일도 일어나지 않습니다.
"f'x'"('x'는 임의의 알파벳) 명령어는 'x'와 같은 알파벳이 나올때까지 커서를 오른쪽으로 이동시킵니다.
만약 해당 알파벳이 문장에 존재하지 않을 경우 이 명령을 수행해도 아무일도 일어나지 않습니다.
(예 : fa입력시 a가 나올때까지 커서를 오른쪽으로 이동)
예를들어 다음과 같은 문장이 있습니다.
(그림) - 네모는 커서의 위치를 의미합니다. 이 그림에서 다음과 같이 명령어를 입력합니다.
- x 명령어를 입력했을시 수행한 그림입니다.
- h 명령어를 입력했을시 수행한 그림입니다.
- fi 명령어를 입력했을시 수행한 그림입니다.
Victor가 문장의 모든 알파벳 e를 지울 있도록 명령어를 최소로 입력시키는 프로그램을 작성하세요. (다른 글자는 지우면 안됩니다.)
처음에는 커서가 문장에 맨 첫글자에 위치해 있습니다.
("e"키가 부러져 있으므로 "fe" 명령어는 사용할 수 없습니다.)
입력
-
첫번째로 문장의 총 길이 N을 입력합니다.
-
두번째 문장은 N개의 알파벳을 입력합니다. 모든 문장은 알파벳 a~j(abcdefghij)로 구성되어 있습니다.
첫번째와 마지막 글자에는 e를 사용할 수 없습니다.
(N<=70,000)
출력
빅터가 모든 e를 지우려면 모든 명령어를 최소 몇번 사용해야 하는지 출력합니다.
입출력 예
입력
35
chefeddiefedjeffeachbigagedegghehad
출력
36
특이하게 N의 개수에 따라 점수가 주어지네요.
N이 70,000개 이하이고 시간제한을 맞추면 100점,
500개 이하면 50점,
5000개 이하면 50+10=60점이 되겠군요.
Ernest Vincent Wright was an American author, known for writing a novel (Gadsby) without using
the letter “e”. Victor is a big fan of Ernest and tries to imitate him in writing a novel, but is looking
for a real challenge. He uses only the first ten characters of the alphabet (namely abcdefghij).
Ironically, the “e” key on his computer breaks halfway through the novel, and for consistency, he
decides to delete all the “e”s he has already written. His friend, a programmer, recommended him to
use the text editor Vim to perform this task. Unfortunately, Victor is not very familiar with Vim, and
knows only three different commands: “x”, “h” and “f”.
- “x” deletes the character at the cursor. The cursor position (counted from the left) does not
change. Victor shall not use this command if the cursor is at the last character of the document.
- “h” moves the cursor one step backward (to the left). Nothing happens if the cursor is at the
beginning of the document.
- “f” waits for the user to input another character C, and then moves the cursor forward to the
next occurrence of C (even if the character at the cursor happens to be C). Nothing happens if
C does not occur anywhere to the right of the cursor position.
For example, if the current text is
where the cursor is denoted by a frame , then
- “x” would give
- “h” would give
- “fi” would give
Write a program that calculates the least number of key presses that Victor needs to use to delete
all the “e”s in the document, but no other letters. Initially, the cursor is at the first character of the
document. Note that the “e” key is broken, so the command “fe” cannot be used.
입력
- The first line contains the integer N, the length of the document.
- The next line contains N characters, each one of the ten lowercase letters from “a” to “j”. The first and the last letter of the input are both different from “e”.
출력
The only line of output should contain exactly one integer: the least number of key presses Victor
needs to delete all the “e”s.
입출력 예
입력
35
chefeddiefedjeffeachbigagedegghehad
출력
36
An optimal solution for the example test case is:
fdhxhhxffhxfahxhhhxhhhxfdhxfghxfahhx
You can test this by starting the Vim editor yourself (type “vim file.txt” at the command prompt to open file.txt, type “:q” to quit).
Constraints
- N <= 70 000
- In test cases worth 50 points: N <= 500
- In test cases worth additional 10 points: N <= 5 000
출처:boi/2013/
[질/답]
[제출 현황]
[푼 후(0)]