본문 바로가기
728x90

전체 글423

[python] 백준 10989 수 정렬하기 3 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 기수 정렬 문제 시간초과를 신경써야 하는 문제 최대 수가 10000000이므로 리스트를 100000001개 만들고 입력 수를 인덱스로 해서 하나씩 +1 1부터 100000000까지 인덱스를 돌면서 value가 0이 아닌 값을 추출하면 된다. CODE import sys input = sys.stdin.readline N = int(input()) A = [0]*10001 for _ in range(N): .. 2023. 2. 22.
[python] 백준 11003 최솟값 찾기 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 문제 해결 i~i+l-1 까지 리스트 원소중 최솟값을 찾는 것이다. 다른 수들은 고려할 필요가 없으므로 (value,index)를 deque를 이용해 저장하자. 원소를 0~n까지 돌면서 deque[-1][0]과 비교하여 원소가 더 작으면 deque[-1][0]을 빼준다. 이를 반복한다. 필요 없기 때문에... 그리고 deque[-1][0]이 더 커지는 때가 오면 오.. 2023. 2. 19.
[python] 백준 12891 DNA 비밀번호 https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 문제 해결 긴 문자열에서 정해진 문자열 개수 p로 자른 다음 개수를 확인하는 문제이다. 왼쪽부터 한 칸씩 문자열을 p개씩 슬라이싱 했을 때 주어진 조건을 만족시키면 가능한 경우의 수이므로 정답 +1씩 올린다. 문자열은 한칸씩 이동하므로 한번 0~p-1까지 문자를 확인한다음 가장 왼쪽 인덱스의 문자를 제외시키고 오른쪽에 한칸 씩 문자를 추가시킴으로써 계산을 최소화 시킬 수 있.. 2023. 2. 19.
[python] 백준 1253 좋다 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 해결 리스트 안의 서로 다른 두 수의 합이 리스트 안의 다른 수가 되는 경우의 수를 구하는 문제이다. 리스트 안의 서로 다른 두 수의 합을 비교하는 것이므로 리스트를 올림차순으로 정렬하고 투포인터 이용하는 것이 좋아 보인다. 두 수의 합이 리스트 안에 있어도 3 + 0 = 3 등 다른 수가 되지 않으면 그 경우는 경우의 수로 계산하지 않는다. CODE import sys input = sys.stdin.readline .. 2023. 2. 18.
728x90