본문 바로가기

Algorithm

 (48)
[백준] Python - 2493 탑 문제 링크 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 풀이 탑의 제일 오른쪽부터 순회하기 위해 stack에 제일 오른쪽 탑의 높이와 인덱스를 추가한다. 순회하면서 현재 탑의 높이보다 왼쪽 탑이 낮다면, stack에 현재 탑도 추가해준다. 그리고 다음 왼쪽 탑과 비교하기 위해 반복문을 나온다. 그렇지 않다면, stack에서 꺼낸 탑의 번호에 마주친 왼쪽 탑의 번호를 result에 추가한다. stack에 있는 요소 모두 왼쪽 탑과 비교..
[백준] Python - 2800 괄호 제거 문제 링크 https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 문제 풀이 ()의 쌍을 찾는다. (ex. "(0/(0))"의 경우 [(3, 5), (0, 6)]) 조합으로 모든 경우의 수를 찾는다. 경우의 수에 따라 for 문을 돌면서 해당 자리를 비우고, result에 추가한다. 정렬하여 출력한다. 전체 코드 from itertools import combinations expression = input().stri..
[백준] Python - 10799 쇠막대기 풀고나니까 쉬운데.. 처음에 어떻게 풀어야 하는지 아이디어가 생기지 않아서 너무 어려웠다. 앞으로 많은 문제를 풀어서 여러 가지 접근 방법에 대한 아이디어를 얻어야겠다고 생각했다 ㅠㅠ 문제 링크 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 풀이 "(" 라면, 스택에 추가한다. ")" 인데 앞선 인덱스의 값이 "(" 였다면, 레이저이므로 그동안 스택에 쌓인 개수만큼 result에 더한다. 그 외의 경우는 ")" 다음에 ")"이 온 경우일 것이고, ..
[백준] Python - 1874 스택 수열 처음엔 문제 이해가 너무 되지 않아서.. 어려웠고, 이후엔 시간 초과가 계속 떴다 ㅠ 수정하다보니 불필요한 계산이 있었다는 것을 알게 되어서 수정하니 통과되었다! 문제 링크 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 풀이 m = [ 4, 3, 6, 8, 7, 5, 2, 1 ] 을 순회하면서 그 숫자(ex. 4) 만큼 l.append() 해준 뒤, cou..
[백준] Python - 20437 문자열 게임 2 문제 링크 https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 문제 풀이 주어진 문자열에서 k개 이상 문자를 포함하는 문자의 위치를 뽑아 list 형태로 dictionary에 넣어준다. 1번 결과로 나온 dictionary의 list를 시작 인덱스부터 k개까지 범위를 잡을 수 있는 만큼 순회한다. 해당 범위의 마지막 인덱스에서 처음 인덱스까지의 차를 저장하여 min, max값을 도출한다. 전체 코드 from collections import d..
[백준] Python - 1316 그룹 단어 체커 문제 링크 https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 문제 풀이 문자열의 문자가 다음 문자와 연속되는지 확인한다. 만약 연속되지 않는데, 이후 문자열에 해당 문자가 있다면 그룹 단어가 아니다. 전체 코드 num = int(input()) result = num for i in range(num) : word = list(input()) for s in range(len(word)-1) : if word[s]..
[백준] Python - 17413 단어 뒤집기2 문제 링크 https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 문제 풀이 '' 또는 '알파벳 소문자/숫자/공백'으로 이루어진 문자열을 찾아 words 변수에 담는다. (re.compile을 사용하여 정규 표현식을 컴파일) words를 순회하며 조건에 따라 result 변수에 이어 붙인다. 만약 '
[백준] Python - 21920 서로소 평균 문제 링크 https://www.acmicpc.net/problem/21920 21920번: 서로소 평균 첫 번째 줄에 입력될 수들의 개수 $N$이 주어진다. $(2 \le N \le 500,000)$ 두 번째 줄에는 수열 $A$를 이루는 자연수 $A_{i}$ 가 공백으로 구분되어 주어진다. $(2 \le A_{i} \le 1,000,000)$ 수열 $A$에 $X$와 서로 www.acmicpc.net 문제 풀이 처음에는 각 수마다 약수를 구해서 서로소(1 이외의 공약수가 없음)인지 비교하여 풀이하려고 했다. 하지만 계속해서 시간초과 ㅠㅠ 결국 파이썬의 math.gcd()를 사용하여 코드를 완성했다... 아래 더보기는 직접 약수를 구해주는 함수를 구현하여 이용한 코드(다른 블로그 도움..)인데, 시간이 더..

티스토리툴바