파이썬 알고리즘: K번째 큰 수 구하기.

알고 넘어가야 할 파이썬 이론:

1. range():

range(stop) :  range(10) 이라고 했을때, range 함수가 하나의 인자를 받는다면 0부터 9까지의 숫자를 생성한다.

range(start,stop) : range(1,11)은 1,2,3,4,5,6,7,8,9,10 의 숫자를 생성한다. 인자를 2개 전달하는 경우 첫번째 인자는 시작하는 숫자가 된다.

range(start, stop, step) :range(0, 20, 2)은 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 의 숫자를 생성한다. 마지막 인자 step은 숫자의 간격을 나타낸다.

range(20, 0, -2) 은 20, 18, 16, 14, 12, 10, 8, 6, 4, 2의 숫자를 생성한다. step으로 음수를 지정할 수 있다.

 

https://withcoding.com/79

 

2. set():

set() 의 특징은

1. 중복을 허용하지 않는다.

2. 순서가 없다. 따라서 정렬하는 sort 함수는 사용이 불가능하다.

3. 키가 존재하지 않고 값 데이터만을 담는다.

 

https://wikidocs.net/16044

https://programmer-ririhan.tistory.com/65

 

 

---

오늘 배운 내용

 

내가 문제풀이 : 

내가 생각하는 문제풀이: 입력예제를 보면 10 3 이니까 10이 자연수 n장의 카드고 3이 k번째 수를 의미할것이다. 그럼 코드는  n , k = map(int , input().split()) 으로 n과 k에 값을 넣어주고 a 로 배열을 하나 만들어 줘서 입력예제에 있는 13 15 34 23 45 65 11 26 42 값을 넣어주어야 할것이다. 코드는 a = list(map( int , input().split())) 큰 수에서 k번째의 수를 찾는것이니까..  solt(reverse=True) 가 들어가야할것 같고... 3장을 뽑을 수 있는 모든 경우의 수를 기록해야하니까... 경우의 수 구하는 공식이 필요하려나..? 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하는거니까.. sum 함수도 필요할 것 같은데... 어떻게 구현하는거지..?

# input= 10 3
#         13 15 34 23 45 65 33 11 26 42
# output=143

n, k = map(int,input().split())
a = list(map(int,input().split()))
res=set()

for x in range(n):
    for y in range(x+1, n):
        for z in range(y+1, n):
            res.add(a[x]+a[y]+a[z])
res = list(res)
res.sort(reverse=True)
print(res[k-1])

 

K번째 큰 수 코드분석

# input= 10 3
#         13 15 34 23 45 65 33 11 26 42
# output=143

n, k = map(int,input().split()) # 변수 n과 k에 각각 입력값을 넣어준다.
a = list(map(int,input().split())) # N개의 입력받은 자료를 리스트에 넣어준다.
res=set() #중복을 제거하는 자료구조인 set을 할당해준다. 
# 이렇게 되면 res에 여러 값을 넣어줘도 딱 한번만 들어가게 된다.

#3개의 자료를 뽑아서 합해준다.
for x in range(n):
    for y in range(x+1, n):
    			# x 뒤부터 돌아야 하기 때문에 x+1을 해준다.
        for z in range(y+1, n):
        		#y 뒤부터 돌아야 하기 때문에 y+1을 해준다.
            res.add(a[x]+a[y]+a[z])
            # set() 자료구조에 넣어주기 위해 add() 로 넣어준다. set 자료구조는 append 쓰지 않는다.

#set은 sort를 사용할 수 없기 때문에 리스트화를 시켜주어야 한다.
res = list(res)
# 리스트화 시킨 res는 sort로 정렬해줄 수 있다.
res.sort(reverse=True)
#인덱스 값으로 뽑아야 하니까 res[k-1]을 해준다.
print(res[k-1])

 

 

---

더 배울 내용

삼중for문은 시간복잡도가 높아 효율성이 좋지 못하다. 

다른 풀이 방법이 있나 좀 더 찾아볼 필요가 있다.

---

느낌점

일단은 코드 구현력을 높히기 위해서 이론을 듣고, 강의를 본 후 이론을 다시 정리하는 식으로 공부하고 있다.

주말에 나 혼자 힘으로 처음부터 끝까지 다시 풀어봐야지...!

일단은 기초 지식과 다양한 코드가 쌓여야지.. 그것들을 가지고 응용을 하던 활용을 하던 내것으로 만들던 할 것 같다.

당장 문제의 감조차 잡지 못한다고 너무 조급해하지 않고 그냥 천천히 확실하게 공부하기로 했다.

 

그리고 해설강의를 듣기 전 나 혼자 고민해보는 시간을 갖기로 했다. 안풀리면 나도 모르게 1시간~2시간까지 한 문제를 싸매고 끙끙대고 있으니, 지금은 딱 20분~30분 시간을 정해놓고 고민하는것이 좋을 것 같다. 고민하는 시간이 계속 길어지다보니 해야 할 다른공부를 하지 못하고 시간분배해놓은 계획이 자꾸 틀어지게 된다.

---