6/29 코테 일지 (Quick Select, 배열 한 줄 출력, 딕셔너리 자료형)

Quick Select (배열이 주어졌을 때, k번째로 큰 값을 select 하는 알고리즘)

Neetcode 150 (https://neetcode.io/problems/kth-largest-element-in-an-array)

 

먼저 sorting을 하는 방식이다. 단순히 k번째로 큰 element를 select하는게 아니라 배열 전체를 sorting 하는 것이니 비효율적이다. sorting 방식에 따라 다르겠지만, 평균적으로 O(nlogn)이 될 것이다. 

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums)[-k]

 

다음은 내가 생각해낸 알고리즘이다. len(nums)-k 번재 원소 를 element마다 비교해가며 swap 해준다. 해당 방식을 최대 len(nums)만큼 반복해주면 되는데, 만약 모든 왼쪽 원소가 . len(nums)-k 번째 원소보다 작고 오른쪽 원소가 pivot 원소보다 크면 boolean을 사용해 for loop을 일찍 탈출하지만, sorting보다 큰 메리트가 없을 것 같은 알고리즘이다. (최악의 경우 O(n^2))이다. 

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        current_max= 0
        temp=0
        for _ in range(len(nums)):
            boolean = 0
            for j,element in enumerate(nums):
                if j< len(nums)- k and element > nums[-k] :
                    temp = nums[-k]
                    nums[-k] = nums[j]
                    nums[j] = temp
                    boolean = 1 
                if j> len(nums)- k and element < nums[-k] :
                    temp = nums[-k] 
                    nums[-k] = nums[j]
                    nums[j] = temp  
                    boolean = 1
            if boolean ==0:
                break
        return (nums[-k])

 

Quick Select 알고리즘 정석

Quick Sort와 비슷하지만, 재귀 함수 call에서 left와 len(arr) -k를 비교해 한 쪽만 call 한다. 

시간 복잡도가 n + 2/n + n/4 ... = 2n이므로 O(n)이 된다.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quickSelect(arr,s,e):
            pivot = arr[e]
            left = s
            for i in range(s,e):
                if arr[i] < pivot :
                    arr[i], arr[left] = arr[left], arr[i]
                    left = left+1
            arr[e],arr[left] =arr[left], arr[e]
            if left < len(arr) - k: return quickSelect(arr,left+1,e)
            elif left > len(arr) - k: return quickSelect(arr,s,left-1)
            else : return arr[-k]
        return quickSelect(nums,0,len(nums)-1)

 

배열을 한 줄 출력 

#1015 

for i,x in enumerate(new_array):
    print(x, end = " ")
    
print(*new_array)

print(' '.join(map(str, new_array)))

골라쓰도록 하자. 

 

dictionary 자료형 (key, value, max, 등)

#2108

최빈값 중 두 번째로 작은 값을 구하는 코드이다. 불필요한 for loop이 많아 보이며, 단순히 최빈값을 구하는게 아니라 같은 빈도의 수 중 두번째로 작은 수를 구하기 위해 직관적이지 못한 boolean을 사용했다. 

#최빈값 중 두번째로 작은 값 구하기 

dictionary={}
for element in array:
  dictionary[element] = 0

for j,element in enumerate(array):
  dictionary[element] += 1  

max_count = 0
for key,val in dictionary.items():
  if val > max_count :
    max_count = val
    
boolean =0
max_element=0 
for key,val in dictionary.items():
  if val == max_count :
    max_element = key 
    boolean += 1
  if boolean == 2 :
    break

 

먼저 dictionary 초기화 부분을 개선해보자. 불필요하게 for loop 두 번을 돌리고 있지만 다음과 같이 개선이 가능하다. 

dictionary = {}
for element in array:
    if element in dictionary:
        dictionary[element] += 1
    else:
        dictionary[element] = 1

if element in dictionary 조건문은 element가 dictionary의 key 값중 존재하는 지를 확인한다. 즉, 존재하지 않으면 1로 초기화 하고, 이미 존재하면 그 값에 1을 더해준다. 

만약 value값의 존재 여부를 확인하고 싶으면 if element in dictionary.values() 를 사용하면 된다.

 

또한 최빈값 중 두 번째로 작은 값을 찾기 위해선 다음과 같이 코드를 짤 수 있다. 

max_value = max(dictionary.values())
mode = sorted([k for k,v in dictioanry.items() if v == max_value])

if len(mode) > 1: print(mode[1])
else: print(mode[0])

먼저 for loop을 돌려가며 max_count를 찾는것이 아닌 max(dictionary.values()) 를 사용했다. 또한, boolean을 사용하지 않고 mode 라는 array에 모든 max_count를 value로 가지는 키 값들의 리스트를 만들고 리스트의 두번째 또는 첫 번재 원소를 출력해준다. 

하지만 확실히 boolean을 사용하니 더욱 시간이 짧게 나온다. (boolean = 2일때 for loop을 break하기 때문)

 

 

그 외 문제들 

#11899

완벽하게 품.

import sys
array = list(sys.stdin.readline().rstrip())

stack = []
for element in array:
  if stack and stack[-1] == '(' and element == ')':
    stack.pop()
  else :
    stack.append(element)

print(len(stack))

 

#1094 

필요 없는 부분이 많았지만 깔끔하게 정리.

import sys
n = int(sys.stdin.readline().rstrip())

array= [64,32,16,8,4,2,1]
count = 0
for element in array:
  if n-element>=0 and n!=0:
    n -=element 
    count += 1 

print(count)