2018. 1. 7. 13:45, 알고리즘/BOJ
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)입니다.
'알고리즘 > 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