구름톤 챌린지 Week 1 - Day 5
숫자들이 주어질 때, 2가지 조건을 만족하는 형태로 정렬한 뒤, K번째 숫자를 출력하는 문제이다.
조건 1. 숫자를 2진수로 바꾸었을 때, 1이 많은 순서대로(내림차순) 정렬할 것
조건 2. 조건 1에서 1의 개수가 같다면, 10진수를 기준으로 큰 값으로(내림차순) 정렬할 것
물론, 조건 1을 만족한 뒤에 조건 2를 만족하는 형태로 들어가야 한다.
_, K = map(int, input().split())
lst = list(map(int, input().split()))
for i, v in enumerate(sorted(lst, reverse=True)):
lst[i] = bin(v)[2:]
lst = sorted(lst, key=lambda x: -x.count("1"))
print(int(lst[K-1], 2))놀랍게도, 복잡해보이는 이 문제도 위의 6줄이면 풀 수 있다.
코드의 핵심이라고 말할 수 있는 하단 4줄은 아래에서 자세히 알아본다.
우선 몇 개의 숫자를 받을지 N을 입력받아야 하는데, 본 코드에서는 사용하지 않아 무시(_)했다.
그리고 K와 lst를 각각 입력받는다.
for i, v in enumerate(sorted(lst, reverse=True)):
lst[i] = bin(v)[2:]파이썬에서 제공하는 정렬 함수, sort()와 sorted()는 stable sort가 기본이다.
Stable sort란, 정렬하려는 두 값이 같을 때 기존의 순서를 유지하는 함수이다.
예를 들어서, list_ = [1, 5, 3, 3, 2]라는 list를 sort()로 정렬하여, [1, 2, 3, 3, 5]가 되었다고 해보자.
이때 두 개의 3 객체는 자리 이동없이 기존의 순서를 유지한다는 이야기이다.
이런 특징을 감안하여 아이디어를 생각해보자.
2진수 기준으로 1 개수가 똑같다면, 10진수일 때 큰 수가 먼저 나오게 정렬해야 한다?
이것은 10진수로 먼저 내림차순 정렬을 한 뒤, 2진수를 기준으로 정렬한다는 말과 똑같다.
왜? 2진수를 기준으로 1 개수가 똑같다면, 10진수 내림차순의 상태를 유지할 테니까.
그리고 2진수를 위한 list를 새로 생성할 필요도 없다. 메모리 낭비다.
이 문제에서는 K번째 10진수가 궁금한 거지, 다른 숫자들은 어떻게 되든 상관없다.
우선 sorted()로 정렬해주되, 내림차순(reverse=True)이 되게끔 한다.
그리고 enumerate()로 index(i)와 value(v)를 같이 반복해준다.
v를 bin() 내장 함수로 2진수로 바꿔주면, 0b... 형태의 형식자가 붙는다. 따라서 2번째부터 슬라이싱을 해준다.
그리고 정렬한 i 위치에 2진수로 바꾼 '문자열'을 저장해준다.
예를 들어서 list_ = [1, 3, 7, 4, 6]이 들어왔다면, 결과적으로 ["111", "110", "100", "11", "1"]이 된다.
lst = sorted(lst, key=lambda x: -x.count("1"))10진수 내림차순으로 정렬하고, 2진수로도 바꿨다.
이제 남은 것은 2진수일 때, 1의 개수를 기준으로 정렬하는 것만이 남았다.
이것은 lambda를 활용하면 간단하게 할 수 있다.
마찬가지로 정렬한 값을 return하기 위해 sorted()를 사용했다. 이때는 sort()를 써도 상관없다.
key를 lambda로 지정해준다. lambda 식은 x를 하나하나 받아와 1의 개수를 세주는(count) 것이다.
이때 x는 lst에 들어있는 요소들 하나하나이고, x.count("1") 앞에 붙은 마이너스는 내림차순을 의미한다.
예시는 다음과 같다. (이전) ["111", "110", "100", "11", "1"] (이후) ["111", "110", "11", "100", "1"]
print(int(lst[K-1], 2))마지막으로 출력하는 부분만이 남았다.
K번째 숫자를 출력해야 하지만, 실제 index상으로는1을 빼줘야 한다. 왜? index는 0부터 시작하니까.
또한, 지금 저장된 K번째 숫자는 2진수이다. 정답에게 필요한 것은 10진수이다.
이때는 int() 내장 함수의 다른 매개변수를 사용하면 쉽게 변환할 수 있다.
int(num, digit) 형태로 int() 내장 함수를 사용할 수 있다.
이때 num은 10진수로 바꿀 문자, digit은 어떤 진법 숫자로 취급할 것인지이다.
예를 들어서 int(31, 9)라고 작성한다면, 31을 9진법 숫자로 취급하여 10진수로 바꾼다는 이야기이다.
그럼 (9^0 * 1) + (9^1 * 3)을 하여 28로 만들어준다.
주의할 점은 num에 들어갈 자료형이 '문자'여야 한다는 점이다.
지금 lst에 저장한 값들은 전부 2진수 문자열이다. (bin() 내장함수를 쓰면 문자열로 반환한다.)
그리고 원하는 index는 K-1이다. 그렇다면 정답이 원하는 코드는 int(lst[K-1], 2)가 된다.
어렵게 새로 list를 선언하고, 순서쌍을 저장하고, 2차원 배열 형태에서 값을 찾을 필요가 전혀 없다는 거다.