본문 바로가기

백준93

AC - 5430번 입력받는 배열을 파싱한 후 deque로 변환하여 다루면 빠른 속도로 해결할 수 있다. deque의 속도는 O(1) 이고, 리스트의 속도는 O(n)이기 때문이다. 하지만 deque의 reverse(deque.reverse())는 속도가 리스트의 reverse와 비슷하게 느리다. 따라서 deque로 구현하되 reverse를 최대한 적게 사용하는 방법으로 코드를 짜야한다. 문제에서 입력받는 수행할 함수 p에서 R이 나올 때 마다 reverse를 하지말고, 상황에 따라서 deque.pop()과 deque.popleft()를 적절하게 사용해주면 된다. 그리고 deque.reverse()는 가장 마지막에 검사하여 적용해주면 된다. from collections import deque import sys n = in.. 2022. 9. 13.
주유소 - 13305 기름값이 가장 적은 도시가 어디인지 먼저 알아내야한다. 그 도시가 처음 출발하는 도시면 간단하고, 아닐 경우, 처음 도시에서 기름값이 가장 싼 도시까지 가는 도중에 그나마 기름값이 싼곳을 거쳐가면 최소비용을 구할 수 있다. 그리고 가장 마지막 도시의 기름값을 알 필요가 없어서 저장하지 않거나 입력받고 삭제하는 것을 추천한다. n = int(input()) distance = list(map(int, input().split())) cost = list(map(int, input().split())) cost.pop() first_cost = cost[0] min_cost = min(cost) min_cost_loc = cost.index(min_cost) pay = 0 p_cost = first_cost.. 2022. 9. 12.
DFS와 BFS - 1260번 DFS는 재귀로 구현하고, BFS는 스택으로 구현한다. 먼저 그래프를 만들어준다. DFS 방문했던 곳을 체크하기위한 배열을 준비한다. 방문시 방문했다고 표시한다. 그 다음 방문한 곳의 그래프를 검사하여 방문하지 않은 곳을 DFS함수에 넣어서 재귀적으로 탐색을 진행한다. BFS 방문했던 곳을 체크하기위한 배열을 준비한다. 방문시 방문했다고 표시한다. 방문한 곳을 스택에 넣는다. 스택에서 꺼내서 출력을 한다. 꺼낸 것의 그래프를 탐색하여 아직 방문하지 않은 곳을 스택에 넣는다. 스택이 빌 때까지 반복하면 모든 끝까지 탐색할 수 있다. import queue import sys from collections import deque input = sys.stdin.readline nodes, edges, sta.. 2022. 9. 10.
나무 자르기 - 2805번 이분탐색으로 해결해야 시간초과가 안생기는 문제이다. 처음에 나무 최대 길이에서 1씩 줄여가면서 답에 근접할 때 멈추는 방식으로 풀었었는데 역시나 시간초과가 발생했다. 이분탐색을 이용하여 나무 최대길이를 high, 최소길이인 0을 low로 둔다. 무한루프를 통해 중간길이를 계산하며 나무가 잘린 길이를 계산해준다. 만약, 나무가 잘린 길이가 너무 많다면 low = mid로 해주고, 나무를 덜 잘랐다면 high = mid를 해준다. 나무를 자를 길이는 양의 정수로만 계산되므로 무한루프의 종료지점을 high - low > 1로 해준다. import sys input = sys.stdin.readline n, m = map(int, input().split()) l = list(map(int, input().sp.. 2022. 9. 8.
괄호 - 9012번 올바른 괄호의 형태가 나왔을 때만 판별해야한다. 괄호중 ')'가 먼저 나오게 되면 항상 올바르지 않은 상황이니 'NO'가 나와야하며, 이 경우를 걸러내는 목적으로 코드를 짜면 빠르게 결과를 도출해낼 수 있다. '(' 가 나왔을 경우 체크용 변수에 1을 더해주고 ')' 가 나왔을 경우 -1을 더해준다. (체크용변수는 0부터 시작) 체크용 변수가 음수가 되면 break를 걸어 'NO'가 출력되게 하고 나머지 경우에 대해서는 'YES'를 출력한다. n = int(input()) for i in range(n): check = 0 #괄호 체크용 변수 result = 'YES' #최종 결과 확인용 변수 v = input() for j in v: if j =='(': check+=1 elif j == ')': ch.. 2022. 9. 4.
단어정렬 - 1181번 파이썬 배열의 매소드인 sort는 문자도 정렬해준다. 그냥사용한면 알파벳순으로 정렬해주고 sort(key = len) 처럼 사용하면 길이를 파악할 수 있는 자료형에 한에서 길이순으로 정렬을 해준다. 문제 조건에 맞게 sort()를 먼저한 후, sort(key = len)을 다음에 사용하여 정렬해준다. n = int(input()) l =[] for i in range(n): l.append(input()) l = set(l) l = list(l) l.sort() l.sort(key=len) for i in l: print(i) 2022. 9. 3.
직각삼각형 - 4153번 직각삼각형인지 아닌지 판별하는 방법은 매우 간단하다. 무한루프를 통해 0, 0, 0 입력 받을 때 break를 걸어주면 된다. while True: l = list(map(int, input().split())) if l[0]+l[1]+l[2] == 0: break else: l.sort() if l[2]**2 == l[0]**2 + l[1]**2: print('right') else: print('wrong') 2022. 8. 31.
직사각형에서 탈출 - 1085번 계산해 볼 수 있는 4개의 거리에 대해 계산한 후 min을 씌워 최소값을 출력한다. l = list(map(int, input().split())) ans = [l[0], l[1], l[2]-l[0], l[3]-l[1]] print(min(ans)) 2022. 8. 30.
수 정렬하기 1, 2 수 정렬하기 1 - 2750번 t=int(input()) arr=[] for i in range(t): arr.append(int(input())) arr.sort() for i in arr: print(i) 수 정렬하기 2 - 2451번 1번 문제와 같은 코드를 사용해도 답은 잘 나오지만 수가 커지면 시간초과에 걸린다. 넘파이의 sort기능을 사용하면 빠르게 정렬가능하지만 기본으로 제공되는 모듈이 아니기 때문에 파일을 찾을 수 없어 런타임 에러가 뜬다. import sys input = sys.stdin.readline n = int(input()) l=[] for i in range(n): num = int(input()) l.append(num) l.sort() for i in l: print(i).. 2022. 8. 29.
그룹 단어 체커 - 1316번 검사할 단어들을 배열에 저장한 다음에 한개씩 꺼낸다. 검사할 단어를 처음부터 한글자씩 스캔한다. 각 글자를 검사할 때 검사용 배열(check = [ ])을 만들어 검사할 단어의 첫글자를 넣어준다. 1. check[-1]과 스캔대상인 글자 대상을 비교하여 같으면 pass해준다. 2. 같지 않으면 check에 스캔중인 글자가 있는지 check.count(글자)로 검사해준다 2-1. 만약 없으면 check.append(글자)를 해준다 2-2. 만약 있으면 문제에서 찾고자하는 그룹단어가 아님으로 바로 break를 걸어주고 출력할 결과 N에서 1을 빼준다. n = int(input()) l = [] for i in range(n): l.append(input()) result = n for i in l: chec.. 2022. 8. 17.
기타줄 - 1049번 필요한 기타줄 N개를 살 때 브랜드에서 제공하는 판매방식인 "6개 세트, 낱개" 2가지 방식에 대하여 구매할 수 있는 방식은 총 3가지 이다. 1. 모두 낱개로 산다. 2. 구매하는 기타줄이 정확히 N개가 되도록 6개 세트와 낱개로 산다. 3. 구매하는 기타줄이 N개보다 커도 되게 모두 6개 세트만 산다. 이 3가지 방식을 사용할 때 필요한 기타줄의 가격은 모든 브랜드중에서 6개 세트가 가장 싼 곳과 낱개가 가장 싼 곳의 정보만 필요하다. 구매할 수 있는 방식 3가지와 가장 싼 곳의 정보를 가져와 비용을 계산하여 가장 작은 비용을 출력한다. import math n,m = map(int,input().split()) price_6 = 1000 price_1 = 1000 for i in range(m): .. 2022. 7. 30.
크면서 작은 수 - 2992번 도움받은 곳 : https://latte-is-horse.tistory.com/379 [solved.ac 실버3] 2992_크면서 작은 수 (파이썬, 순열) https://github.com/mangbaam/CodingTest GitHub - mangbaam/CodingTest: 프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다. 프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다. Con.. latte-is-horse.tistory.com (나중에 다시 풀어볼 것) from itertools import permutations n = input() all = list(set(map(lambda x: ''.join(x), (permutations(n,len(n)))))) all.s.. 2022. 7. 29.

티스토리툴바