환영합니다. 이 블로그 번째 방문자입니다.
[Q3:English] Kth largest element
Given an array of integers arr and an integer k find the kth largest element. (1 ≤ k ≤ length of arr) For example, arr = [4,2,9,7,5,6,7,1,3], k = 4, output : 6. [ Method 1] # Logic Remove max element in the arr for k-1 times and return max element. # Code # Complexity T(n,k) : (k-1) * 2n + n = O(kn) S(n) : O(1) [Method 2] # Logic Use sorting # Code # Complexity T(n,k) : O(nlogn) + O(1) = O(nlogn..
[Q2:English] First and last index in sorted array
👇🏻 문제(이 정도는 해석X...귀찮,, 영어강의라 포스트도 영어로) Given a sorted array of integers arr and an integer target, find the index of the first and last position of target in arr. In targer can't be found in arr, return [-1,-1]. For example, arr = [2,4,5,5,5,5,5,7,9,9], target = 5 👉🏻 output : [2, 6] [Method 1] # Logic # Code # Complexity S(n) = O(1) T(n) = O(n) [Method 2] How about using binary search? Because i..
[re-Python] 문자열, 배열 정렬 (sort, sorted)
코딩테스트에서 간간히 나오는 유형이라 모르고 지나칠 수가 없는... 근데 헤깔리는... 1차원 배열을 정렬하는 것은 매우 쉽다. [1차원 배열] Ascending Sort, 오름차순(1,2,3,...) 정렬 arr = [5,2,3,1,4] # 1번 방법 sorted(arr) # 출력 : [1,2,3,4,5] # 2번 방법 arr.sort() # 출력 : [1,2,3,4,5] sorted(배열명) 이나 배열명.sort()를 사용하면 된다. 숫자, 문자, 문자열 전부 상관없이 오름차순 정렬이 된다. 다만, 대소문자가 섞여있는 배열에는 대문자 오름차순 > 소문자 오름차순 으로 정렬된다. (문자를 아스키코드 값에 대응하기 때문) 이 두 내장 메소드의 차이점은 분명해서 언제 사용할지 분명히 나누어진다. sorte..
[2] 백준 13458번: 시험감독
{ 문제 } https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net { 40분 무코딩 로직 사고} 나눗셈 문제 결과 : 2분 문제 이해 + 4분 문제 로직 생각 { 코드 구현 } import math N = int(input()) A = list(map(int, input().split())) B, C = map(int, input().split()) judges = [0 for i in ran..