[백준/Python] 9935번. 문자열 폭발

문제https://www.acmicpc.net/problem/9935  풀이문자열에서 폭발 문자열이 없어질때까지 반복해서 찾아 지워나간다면 이론적으로 풀리기야 하겠지만 시간이 초과된다. 스택을 이용하면 전체 문자열에서 폭발 문자열을 찾는데 소요되는 시간, 문자열에서 폭발문자열을 반복하며 도려내어 새로운 문자열을 만드는 시간을 단축하여 빠르게 해결이 가능하다. 문자열을 앞에서부터 한글자씩 끝까지 순회하며 스택에 push하면서 스택의 윗부분과 폭발 문자열이 일치한다면 폭발 문자열의 길이만큼 pop해주기만 하면 한번의 순회로 쉽게 해결이 가능하다.    정답 코드msg = input()bomb = list(input())answerStack = []for letter in msg: answerStack...

• format_list_bulleted 알고리즘/백준
• · 2024. 11. 15.
• textsms

[백준/Python] 11279번. 최대 힙

문제https://www.acmicpc.net/problem/11279   풀이제목 그대로 최대 힙 자료구조를 사용하는 문제이다.최대 힙은 부모 노드가 자식 노드보다 큰 값을 가지는 완전 이진 트리로 구현된 자료구조이고따라서 최대힙의 Root 노드에는 항상 전체 트리의 최대값이 저장된다. 파이썬은 편리하게도 heapq 모듈을 import하면 최소 힙 자료구조를 사용할 수 있지만, 애석하게도 최대 힙은 구현이 되어있지 않은데, 모든 값에 -를 붙여서 뒤집으면 최소힙을 최대 힙처럼 사용이 가능하다.(마이너스를 붙여서 야매로 뒤집는건 최대 힙 말고도 내림차순 정렬 할때도 유용하다.) heap 모듈은 힙으로 사용할 빈 리스트를 선언하고 heapq.heappush(리스트, 값)으로 값을 push하고heapq.he..

• format_list_bulleted 알고리즘/백준
• · 2024. 11. 15.
• textsms

[백준/Python] 1927번. 최소 힙

문제https://www.acmicpc.net/problem/1927   풀이제목 그대로 최소 힙 자료구조를 사용하는 문제이다.최소 힙은 부모 노드가 자식 노드보다 작은 값을 가지는 완전 이진 트리로 구현된 자료구조이고따라서 최소힙의 Root 노드에는 항상 전체 트리의 최솟값이 저장된다. 파이썬은 편리하게도 heapq 모듈을 import하면 최소 힙 자료구조를 사용할 수 있다. 힙으로 사용할 빈 리스트를 선언하고 heapq.heappush(리스트, 값)으로 값을 push하고heapq.heappop(리스트)로 Root노드의 최소 값을 pop하다. 간단하다. heapq 모듈은 최대 힙의 구현은 없지만 최소 힙을 이용해 최대 힙도 구현할 수 있다.    정답 코드import heapqimport sysinpu..

• format_list_bulleted 알고리즘/백준
• · 2024. 11. 15.
• textsms