[BOJ] 9935번: 문자열 폭발

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


문제 자체는 단순합니다. 이걸 정말 마음편하게 코딩한다면 전체에 대해서 폭발 문자열이 있는지 확인하고 제거, 제거가 한번이라도 일어났다면 다시 전체에 대해서 폭발 문자열이 있는지 확인하고 제거 뭐 이런식으로 하면 되겠지만


CCCCCCCCCC....CCC444444......4444

C4


라는 입력에 대해 생각해보면 대략 O(N^2)이 필요해서 시간내에 풀 수가 없습니다.


대신에 스택을 활용하면 됩니다.


문자열을 입력받는 대로 스택에 넣는데, 스택에는 {문자, 현재 문자가 폭발문자열에서 이어지는 값}을 넣습니다. 예를 들어


ADBABCD

ABC


라는 예제를 생각해보면 스택에는


{A, 1} / {D, 0} / {B, 0} / {A, 1} / {B, 2} / {C, 3} / {D,0}이 들어가게 됩니다.


이 때 폭발 문자열과 같은 길이가 스택으로 들어온다면(위의 예제에서 {C, 3}) 3개를 pop합니다. 이 작업을 반복한 후 스택을 역순으로 출력하면 답이 됩니다. 시간복잡도는 O(N)입니다.


https://github.com/blisstoner/BOJ/blob/master/9935.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 2231번: Digit Generator  (0) 2018.01.07
[BOJ] 10773번: 제로  (0) 2018.01.07
[BOJ] 2098번: 외판원 순회  (0) 2018.01.07
[BOJ] 1015번: 수열 정렬  (0) 2018.01.07
[BOJ] 1806번: 부분합  (0) 2018.01.07
[BOJ] 1890번: 점프  (0) 2018.01.07
  Comments