[백준] 9935번 - 문자열 폭발 / 골드4 / 파이썬 풀이

2022. 1. 12. 00:10·알고리즘 공부

문제 링크

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

 

9935번: 문자열 폭발

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모

www.acmicpc.net

 

시간 제한 : 2초

메모리 제한 : 128 MB

 

문제 요약

  • 문자열 속에 '폭발 문자열'이 존재하면 해당 문자열은 삭제됨.
    (문자열 : 입력으로 주어짐 / 폭발 문자열 : 입력으로 주어짐)
  • '폭발 문자열'이 폭발하면, 즉, 사라지고 나면 남은 문자열은 순서대로 이어 붙임.
  • 이렇게 이어 붙여진 문자열에 폭발 문자열이 또 포함되어 있을 수 있음.
  • 폭발 문자열이 문자열에서 사라질때까지 폭발이 계속됨.
  • 제약사항
    - 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않음.

  • 문제 : 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구한다.

  • 종료 조건
    - 폭발 문자열이 사라지면 종료됨.
    - 모든 문자열이 폭발되면 "FRULA" 를 출력.

 

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

예제 입력 1

mirkovC4nizCC44
C4

예제 출력 1

mirkovniz

 

예제 입력 2

12ab112ab2ab
12ab

예제 출력 2

FRULA

풀이

 

"폭발 문자열의 맨끝 문자의 일치여부만 조건문으로 넣어도, 문자열을 일일히 다 비교하지 않아도 된다!"

"""
    1. 입력문자열을 앞에서부터 차례차례 한 글자씩 스택에 push 합니다.
    2. 현재 글자가 폭발 문자열의 마지막 글자와 일치하면 
스택의 top부터 폭발문자열의 길이까지 확인하여 폭발문자열이 만들어지는지 확인합니다.
    3. 폭발문자열이 만들어진다면 만들어지는 폭발문자열을 스택에서 pop합니다.
    4. 1~3을 반복합니다.
    5. 문자열 순회를 마치고 스택이 비어있으면, FRULA를 출력, 비어있지 않다면 스택 속 문자열을 차례로 출력합니다.
"""
 
def main():
 
    string = input()    # 전체 문자열
    bomb = input()      # 폭발 문자열
 
    bomb_lastChar = bomb[-1] # 폭발 문자열의 마지막 글자
    stack = []
    bomb_length = len(bomb)  # 폭발 문자열의 길이
 
    for char in string:
        stack.append(char)		# 한 글자씩 스택에 넣기.
        if char == bomb_lastChar and ''.join(stack[-bomb_length:]) == bomb:
        # 현재 스택에 넣은 문자가 폭발 문자열의 맨끝 문자와 일치하고,
	# 스택에서 폭발문자열의 길이만큼 문자열을 추출했을 때, 이 문자열이 폭발문자열과 일치한다면
            del stack[-bomb_length:]			# 해당 문자열을 스택에서 제거한다.
 
    answer = ''.join(stack)
 
    if answer == '':
        print("FRULA")
    else:
        print(answer)
 
 
if __name__ == '__main__':
    main()

 

참고

https://mytodays.tistory.com/23

 

[백준 9935] 문자열 폭발 - python

문제링크: https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지

mytodays.tistory.com

 

'알고리즘 공부' 카테고리의 다른 글

[백준] 1958번 - LCS 3 / 골드 3 / 파이썬 풀이  (0) 2022.02.14
[백준] 1507번 - 궁금한 민호 / 골드 3 / 파이썬 풀이  (0) 2022.01.31
[백준] 2252번 - 줄 세우기 / 골드 3 / 파이썬 풀이  (0) 2022.01.23
[백준] 1915번 - 가장 큰 정사각형 / 골드4 / 파이썬 풀이  (0) 2022.01.11
[백준] 16236번 - 아기상어 / 골드4 / 파이썬 풀이  (0) 2021.12.21
'알고리즘 공부' 카테고리의 다른 글
  • [백준] 1507번 - 궁금한 민호 / 골드 3 / 파이썬 풀이
  • [백준] 2252번 - 줄 세우기 / 골드 3 / 파이썬 풀이
  • [백준] 1915번 - 가장 큰 정사각형 / 골드4 / 파이썬 풀이
  • [백준] 16236번 - 아기상어 / 골드4 / 파이썬 풀이
코_노
코_노
일상의 불편함을 기술로서 해결하기 위해 노력하는 IT 엔지니어입니다. Contact point) jjh3706@gmail.com
  • 코_노
    코딩하는 주노 이야기
    코_노
  • 전체
    오늘
    어제
    • 코딩 이야기 (121)
      • DB (35)
        • SQL Server (MSSQL) (27)
        • MongoDB (2)
        • Hadoop Ecosystem (0)
        • SQLP 공부 (2)
      • 데이터 엔지니어링 (0)
        • Spark (0)
      • Middleware (21)
        • 웹서버 (7)
        • WAS (6)
        • WSGI (3)
        • 기타 (5)
      • OS (10)
        • Linux (7)
        • Windows (3)
      • Network (8)
      • Cloud (1)
        • AWS (1)
      • DevOps (8)
        • Container & K8S (0)
        • Github (3)
        • Ansible (2)
        • Terraform (3)
      • Security (3)
      • Observability (5)
      • CS 지식 | 기초 용어,개념 (7)
      • Python (1)
        • Flask (0)
      • Java (7)
        • JPA (0)
      • 안드로이드 (1)
      • 알고리즘 공부 (14)
  • 블로그 메뉴

    • 홈
    • 코딩 이야기
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    jvm 실행 옵션
    SSMS
    SAS
    SQL Server
    백준 알고리즘
    MongoDB Sharding
    백준 python
    백준 파이썬
    SQL Server 2019
    백준
    db
    SAS 아키텍처
    SQL Server 2019 Restore
    Windows AD
    백준 골드4
    백준 골드2
    백준 골드 2
    SAS Intelligence Platform
    DBA
    MSSQL
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.6
코_노
[백준] 9935번 - 문자열 폭발 / 골드4 / 파이썬 풀이
상단으로

티스토리툴바