조준장 개발자 생존기

문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 알고리즘 - 반복문을 통해 문자열을 확인한다. - 스택에 문자를 하나씩 추가한다. - 스택의 마지막 요소와 폭발 문자열의 마지막 요소가 같고 스택의 맨 뒤에 폭발 문자열 길이만큼 짜른 것의 문자열과 폭발 문자열이 같으면 스택의 맨 뒤에 폭발 문자열 길이만큼 짜른 것의 문자열을 제거한다. 코드 import sys s = str(sys.stdin.readline().strip()) bomb = str(sys.stdin.readline().stri..

문제 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 알고리즘 - Union-find 알고리즘을 통해 문제를 수행한다. - 현재 도시와 연결되어있는 도시를 확인하고 연결되어 있다면 두개의 도시를 합집합으로 표현한다. - set() 함수를 통해 합집합을 찾는다. 즉, 모든 도시가 연결되어있는지 확인한다. 코드 import sys sys.setrecursionlimit(10 ** 6) # a가 속한 집합과 b가 속한 집합 합치기 def union(x, y): x = find(x) y = find(y) # a와 b..

문제 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 알고리즘 - bfs 탐색과 위상 정렬을 통해 문제를 수행한다. - 선행 문제의 개수를 반복문을 통해 확인한다. - 선행 문제 필요 없이 풀 수 있는 문제부터 힙 푸시하여 탐색한다. - 연결된 문제를 탐색하면서 선행 문제의 개수를 -1 해준다. - 선행 문제의 개수가 0인 문제를 힙 푸시하여 탐색한다. - 탐색한 문제는 결과 리스트에 추가한다. 코드 import sys import heapq # bfs 탐색 def bfs(): ..

문제 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 알고리즘 - 테스트 케이스만큼 반복한다. - 반복문을 통해 강산이의 입력 순서를 확인한다. - 커서 기준으로 res 리스트는 왼쪽에 있는 입력, stack 리스트는 오른쪽에 있는 입력이다. - 커서 기준에 따라 입력을 수행해준다. 코드 import sys t = int(sys.stdin.readline()) # 테스트 케이스만큼 반복 for _ in range(t): l = list(map(str, sys.stdin.readline().strip()..

문제 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 알고리즘 - collections 모듈에 Counter 클래스를 사용하여 문제를 수행한다. - 의상의 이름과 종류를 입력받아 종류를 리스트에 추가한다. - 의상의 종류를 추가한 리스트에 Counter 함수를 통해 개수를 확인한다. - 알몸도 옷이라고 생각하여 각 의상의 + 1 을 해준 후 각 의상의 종류를 곱해준다. - 곱하게 되면 모든 조합이 나오고 이때, 모든 ..

문제 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 알고리즘 - 입력받은 괄호를 반복문을 통해 확인한다. - "(" 와 "[" 이면 스택에 추가해준다. - ")" 경우와 "]" 경우는 조건문을 통해 나눠서 코드를 작성한다. 코드 import sys s = str(sys.stdin.readline().strip()) stack = [] # 입력받은 괄호를 반복문을 통해 확인한다. for i in s: # i가 "(", "[" 일 경우 스택에 추가 if i == "(" or i == "[": stack.app..

문제 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 알고리즘 - 포켓몬의 알파벳 문제는 딕셔너리 자료형으로 수행하고 숫자 문제는 리스트 자료형으로 수행한다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) book_dic = {} book_list = [] # 포켓몬의 개수를 반복하여 포켓몬의 이름을 입력받는다. for i in range(n): poketmon = sys.stdin.readline().rstrip() #..

문제 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 알고리즘 - 반복문을 통해 탑의 높이를 확인한다. - 스택에 탑이 있는지 확인하고 스택에 탑이 있으면 현재 탑과 비교하고 없으면 스택에 현재 탑의 높이를 추가한다. - 스택에 탑의 높이를 추가할 때 탑의 위치까지 묶어서 추가하여 탑의 위치를 쉽게 찾게 한다. - 코드 주석을 확인하면서 보면 더 이해하기 쉬울 것이다. 코드 import sys n = int(sys.stdin.readline()) top = list(map(int, sys.stdin.read..

문제 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 알고리즘 - heapq 모듈을 사용하여 문제를 수행한다. - 연산의 개수만큼 반복하여 연산에 대한 정보를 입력받는다. - 배열의 x 값을 넣을 때 절댓값을 우선순위로 하여 힙 푸시한다. 코드 import sys import heapq n = int(sys.stdin.readline()) heap = [] # 연산의 개수만큼 반복하여 연산에 대한 정보를 입력받아 수행한다. for i in range(n): x = int(sys.stdin...

문제 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 알고리즘 - re 모듈과 deque 모듈을 사용하여 문제를 수행한다. - 테스트 케이스만큼 반복하여 문제의 최종 결과를 출력한다. - 수행해야할 함수를 반복하여 try- except문을 통해 조건을 수행한다. - 에러의 유무에 따라 최종 결과값을 출력한다. 코드 import sys import re from collections import deque t = int(sys.stdin.readline()) # 테스트 케이스만큼 반복하여 문제를 수행 for _ in range(t): p = sys.stdin.read..