[Coding Test]/[백준]

[백준] 11899 파이썬(python) : 괄호 끼워넣기 - 필요한 괄호 개수 세기

https://www.acmicpc.net/problem/11899 11899번: 괄호 끼워넣기 첫 번째 줄에 S를 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 출력합니다. 불가능한 경우는 주어지지 않습니다. www.acmicpc.net import sys string = sys.stdin.readline().rstrip() stack, cnt = [], 0 #1 for char in string: if char == '(': #2 stack.append(char) else: if stack and stack[-1] == '(': #3 stack.pop() elif not stack: #4 cnt += 1 cnt += len(stack) #5 print(cnt) #1 : sta..

[백준] 2800 파이썬(python) : 괄호 제거

2800번 : 괄호 제거   import sysfrom itertools import combinationsstring = sys.stdin.readline().rstrip()idx_stack, stack, answer = [], [], set() #1for idx, v in enumerate(list(string)): #2 if v == '(': #3 stack.append(idx) elif v == ')': #4 start = stack.pop() end = idx idx_stack.append([start, end])for i in range(1, len(idx_stack)+1): #5 for j in combinations(idx_..

[백준] 16210 파이썬(python) : PPAP

https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net PPAP에서 P가 PPAP로 바뀔 수 있다고 했다. 그렇다면 경우는 4가지가 나온다. 1. (PPAP)PAP 2. P(PPAP)AP 3. PPA(PPAP) 4. PPAP 이 4가지를 고려하며 코드를 짜야한다. import sys string = sys.stdin.readline().rstrip() stack = [] ppap = [ 'P', 'P', 'A', 'P' ] #1 for i in range(len(string)): stack.append..

[백준] 1662 파이썬(python) : 압축

https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 번역을 해서 가져온 외국 문제는 설명이 늘 부족하다. 예제1의 33(562(71(9)))는 K(Q)의 형태로 되어있는데 전개를 하면 33(562(79))가 되고 33(567979)가 되고 마지막으로 3567979567979567979가 된다. 그래서 총 길이는 19가 된다. import sys string = sys.stdin.readline().rstrip() stack, cnt = [],..

[백준] 2493 파이썬(python) : 탑 - (monotone stack 알고리즘)

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 단조스택 문제다. 오른쪽에서 부터 보기 시작하면 오름차순이지만 왼쪽에서 보면 내림차순이다. 결국 원소의 위치 그러니까 인덱스를 출력해줘야 하는 문제여서 stack에 값이 아닌 인덱스를 삽입해준다. import sys n = int(sys.stdin.readline()) tower = list(map(int, sys.stdin.readline().split())) res, stack = [0]*n..

[백준] 6198 파이썬(python) : 옥상 정원 꾸미기

https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 이중 for문으로 풀었더니 시간초과가 나왔다. 그도 그럴게 이중for문으로 해결할 수 있는 간단한 문제가 골드 난이도를 가지고 있을것 같지 않았다. 이중for문으로 시간초과 나온 코드) import sys n = int(sys.stdin.readline()) building = [ int(sys.stdin.readline()) for _ in range(n) ] answer, cnt = 0..