만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.
이렇게 정렬하는 방법을 빈도 정렬이라고 한다.
수열이 주어졌을 때, 빈도 정렬을 하는 프로그램을 작성하시오.
입력
첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000)
둘째 줄에 메시지 수열이 주어진다.
출력
첫째 줄에 입력으로 주어진 수열을 빈도 정렬한 다음 출력한다.
시간제한이 1초 이므로, Python으로 초당 2,000만번의 연산만 가능하다고 한다면, 최대 10억까지인 count 리스트를 만드는 방법은 적합치 않음.
# n개의 수열, c보다 작음
n,c=map(int,input().split())
# cnt 배열을 만들면 안됨. c 가 10억 이하이므로..
# dictionary로 접근해서 key를 숫자로 한다면?
# 숫자의 개수와 처음 인덱스를 value으로 저장한다면?
ans,i = {},0
for a in map(int, input().split()):
try:
ans[a][0]+=1
except:
ans[a] = [1,i]
i+=1
# print(sorted(ans.items(), key=lambda x: (-x[1][0], x[1][1])))
# x[0]는 dictionary 의 key 를 의미하며, x[1]은 value를 의미하므로
# 개수로는 내림차순, 순서로 오름차순 정렬
for li in sorted(ans.items(), key=lambda x: (-x[1][0], x[1][1])):
for _ in range(li[1][0]):
print(li[0], end=' ')숏코딩 분해해보기
print(*sorted(a:=[*open(0)][1].split(),key=lambda x:(-a.count(x),a.index(x))))얼핏 봐서는 접근 자체는 동일하게 정렬 함수인
sorted를 써서 개수로 내림차순, 나온 순서로 오름차순 정렬을 한 것으로 보인다.
신기한 점은 군더더기 없이 입력과 출력을 단 한줄로 처리해 버렸다는 것...
먼저 바다코끼리 연산자(:=)를 써서
a라는 변수를 할당과 반환을 동시에 하였다.
변수 := 표현식
작동하는 방식은 표현식의 결과를 변수에 할당하고, 동시에 반환합니다. 즉, 변수 = 표현식을 하고, return 변수 기능을 합니다.
open(0)를 통해0을 인수로 받아서 파일 이름 대신에 standard input을 읽고 파일로 열 수 있다.
다음과 같은 입력일 때의 코드 수행 결과를 예시로 살펴보도록 하자
9 77
11 33 11 77 54 11 25 25 33
print(open(0))
#아래와 같은 file object를 반환한다
<_io.TextIOWrapper name=0 mode='r' encoding='UTF-8'>
[*open(0)]syntax는 list comprehension으로 인풋 파일의 모든 라인을 읽어 문자열의 리스트 형태로 저장하는 것이다.print([*open(0)]) # 아래와 같이 string이 줄바꿈(\n)으로 구분되어 리스트 형태로 저장된다. ['9 77\n', '11 33 11 77 54 11 25 25 33'] # 첫번째 원소는 사실 상 필요 없으므로(?) # 두번째 원소에 접근하기 위해 [*open(0)][1] # 다음으로 공백을 처리하기 위해 아래와 같이 코드를 수행하면 print([*open(0)][1].split()) #아래의 결과와 같이 리스트 형태로 나온다. ['11', '33', '11', '77', '54', '11', '25', '25', '33']
이후
count(x)내장 함수를 통해 각 원소의 개수를 기준으로 내림차순 정렬,
index(x)내장 함수를 통해 문자 및 문자열의 위치를 찾아주고, 같은 문자 및 문자열이 있을경우 처음 검색된 위치를 반환한다.
그러므로 각 원소의 위치를 기준으로 오름차순 정렬이 된다
find(x)함수는 문자열만을 argument로 받기 때문에 Attribute에러가 나니 참고하자
