[Algorithm] cpp-python 백준 33651번: Vandalism

문제

링크: https://www.acmicpc.net/problem/33651
요약: UAPC에서 몇 글자를 지워 얻은 s가 주어질 때, 제거된 문자들을 원래 순서대로 출력.

입력/출력

1
2
3
4
5
입력
s  (빈 문자열 아님, 길이 ≤ 3, UAPC에서 일부를 삭제해 얻은 부분수열)

출력
UAPC에서 제거된 문자들을 원래 순서대로 이어붙인 문자열

예시

1
2
3
4
5
6
7
8
입력: UAC
출력: P

입력: P
출력: UAC

입력: UC
출력: AP

접근 개요

핵심 관찰: 목표는 고정 패턴 UAPC에서 입력 s를 얻기 위해 빠진 문자들의 순서를 복원하는 것.
두 포인터: t = "UAPC"를 좌→우로 순회하며 s와 일치하면 s 포인터 전진, 불일치면 해당 문자를 제거 목록에 추가.
고정 길이(4) 패턴이므로 한 번의 선형 스캔으로 충분하며 구현이 단순하고 안전합니다.

알고리즘

t = "UAPC", j = 0, removed = ""로 초기화
t의 각 문자 c에 대해
- j < |s|이고 s[j] == c라면 j++
- 아니면 removed += c
removed 출력

정당성 요약:

s는 UAPC의 부분수열이므로 UAPC를 좌→우로 훑으며 일치 문자를 건너뛰면, 건너뛰지 못한 문자들은 모두 삭제된 문자이며 그 상대적 순서도 원본 순서를 보존합니다.

복잡도

시간: O(|UAPC|) = O(1)
공간: O(1)

구현 (C++)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	string s;
	if (!(cin >> s)) return 0;

	string t = "UAPC", removed;
	size_t j = 0;
	for (char c : t) {
		if (j < s.size() && c == s[j]) j++;
		else removed.push_back(c);
	}
	cout << removed;
	return 0;
}

구현 (Python)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
import sys

def solve():
    s = sys.stdin.readline().strip()
    t = "UAPC"
    j = 0
    removed = []
    for c in t:
        if j < len(s) and s[j] == c:
            j += 1
        else:
            removed.append(c)
    print("".join(removed))

if __name__ == "__main__":
    solve()