백준 33516번 : skeep 문자열 풀이

1. 문제 링크

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

 

---

2. 접근 방법

문자열에서 skeep 이라는 연속한 부분 문자열을 s 를 제외한 소문자 알파벳으로 바꿀 수 있다는 조건이 큰 힌트가 되었다.

skeep 부분 문자열이 만들어지면 이를 와일드카드 문자 *로 바꿔서 다른 skeep 문자열을 만드는 데 사용할 수 있다는 의미이기 때문이다.

 

따라서 문자열에서 s 가 등장할 경우 스택에 넣어주고, k , e , p 가 등장할 경우 이전의 문자들을 확인하여 패턴과 일치하면 스택에 넣어주었고, 패턴과 일치하지 않는 문자가 등장할 경우 스택을 모두 비워주었다.

또한 스택의 top이 p 인 경우에는 skeep 을 스택에서 제거한 후 와일드카드 문자 * 를 넣어주었다. 이때 skeep 문자열을 * 로 치환하면 그 즉시 skee* 과 같이 만들어져서 새로운 skeep 을 만들어낼 수 있기 때문에 이 작업이 연쇄적으로 일어날 수 있도록 구현해야 한다.

 

예시 : sskeepeep

+ s       <- 새로운 skeep이 시작될 수 있으므로 스택에 넣는다.
s + s     <- 새로운 skeep이 시작될 수 있으므로 스택에 넣는다.
ss + k    <- 패턴과 일치하므로 스택에 넣는다.
ssk + e   <- 패턴과 일치하므로 스택에 넣는다.
sske + e  <- 패턴과 일치하므로 스택에 넣는다.
sskee + p <- 패턴과 일치하므로 스택에 넣는다.
sskeep    <- 만들어진 skeep을 와일드카드(*)로 바꾼다. (횟수: 1회)
s* + e    <- 패턴과 일치하므로 스택에 넣는다.
s*e + e   <- 패턴과 일치하므로 스택에 넣는다.
s*ee + p  <- 패턴과 일치하므로 스택에 넣는다.
s*eep     <- 만들어진 skeep을 와일드카드(*)로 바꾼다. (횟수: 2회)
*         <- 새로운 skeep은 s로 시작해야 하므로 스택을 비운다. (*은 s로 대체할 수 없기 때문)

 

예시 : skskyesep

+ s      <- 새로운 skeep이 시작될 수 있으므로 스택에 넣는다.
s + k    <- 패턴과 일치하므로 스택에 넣는다.
sk + s   <- 새로운 skeep이 시작될 수 있으므로 스택에 넣는다.
sks + k  <- 패턴과 일치하므로 스택에 넣는다.
sksk + y <- 패턴과 일치하지 않으므로 스택을 비운다.
+ e      <- 새로운 skeep은 s로 시작해야 하므로 스택을 비운다.
+ s      <- 새로운 skeep이 시작될 수 있으므로 스택에 넣는다.
s + e    <- 패턴과 일치하지 않으므로 스택을 비운다.
+ p      <- 새로운 skeep은 s로 시작해야 하므로 스택을 비운다.

 

로직은 대략 이 정도로 작성했다.

 

그런데 스택에 문자를 하나씩 넣도록 구현한다면, 스택에 문자를 하나하나 다 저장해야 하고, 가장 마지막으로 들어온 글자 5개를 확인할 때 스택에서 5개의 원소를 꺼내서 확인해야 한다.

따라서 이 부분을 개선하여 스택에 skeep 문자열이 얼마나 만들어졌는지를 나타내는 1부터 5까지의 정수를 대신 넣도록 구현했다. 5개의 문자 대신 하나의 정수를 넣으면 되므로 메모리를 아낄 수 있다.

 

개선한 로직은 다음과 같다.

1. 이번 문자가 s 인 경우
   • 스택에 1을 넣는다.
2. 이번 문자가 k 인 경우
   • 스택의 top이 1이면 1을 2로 바꾼다.
   • 그렇지 않다면 스택을 비운다.
3. 이번 문자가 e 인 경우
   • 스택의 top이 2이면 2를 3으로 바꾼다.
   • 스택의 top이 3이면 3을 4로 바꾼다.
   • 그렇지 않다면 스택을 비운다.
4. 이번 문자가 p 인 경우
   • 스택의 top이 4이면 4를 5로 바꾼다. 이후 5번 과정으로 이동한다.
   • 그렇지 않다면 스택을 비운다.
5. 스택의 top이 5인 경우
   • 답을 1 증가시키고, 스택에서 top 원소를 제거한 후, 스택에 원소가 남아있다면 스택의 새로운 top을 1 증가시킨다.
     • 스택의 새로운 top이 5가 되었다면 이 과정을 다시 실행한다.

 

코드로 표현하면 다음과 같다.

for (char &c : s) {
    if (c == 's') {
        stck.push(1);
    }
    else if (c == 'k') {
        if (!stck.empty() && stck.top() == 1) {
            stck.top()++;
        }
        else {
            clear_stack(stck);
        }
    }
    else if (c == 'e') {
        if (!stck.empty() && (stck.top() == 2 || stck.top() == 3)) {
            stck.top()++;
        }
        else {
            clear_stack(stck);
        }
    }
    else if (c == 'p') {
        if (!stck.empty() && stck.top() == 4) {
            stck.top()++;
        }
        else {
            clear_stack(stck);
        }
    }
    else {
        clear_stack(stck);
    }

    while (!stck.empty() && stck.top() == 5) {
        ans++;
        stck.pop();

        if (!stck.empty()) {
            stck.top()++;
        }
    }
}

 

---

3. 전체 코드 (C++ & Java)

• C++ : https://github.com/infikei/algorithm/blob/main/baekjoon_all/33000%2B/boj_33516_contest150_B_P.cpp
• Java : https://github.com/infikei/algorithm/blob/main/baekjoon_all/33000%2B/boj_33516.java