문제 95

쉬운 문제만 출제할게요

내 상태: 미제출
난이도: 95번 문제 난이도 보기

Gold V
출제자: rlatjwls7882
시간 제한: 1000 ms
메모리 제한: 512 MB

태그 보기

그리디 알고리즘문자열

어느 날 출제진은 다음과 같은 메시지를 받았다.

그 이후 출제진은 쉬워 보이지만 실제로는 쉽지 않은 문제를 출제하기 시작했다.

세종이는 문제의 제목만 보고 난이도를 판단한다. 제목이 다음 조건을 모두 만족하면 쉬운 문제라고 판단한다.

EASY가 부분 문자열로 포함되어 있다.
HARD가 부분 문자열로 포함되어 있지 않다.

예를 들어, HARDEASY는 쉬운 문제가 아니고 HAEASYRD는 쉬운 문제이다.

세종이는 주어진 제목을 쉬운 문제의 제목으로 만들기 위해, 연속한 하나 이상의 문자를 최대 한 번 삭제할 수 있다.

예를 들어, EAHARDSY에서 $3$번째 문자부터 $6$번째 문자까지 삭제하면 EASY가 된다.

세종이가 주어진 제목을 쉬운 문제의 제목으로 만들 수 있는지 구하라.

입력

첫 번째 줄에 문제의 제목을 의미하는 알파벳 대문자로 이루어진 문자열 $S$가 주어진다. $(1 \le \lvert S\rvert \le 100\,000)$

출력

첫 번째 줄에 세종이가 주어진 제목을 쉬운 문제의 제목으로 만들 수 있다면 Yes를, 그렇지 않다면 No를 출력한다.

예제 입력 1

EASYHARD

예제 출력 1

Yes

예제 입력 2

EAHARDSY

예제 출력 2

Yes

예제 입력 3

HARD

예제 출력 3

No

노트

$\lvert S \rvert$는 문자열 $S$의 길이를 의미한다.

문자열 $T$가 문자열 $S$의 부분 문자열이라는 것은 어떤 두 정수 $l$, $r$ $(1 \le l \le r \le \lvert S \rvert)$에 대해 $T=S_lS_{l+1}\cdots S_r$인 경우를 뜻한다.

해당 메시지를 받기 전까지 이 문제는 출제진이 준비한 문제 중 난이도가 높은 편이었다.

공식 해설 풀이 스포일러 보기 접기

남길 EASY를 기준으로 나누기

한 구간을 삭제하면 원래 문자열의 접두사와 접미사가 이어진다. 최종 EASY는 왼쪽에 온전히 남거나, 오른쪽에 온전히 남거나, 새로 이은 경계에 걸쳐 만들어진다.

이를 하나로 다루기 위해 EASY를 다음 다섯 방식으로 나눈다.
\[ (\text{빈 문자열},\text{EASY}),\quad(\text{E},\text{ASY}),\quad (\text{EA},\text{SY}),\quad(\text{EAS},\text{Y}),\quad (\text{EASY},\text{빈 문자열}). \]

각 분할에서 왼쪽 조각은 가장 이른 등장을, 오른쪽 조각은 가장 늦은 등장을 고른다. 두 조각이 겹치지 않는다면 왼쪽 조각의 끝까지의 접두사와 오른쪽 조각부터의 접미사를 남기고 그 사이를 삭제한다. 빈 왼쪽 조각은 접두사를 전부 버리는 뜻이고, 빈 오른쪽 조각은 접미사를 전부 버리는 뜻이다.

이 결과에 HARD가 없다면 Yes이다. 선택한 두 조각이 이어져 EASY는 반드시 존재한다. 지울 사이 구간이 비어 있으면 삭제하지 않은 경우로 보면 된다.

가장 바깥의 등장만 고르면 되는 이유

어떤 분할로 성공하는 삭제가 있다고 하자. 왼쪽 조각을 더 앞으로 옮기면 남기는 접두사가 짧아지고, 오른쪽 조각을 더 뒤로 옮기면 남기는 접미사가 짧아진다. 따라서 이 두 조각 내부에 새로운 HARD가 생기지는 않는다.

새 연결 경계를 가로지르는 HARD도 생길 수 없다. 경계의 두 문자는 EA, AS, SY 중 하나인데, 이 인접 문자쌍은 HARD 안에 없다. 한 조각이 비어 있으면 새 연결 경계 자체가 없다.

EASY가 한쪽에 온전히 남는 해도 빈 조각을 사용한 첫째나 마지막 분할에 포함된다. 따라서 가능한 해가 있다면 다섯 후보 중 하나가 반드시 성공한다. 모두 실패하면 No이다.

패턴 길이와 분할 수가 상수이므로 문자열 길이를 $n$이라 할 때 시간복잡도와 공간복잡도는 $O(n)$이다.

