Python

[파이썬/Python] 정규표현식 - 리스트 내 원소들 중 숫자만 필터링하기

import re page = ['처음', '5개 앞', '이전', '6', '7', '8', '9', '10', '다음', '5개 뒤', '마지막'] p = re.compile("^[0-9]+$") page_only_digit = list(filter(p.match, page)) print(page_only_digit) # ['6', '7', '8', '9', '10'] 원래는 p.match 부분에 isdigit 내장 함수를 사용하려고 했는데, '5개 앞' 같이 원소 내 공백이 존재하면 내부적으로 구현되어 있는 ord 메서드를 적용할 수가 없어서 먹히질 않았습니다. 그래서 어쩔 수 없이 정규표현식으로 걸러줬습니다.

[파이썬/Python] Collections - Deque

들어가며 코딩테스트에 응시할 때 빠르게 찾아볼 수 있도록 따로 정리한 내용입니다. 공부하시기에는 빈약한 내용일 수 있음을 미리 알려드립니다. 공식 문서를 참고할 때에는 대부분의 기업이 이용하고 있는 프로그래머스 코딩테스트 환경에 적용된 python 3.8 버전의 collections을 참고했습니다. 코딩테스트용으로 작성한 글인 만큼 빠르게 훑을 수 있어야 하므로 경어체를 사용하지 않겠습니다. 초기화 방법 1. 기존의 iterable 객체 없이 빈 큐를 초기화 from collections import deque queue = deque() print(d) # deque([]) 2. 기존의 iterable 객체 없이 큐를 구현하되, 구현하면서 임시의 iterable 객체를 이용하여 초기화 from coll..

[백준 알고리즘][파이썬/Python] 11279번: 최대 힙

문제 시간 제한 : 1 초 (추가 시간 없음), 메모리 제한 : 256 MB 널리 잘 알려진 자료구조 중 최대 힙이라는 것이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 1. 배열에 자연수 x를 넣는다. 2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다. 출력 입력에서 0이 주어진 ..

[백준 알고리즘][파이썬/Python] 11866번: 요세푸스 문제 0

문제 시간 제한 : 2 초, 메모리 제한 : 512 MB 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 입출력 예 ..

[백준 알고리즘][파이썬/Python] 7568번: 덩치

문제 시간 제한 : 1 초, 메모리 제한 : 128 MB 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x,y), (p,q)라고 할 때 x>p 그리고 y>q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56,177), (45,165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55,173)이라면 몸무게는 D가 C보다 더 무겁고, 키는..

[백준 알고리즘][파이썬/Python] 11723번: 집합

문제 시간 제한 : 1.5 초, 메모리 제한 : 4 MB 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) all: S를 {1, 2, ..., 20} 으로 바꾼다. empty: S를 공집합으로 바꾼다. 입력 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이..

[파이썬/Python] 리스트(list)의 메소드 시간 복잡도(Big-O) 정리

파이썬으로 코딩테스트를 진행하며 가장 많이 쓰는 기본 자료형은 리스트(list)와 문자열(string), 딕셔너리(dictionary), 집합(set) 정도이다. 기본 자료형을 벗어난 것 중 많이 쓰는 것은 collections 모듈의 Counter와 deque 정도가 있겠고, 아주 가끔 itertools 모듈의 permutations 혹은 combinations 정도를 쓰는 것 같다(사실 이 둘은 시간복잡도가 터져버리기 때문에 거의 안 쓴다). 약간 난이도가 있는 코딩테스트 문제들은 항상 시간복잡도와 공간복잡도에 대한 제약이 주어진다. 특히 시간복잡도에 대한 제약은 아주 중요하며, 이를 고려하기 위해서는 이용하는 자료형의 메소드 별 시간 복잡도를 알고 있어야 한다. 그래서 이번 기회에 정리를 해볼까 한..

[백준 알고리즘][파이썬/Python] 1748번: 수 이어 쓰기 1

문제 시간 제한 : 1초, 메모리 제한 : 128 MB 1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다. 1234567891011121314151617181920212223... 이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. 출력 첫째 줄에 새로운 수의 자릿수를 출력한다. 입출력 예 제출 코드 n = int(input()) lst = [9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999] max = 0 len = 0 for idx, val in enumerate(lst): if n < val: max +=..