[BOJ] 33516 - skeep 문자열

https://www.acmicpc.net/problem/33516

BOJ - skeep 문자열

문제 유형: 문자열 처리, 스택

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 1024MB

 

문제

skeep은 자신의 오프라인 팬클럽을 운영 중이다. 어느덧 인기스타가 된 skeep의 팬클럽에는 사람들이 몰려 공간이 부족해졌다.

이에 skeep은 자신의 진정한 팬만 팬클럽에 입장시키기로 결심했다.

skeep의 진정한 팬이라면 skeep이라는 문자열을 좋아할 것이라 믿으며, 이를 판별하기 위해 다음과 같은 문제를 준비했다.

길이가 N$N$인 알파벳 소문자로 구성된 문자열이 주어진다. 이 문자열에서 다음 작업을 원하는 만큼 수행할 수 있다.

• 문자열에서 skeep이라는 연속한 부분 문자열을 찾아 s를 제외한 소문자 알파벳 하나로 바꾼다.

이때, 수행할 수 있는 작업의 최대 횟수를 구해야 한다.

skeep의 팬인 당신은 팬클럽에 들어가기 위해 이 문제를 해결해야 한다. 문자열의 길이와 문자열이 주어질 때 정답을 출력하시오.

 

입력

첫 번째 줄에 문자열의 길이에 해당하는 정수N이 주어진다. (1≤N≤1000000) 

두 번째 줄에 알파벳 소문자로 구성된 길이가 N인 문자열이 주어진다.

 

출력

위 작업의 최대 횟수를 출력하시오.

 

풀이

스택을 통해 문자열의 문자를 순차적으로 읽으면서 저장한다.

만약 스택의 맨 끝이 'skeep'이 되었다면, skeep을 지우고 '*'로 대체한다.

skeep을 인식할 때, '*'가 와일드카드로서 허용될 수 있도록 해준다.

이 작업을 가능한 계속 반복해주면 된다.

 

코드

GO

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int32
	var s string
	fmt.Fscan(reader, &n)
	fmt.Fscan(reader, &s)

	ans := 0
	stk := make([]byte, 0)
	cmp := []byte{'s', 'k', 'e', 'e', 'p'}

	for _, ch := range s {
		stk = append(stk, byte(ch))

		for len(stk) >= 5 && stk[len(stk)-5] == cmp[0] {
			flag := true
			j := 1
			for i := len(stk) - 4; i < len(stk); i++ {
				if !(stk[i] == cmp[j] || stk[i] == '*') {
					flag = false
					break
				}
				j++
			}
			if flag {
				stk = stk[:len(stk)-4]
				stk[len(stk)-1] = '*'
				ans++
			} else {
				break
			}
		}
	}

	fmt.Fprintln(writer, ans)

}