구현 · 언어별 풀이

C++ 구현

다섯 분할마다 왼쪽 조각의 첫 등장은 find, 오른쪽 조각의 마지막 등장은 rfind로 찾는다. 빈 조각은 시작 또는 끝 경계로 따로 처리하고, string::npos인지 확인한 뒤에만 인덱스 계산을 한다. 남긴 두 부분을 이어 후보를 만들고 find("HARD")로 검사한다. 후보가 다섯 개뿐이므로 문자열 복사도 전체 선형 시간이다.

C 구현

EASY의 다섯 분할마다 왼쪽 조각의 가장 이른 끝과 오른쪽 조각의 가장 늦은 시작을 찾는다. 빈 조각은 문자열 양 끝으로 처리한다. 두 구간이 겹치지 않을 때만 연결하고 strstr로 HARD 존재를 확인할 수 있다.

Python 구현

str.find와 rfind로 왼쪽·오른쪽 조각을 찾는다. 두 선택 구간이 겹치지 않는지 검사한 뒤 prefix+suffix를 만들고 "HARD" not in candidate인지 확인한다. 빈 조각의 끝·시작은 0,len(S)으로 둔다.

s에서 다섯 분할을 직접 확인한다. 빈 조각과 찾지 못한 조각을 구분한 뒤 경계를 계산한다.

ok = False
for k in range(5):
    left, right = "EASY"[:k], "EASY"[k:]
    p, q = s.find(left), s.rfind(right)
    if p == -1 or q == -1:
        continue
    end = p + len(left) if left else 0
    start = q if right else len(s)
    if end <= start and "HARD" not in s[:end] + s[start:]:
        ok = True
        break

Java 구현

indexOf와 lastIndexOf로 각 조각 위치를 찾는다. -1일 때 인덱스 계산을 하지 않고 빈 조각은 별도 처리한다. 후보 문자열에서 contains("HARD")를 검사한다.

s에서 찾지 못한 위치는 건너뛰고, 빈 조각의 경계는 문자열 양 끝으로 둔다.

boolean ok = false;
for (int k = 0; k <= 4; k++) {
    String left = "EASY".substring(0, k);
    String right = "EASY".substring(k);
    int p = s.indexOf(left), q = s.lastIndexOf(right);
    if (p < 0 || q < 0) continue;
    int end = left.isEmpty() ? 0 : p + left.length();
    int start = right.isEmpty() ? s.length() : q;
    if (end <= start && !(s.substring(0, end) + s.substring(start)).contains("HARD")) {
        ok = true;
        break;
    }
}

Rust 구현

s.find(), s.rfind()의 Option을 확인한 뒤 경계를 계산한다. 입력이 대문자 ASCII라 바이트 슬라이스 경계가 문자 경계와 같다. prefix와 suffix가 겹치지 않을 때만 연결하고 contains("HARD")를 확인한다.

대문자 ASCII 문자열의 위치는 바이트 인덱스로 다뤄도 된다. 두 조각을 찾았을 때만 남길 문자열을 만든다.

let mut ok = false;
for k in 0..=4 {
    let (left, right) = "EASY".split_at(k);
    if let (Some(p), Some(q)) = (s.find(left), s.rfind(right)) {
        let end = if left.is_empty() { 0 } else { p + left.len() };
        let start = if right.is_empty() { s.len() } else { q };
        if end <= start {
            let candidate = format!("{}{}", &s[..end], &s[start..]);
            if !candidate.contains("HARD") {
                ok = true;
                break;
            }
        }
    }
}

JavaScript 구현

다섯 분할의 왼쪽 조각은 indexOf, 오른쪽 조각은 lastIndexOf로 찾는다. 빈 조각은 각각 끝점 $0$, 시작점 $|S|$로 직접 처리하면 찾지 못한 경우의 $-1$과 섞이지 않는다.

let ok = false;
for (let k = 0; k <= 4; k++) {
    const left = 'EASY'.slice(0, k);
    const right = 'EASY'.slice(k);
    const i = left ? s.indexOf(left) : 0;
    const j = right ? s.lastIndexOf(right) : s.length;
    if (i < 0 || j < 0) continue;
    const end = i + left.length;
    if (end <= j && !(s.slice(0, end) + s.slice(j)).includes('HARD'))
        ok = true;
}
console.log(ok ? 'Yes' : 'No');

남긴 접두사·접미사를 이은 뒤 HARD가 없는지 검사한다. 분할 수와 패턴 길이가 상수이고 제목이 $100\,000$글자 이하이므로 이 다섯 문자열 후보는 충분히 작다. 모든 삭제 구간을 열거하거나 별도 문자열 검색 자료구조를 만들지 않는다.

제출

언어