[백준 9935번] 문자열 폭발

난이도: 골드 4

문제 링크: www.acmicpc.net/problem/9935

9935번: 문자열 폭발

백준 9935번: 문자열 폭발

문자열을 다루는 문제입니다.

처음에는 정말로 단순하게 접근했다가,

답은 잘 나오는데 시간 초과가 떠 버리는 바람에 (...)

결국 다시 생각해서 접근했습니다.

제가 직접적으로 스택을 사용하지는 않았지만, 문제 분류 중에 스택이 적혀 있습니다.

실제로 많은 분들이 스택을 이용해서 문제를 해결하셨더라구요.

 

제가 접근한 방법은 아래와 같습니다.

• 결과 문자열을 담기 위한 char형 array를 전역으로 선언한다.
• 문자열을 앞에서부터 순서대로, 검사한다. 검사하는 대상은 '폭발 문자열의 맨 마지막 문자' 입니다.
• 일치하면, 그때부터 폭발 문자열의 길이만큼 거슬러 올라가며 문자를 하나씩 검사해 봅니다.
• 만약 폭발 문자열과 전체가 일치하면, 문자열의 인덱스 idx를 폭발 문자열만큼 값을 줄입니다.
• 위 과정을 완료하고 나면, 문자열 전체에 대해 훨씬 적은 시간 안에 폭발 문자열을 전부 확인할 수 있습니다.
• 완료 후 맨 뒤에 '\0'을 추가해 줍니다. 이는 문자열의 마지막을 나타냅니다.
• 결과에 맞는 값을 출력해 줍니다.

실제 구현은 그렇게 어렵지 않은 문제였습니다.

이런 류의 문제는 늘 코드로 작성하는 시간보다 종이에 구상하는 시간이 더 오래 걸리네요.

 

*코딩 스터디 그룹을 통해 접한 문제입니다 (10주차 3번 문제). 링크