💰 고득점 Kit : 정렬

---

🌞 K번째수

🚊 문제 설명

• 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
2에서 나온 배열의 3번째 숫자는 5입니다.

📢 배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

🚊 제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

🚊 입출력 예

입출력 예 #1, 2

• [1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
• [1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
• [1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

📑 Code : 내꺼

📌 Logic 설명

1. 반복문을 돌면서 commands의 각 요소 command를 꺼내옴
2. command 내의 각 요소는 기존 array를 슬라이싱할 start, end, 그리고 슬라이싱된 리스트를 정렬 후 우리가 찾을 요소의 순서를 의미
3. 단, start, end, index는 순번이 아닌 Index No.을 의미하므로 그에 맞게 조정해줘야 함.
4. list comprehension을 이용하여 간단하게 작성
5. 위의 로직을 순서대로 구현

> code
def solution(array, commands):
    return  [sorted(array[start-1:end])[index-1] for start,end,index in commands]

📑 Code : 다른 사람꺼

-

• 없음

> code

💡 새롭게 알게된 점

📌 -

> code

---

🌞 가장 큰 수

🚊 문제 설명

• 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
• 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

📢 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

🚊 제한사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

🚊 입출력 예

📑 Code : 내꺼

📌 Logic 설명

1. 주어진 숫자들을 앞자리 수가 큰 것부터 앞에 배열해야 그것들을 이어 붙였을 때 가장 큰 수가 나옴.
2. 그것을 위해 주어진 리스트의 각 숫자들의 타입을 int 가 아닌 str 으로 변환
3. 그 다음에 리스트를 역순으로 정렬을 하게 되면, 앞자리 숫자가 큰 것부터 정렬하게 됨.
4. 그러나 위의 방식대로 하게 되면 3, 30, 34가 주어졌을 때 34, 30, 3 순서로 정렬하게 되고 이는 34, 3, 30 을 이어 붙인 숫자보다 작게됨. (34303 < 34330)
5. 이를 방지하기 위해 각 숫자를 3번 이어 붙여서 최소 3자리 이상의 숫자를 만들고, 그 값들의 크기를 비교하여 역순으로 정렬하면 됨.

   • 왜냐하면, 제한 사항에 numbers의 원소는 1000 이하의 숫자라는 내용이 있기 때문
   • ['3', '30', '34']의 경우, 각 요소를 3번씩 이어 붙이면 '333', '303030', '343434' 이 되고, 이를 문자열의 크기라는 기준으로 역순 정렬하면 '343434' > '333' > '303030' 순이 되기 때문에 리스트 정렬 결과가 ['34', '3', 30']이 됨.

• 즉, 1 > 2 > 5 순서대로 동작하게 코드를 작성하면 됨.

> code
def solution(numbers):
	# 주어진 리스트의 각 요소를 문자열로 변환
    numbers = list(map(str, numbers))
    # lambda 함수를 이용하여 주어진 리스트를 각 요소를 3번씩 이어붙인 결과의 역순으로 정렬하게 됨.
    numbers.sort(key=lambda x: x * 3, reverse=True)
    # 리스트 내의 문자열을 이어붙인 뒤 정수로 변환 후 다시 문자열로 변환
    return str(int(''.join(numbers)))

📑 Code : 다른 사람꺼

💡 두 수의 크기를 비교하여 1/0/-1을 반환하는 comparator 함수 생성

💡 functools 모듈의 cmp_to_key 함수를 이용하여 내가 만든 함수로 커스텀 정렬

• return 값은 항상 1/0/-1 이어야 함.

  • 1 : 정렬 기준대로 앞으로 가기 위해 True를 의미
  • -1 : 정렬 기준과 반대로 가서 뒤로 가기 위해 False를 의미
  • 0 : 0은 아예 정렬 기준에 해당되지 않아 그대로 있을 때를

💡 참고 :

[Python] 커스텀한 기준으로 sort()하기 : cmp_to_key()

> code
import functools

# 커스텀 정렬 함수 comparator 생성
def comparator(a,b):
	print(f"a:{a}")
    print(f"b:{b}")
	# t1 : 두 문자열의 수를 순서대로 이어 붙인 결과
    t1 = a+b
    # t2 : 두 문자열의 수를 반대로 이어 붙인 결과
    t2 = b+a
    
    print(f"int(t1) > int(t2) : {int(t1) > int(t2)}")
    print(f"int(t1) < int(t2) : {int(t1) < int(t2)}")
    print(f"비교 결과 : {result}")
    print("==============================================")
    
    # t1의 숫자값이 더 크다면 1 : 더 큰 값이 뒤로 이동
    # t2의 숫자값이 더 크다면 -1  : 더 큰놈이 앞으로 이동
    # 두 값이 동일하다면 0 : 순서는 기존과 동일
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) 

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

🔎 예시를 통한 확인

• 위의 코드에는 print 문이 모두 달려있는데, 예시 코드를 돌려보면 아래와 같은 결과가 나옴.
  예시를 통한 출력 내용 확인

numbers = [3, 30, 34, 5, 9]
solution(numbers)


--- 출력 결과 ---

a:5
b:9
int(t1) > int(t2) : False
int(t1) < int(t2) : True
비교 결과 : -1
==============================================
a:34
b:5
int(t1) > int(t2) : False
int(t1) < int(t2) : True
비교 결과 : -1
==============================================
a:30
b:34
int(t1) > int(t2) : False
int(t1) < int(t2) : True
비교 결과 : -1
==============================================
a:3
b:30
int(t1) > int(t2) : True
int(t1) < int(t2) : False
비교 결과 : 1
==============================================
a:3
b:5
int(t1) > int(t2) : False
int(t1) < int(t2) : True
비교 결과 : -1
==============================================
a:3
b:34
int(t1) > int(t2) : False
int(t1) < int(t2) : True
비교 결과 : -1
==============================================
a:3
b:30
int(t1) > int(t2) : True
int(t1) < int(t2) : False
비교 결과 : 1
==============================================


--- return 값 ---
'9534330'

---

🌞 H-Index

🚊 문제 설명

• H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다.
• 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.
• 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

📢 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

🚊 제한사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

🚊 입출력 예

입출력 예

• 이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다.
• 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

📑 Code : 내꺼

Code 1

📌 Logic 설명

코드에 직접 적음

> code 1
def solution(citations):
    # 인용이 적게 된 논문들부터 서칭하기 위해 정렬
    citations.sort()
    # idx : 나보다 인용된 수가 적은 논문의 수
    # citation : 논문의 인용된 횟수
    for idx , citation in enumerate(citations):
        # 인용된 횟수가 남은 논문의 수(나를 포함한)보다 크거나 같으면
        if citation >= len(citations) - idx :
            # 인용된 논문의 숫자를 return
            return len(citations) - idx
    # 논문이 1편밖에 없는 경우
    return 0

Code 2

📌 Logic 설명

여기 사이트 내용 참고

> code 2
def solution(citations):
    # 인용이 많이 된 논문들부터 서칭하기 위해 역순으로 정렬
    citations.sort(reverse=True)
    print(f"citations : {citations}")
    print("=======~~=======")
    for idx, citation in enumerate(citations):
        print(f"idx : {idx}")
        print(f"citation : {citation}")
        print("========")
        # H-Index를 idx라고 가정
        # citation : 나머지 논문들이 인용된 횟수 중 최댓값
        # 나머지 논문들이 인용된 횟수 중 최댓값이 idx번 이하인 최초의 경우를 찾음.
        if idx >= citation:
            # idx를 반환
            return idx
    print(f"citations : {citations}")
    print("--------")
    # citations를 모두 서칭하였는데 H-Index 조건을 만족하는 값이 없다면
	# citations의 길이보다 작은 값으로 리스트를 2갈래로 구분지을 수 없다는 것이기 때문에
	# citations의 길이가 우리가 찾는 H-Index
    return len(citations)

🔎 예시를 통한 확인

• 위의 코드에는 print 문이 모두 달려있는데, 예시 코드를 돌려보면 아래와 같은 결과가 나옴.
  예시를 통한 출력 내용 확인

citations = [6, 5, 5, 5, 3, 2, 1, 0]
solution(citations)


--- 출력 결과 ---

citations : [6, 5, 5, 5, 3, 2, 1, 0]
=======~~=======
idx : 0
citation : 6
========
idx : 1
citation : 5
========
idx : 2
citation : 5
========
idx : 3
citation : 5
========
idx : 4
citation : 3
========


--- return 값 ---
'9534330'

📑 Code : 다른 사람꺼

Code 1

• 문제 조건을 제일 직관적으로 표현한 코드
• 그러나, 주어진 citations 배열을 모두 순회해야 하므로 좋은 코드는 아님.

> code
    def solution(citations):
        # 최대값을 구하기 위해 max_라는 변수를 사용
        # 조건을 만족하는 값이 생길때마다 최대값으로 갱신하여 
        max_ = 0
        # 인용된 논문 수가 많은 것부터 탐색하기 위해 역순으로 정렬
        citations.sort(reverse=True)
        # index를 1부터 시작하는 이유는, 나를 포함한 값을 계산하기 위함
        for index, citation in enumerate(citations, start=1):
            # index : 지금 citation보다 인용된 횟수가 크거나 같은 논문의 수
            print(f"index : {index}")
            # citation : 논문의 인용된 횟수
            print(f"citation : {citation}")
            # (현재 논문의 인용 회수)가 (현재 논문의 인용된 횟수 이상으로 인용된 논문의 수)보다 더 크거나 같다면
            if citation >= index:
                # H_index가 될 수 있는 후보로 갱신
                # index는 1부터 점차 커지고, 최종적으로 만족하는 값이 max_에 저장되므로
                # 반복문 종료 후 결국 max_ 값은 H-Index를 만족하는 값이 됨.
                max_ = index
                print(f"answer : {answer}")
        return answer

Code 2

• 현재 논문보다 인용이 많이 된 논문의 횟수를 바로 체크하기 위해 주어진 배열을 역순으로 정렬
• enumerate의 시작을 1로 맞춤으로써, 배열의 idx 요소 값 각각이 바로 나보다 인용이 많이된 논문의 횟수를 뜻하게 됨.

> code
    def solution(citations):
        citations.sort(reverse=True)
        answer = max(map(min, enumerate(citations, start=1)))
        return answer

• 예시

  • citation = [1,6,2,4,0] 인 경우, 역순으로 정렬하면 [6,5,4,1,0]이 되고,
  • enumerate(citations, start=1) 함수 로 인해 (1,6), (2,5), (3,4), (4,1), (5,0) 와 같은 객체가 생성됨.
  • map(min, enumerate(citations, start=1))의 결과, (1,2,3,1,0)이라는 객체가 생성됨.
  • 결과적으로 3이 return됨.

• 해석

  • 위의 코드는 각각의 (idx, citation) 객체에 대해 x = 1부터 시작하여 y = index, y = citation 라고 하는 일차 함수를 그린 후, 각각의 x값에 대해 y값의 min 값들만 체크한 다음에 그 중에서 max 값을 찾은 결과임.
  • https://ssuamje.tistory.com/47
    → 이 블로그에 관련된 내용이 더 자세히 적혀 있으니 참고할 것.

💡

📌

---