[Coding Test]

[백준] 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..

[백준] 2304 파이썬(python) : 창고 다각형

https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 문제가 어려운데 해결방법만 알면 난이도가 낮아진다고 느낀다. NHN에 비슷한 문제가 나왔었다고 한다. 문제의 그림을 예시로 들면 왼쪽에서 시작해서 가장 큰 높이를 가진 기둥까지의 높이를 전부 더한 값과 오른쪽에서 시작해서 가장 큰 높이를 가진 기둥 직전까지의 높이를 더한 값 두 개를 더하면 정답이 나온다. 즉, 왼쪽은 4+4+6+6+6+6+10 = 42이고 오른쪽은 8+8+8+8+..

[백준] 12789 파이썬(python) : 도키도키 간식드리미 - (올바른배열인지확인)

12789번: 도키도키 간식드리미   빠져 나갈 수 있는 방법은 단 2가지이다. 줄을 서있는 장소와 대기열에서 빠져나오는것이다. 줄을 서있는 장소는 FIFO이 가능하므로 queue라고 할 수 있고, 대기열은 FILO이므로 스택으로 볼 수 있다. queue의 가장 왼쪽에서 번호표와 일치하면 빠져나갈 수 있고 stack의 top에서 번호표와 일치하면 빠져나갈 수 있다.   queue도 stack도 모두 잘 끝내서 종료된 모습이다.    out_num가 3인데 stack의 top은 4여서 꺼내지 못하고 종료하는 상황이다.  from collections import dequeimport sysn = int(sys.stdin.readline())queue = deque(map(int, sys.stdin.read..

[백준] 4889 파이썬(python) : 안정적인 문자열 - 개수 세기

https://www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우 www.acmicpc.net 이 루트를 반복하면 된다. 1. { 이면 스택에 삽입 2. } 인데 스택에 원소가 있고 stack[-1] == '{'이면 stack.pop() 수행 3. } 인데 스택이 비어있으면 stack에 { 를 삽입 (바꿔준다고 생각) 그리고 cnt +1 추가 4. stack에 들어있는건 여는 괄호 {뿐이니까 남아있다면 그것의 절반의 숫자를 cnt에 추가(절반은 닫는 괄호 }로 바꿔주는거니까) impor..