본문 바로가기

BOJ/Python

 (192)
[BOJ/백준] 6549 - 히스토그램에서 가장 큰 직사각형 (Python) 문제문제링크너비가 1인 직사각형으로 이루어진 히스토그램이 있다.각 줄에서 첫 번 째 값은 직사각형의 수이고, 그 후 값들은 히스토그램의 높이다.히스토그램에서 가장 널이가 큰 직사각형을 구하라. 풀이stack에는 높이와 시작 인덱스를 저장한다.스택에 값이 있고 마지막 값의 높이가 현재 높이보다 크다면, 높이와 시작 인덱스를 꺼내 현재 위치 i에서의 크기를 구한다.최대 크기와 이 크기 중 큰 값을 max_s에 재저장한다.스택에는 현재 높이와시작 인덱스를 저장한다.스택에 남은 직사각형을 처리하기 위해 for문을 다시 써주고, max_s를 리턴한다.이 과정을 입력이 0이기 전까지 반복한다.  코드import sysinput=sys.stdin.readlinedef maxsize(): #최대 크기의 직사각형 구..
[BOJ/백준] 17413 - 단어 뒤집기 2 (Python) 문제문제링크안의 문자는 그대로, 나머지는 단어만 뒤집어서 출력하라. 풀이문자열을 내부 문자열은 유지하면서 split한다.이 포함된 부분은 stack에 그대로 저장하고, 이외에는 공백 기준으로 단어 리스트를 생성한다.각 단어를 뒤집고 뒤집힌 단어들을 공백과 다시 합쳐 stack에 추가한다.stack 내 모든 요소를 문자열로 합쳐 리턴한다. 코드import sysinput=sys.stdin.readlineimport redef reverse_w(s): tokens=re.split(r'(]*>)',s) stack=[] for i in tokens: if i.startswith(''): stack.append(i) else: wo..
[BOJ/백준] 28702 - FizzBuzz (Python) 문제문제링크i가 3의 배수이자 5의 배수이면 'FizzBuzz'를, i가 3의 배수이고 5의 배수가 아니면 'Fizz'를,i가 3의 배수가 아니고 5의 배수면 'Buzz'를, i가 3배수도 아니고 5배수도 아니면 i 그대로 출력한다.연속으로 세 개의 문자열이 주어질 때, 바로 다음 문자열은 무엇인가? 풀이 FizzBuzz를 출력하는 경우는 15의 배수인 경우이다.3배수, 5배수, 15배수가 연속해서 나오는 경우는 없다. 따라서 세 줄 중 적어도 하나는 정수가 출력된다.셋 중 정수인 것을 기준으로 x값(세 수의 바로 다음 값)을 결정한다.x값을 위 규칙에 맞춰 리턴값을 결정해 출력한다. 코드def FizzBuzz(i): if i%15==0: return 'FizzBuzz' elif ..
[BOJ/백준] 32710 - 구구단표 (Python) 문제문제링크A*B=C의 형태로 이루어진 구구단표가 있다. 구구단이 2단부터 9단까지 있다고 할 때, n이 이 표에 등장하는가? 풀이A는 2부터 9까지, B는 1부터 9까지, C는 이들의 모든 조합의 곱이 가능하다.따라서 정수 n이 1부터 9까지의 정수로 나누어떨어지고 n을 그 수로 나눈 몫이 9 이하일 때 등장한 것이다.기본값을 False로 설정하고 위 경우에 해당할 때만 True로 바꾸고 for문을 break로 벗어난다.TF가 참일 때만 1을 출력하고, 이외에는 0이 출력한다. 코드n=int(input())for i in range(1, 10): TF=False if n%i==0 and n//i
[BOJ/백준] 32776 - 가희와 4시간의 벽 2 (Python) 문제문제링크철도편 소요시간과 항공편 소요시간(역a에서 공항a -> 공항a에서 공항b -> 공항b에서 역b)이 주어진다.이용객 p는 철도를 좋아하고, 고속철도로 구간을 주파하는데 소요 시간이 4시간 이하이다.   # 4시간의 벽: 고속철도가 4시간 이하로 주파하는 구간에서는 고속철도가 우위에 선다.두 역 사이를 이동할 때 어느 교통수단을 더 많이 이용하는가.  풀이승객들 중 철도를 좋아하는 사람이 많다는 것은 두 이동수단의 시간이 같을 때 철도를 선택하라는 뜻이다.두 수단의 이동소요시간 비교와 4시간의 벽을 활용하는 문제이다.고속철도가 항공편보다 빠르거나(짧은 시간) 고속철도의 이동시간이 4시간 이하면 고속철도를 선택하고, 나머지 경우는 항공편을 이용한다.시간은 분 기준으로 입력되므로 단위를 잘 확인해야 ..
[BOJ/백준] 1439 - 뒤집기 (Python) 문제문제링크1과 0으로만 이루어진 문자열이 있다.이를 모두 같은 숫자로만 만들기 위해 전체 혹은 부분을 0은 1로, 1은 0으로 뒤집는다.이 행동의 최소 횟수를 출력하라. 풀이각각의 숫자로 이루어진 부분을 구하고 둘 중 개수가 적은 만큼이 최소횟수가 된다.정규표현식 모듈인 re을 사용한다.findall로 각각 패턴에 매칭되는(1로만 이루어진, 0으로만 이루어진) 부분을 찾아 리스트에 저장한다.두 리스트의 개수 중 작은 것을 구하면 된다. 코드import sysinput=sys.stdin.readlineimport res=input().strip()zeros=re.findall(r'0+',s)ones=re.findall(r'1+',s)print(min(len(zeros), len(ones)))
[BOJ/백준] 1715 - 카드 정렬하기 (Python) 문제문제링크매우 많은 숫자 카드 묶음이 있을 때, 이들 중 두 묶음씩 골라 서로 합쳐나간다.이때 최소 몇 번의 비교가 필요한가? 풀이우선순위 큐를 사용하는 문제이다.heapq는 파이썬의 힙 자료구조로 기본적으로 최소 힙을 구현한다.haepify로 카드묶음을 최소 힙으로 변환한다.heappop으로 카드 묶음 중 가장 작은 두 원소를 꺼내 합친다. 이 과정을 두 번씩 한다.이 둘을 합쳐 비교 횟수에 더하고 4개의 원소가 빠진(2번의 과정이었으므로) card에 합을 추가한다.마지막 비교까지(card 원소가 1개일 때) 위 과정을 반복한다. 코드import sysinput=sys.stdin.readlineimport heapqn=int(input())card=[int(input()) for _ in range(..
[BOJ/백준] 1931 - 회의실 배정 (Python) 문제문제링크회의들의 시작시간과 끝나는 시간이 주어진다. 회의가 겹치지 않게 회의실을 사용할 수 있는 회의의 최대 개수를 구하라. 풀이그리디 알고리즘을 사용하기 위해 회의들을 정렬해야 한다.이 때 정렬기준은 끝나는 시간이다. 끝나는 시간이 같을 경우 회의 시간이 짧아야 하므로 두번째 기준은 시작시간이 된다.정렬된 회의들의 시작시간과 이전 회의의 끝나는 시간을 비교해 회의실이 사용 가능한 경우에만 1을 더한다. 코드import sysinput=sys.stdin.readlinen=int(input())meet=[tuple(map(int, input().split())) for _ in range(n)]meet.sort(key=lambda x: (x[1],x[0]))time=0count=0for start, e..

티스토리툴바