• Home
  • About
    • JOOS photo

      JOOS

      Joos's blog

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

[백준] 11004번 : k번째 수 with python3

31 Oct 2018

Reading time ~1 minute

문제: https://www.acmicpc.net/problem/11004

import sys
read = lambda : sys.stdin.readline().strip()
write = lambda x: sys.stdout.write(str(x)+ "\n")

def nth(arr, n):
    pivot = arr[0]
    below = [x for x in arr if x < pivot]
    above = [x for x in arr if x > pivot]

    num_less = len(below)
    num_less_or_equal = len(arr) - len(above)

    if n < num_less:
        return nth(below, n)
    elif n >= num_less_or_equal:
        return nth(above, n - num_less_or_equal)
    else:
        return pivot


n, k = map(int, read().split())
a = list(read().split())
for i in range(len(a)):
    a[i] = int(a[i])
write(nth(a, k-1))

원래 python 내장 sort썼다가 계속 시간초과 메모리초과 난리가 나서 직접 sort해서 k 번째 수 내보내는 것 만드니 통과되었다… 악질이다



algorithm백준python Share Tweet +1