정렬

 

사실 파이썬 정렬은 arr.sort(reverse=True)이것만 알아도 너무너무 쉽다. 

하지만.. N이 굉장히 큰 경우가 시간초과 문제가 발생한다. 

 

FOR문의 최소화를 목표로 두고 진행해야겠다. 

 

2751 

for i in a:
...     print(i)

핵심 코드이다. a라는 배열에서, 1개 1개씩 index를 출력할 수 있고, 

시간 복잡도가 해당 a배열을 생성해서 출력하는 것보다 훨씬 빠르다 .

 

sort는 원 배열까지, sorted(배열)은 원배열 값에 영향을 미치지 않는다. 

다만 sort는 return값이 None . sorted()는 return 값이 완성된 애를 리턴해준다.

정렬만하면될땐 sort, 값을 받아낼땐 sorted를 쓰자. 

 

code상엔 당연히 문제가 없었지만, 파이썬의 sort는 timsort를 사용하는 것으로 알고 있어 어떤 문제가 있는지 전혀 모르겠는 상태에서 , 답을 찾아보았다. 

 

마지막 for문에서 sorted된 배열을 넣는 것은 시간 복잡도에 아무런 의미가 전혀 없었고 , 

실질적으로 도움이 된것은 input()대신 sys.stdin.readline()을 사용하는 것이었다.

이 방식을 잘 기억해두었다, 걸리는 시간의 감소로 활용하자 . 

sys.stdin.readline().split()도 문제없이 가능하다. 

<암기법> cin cout처럼, sys.stdin.readline()을 외우자 // 다만 n과 같은 prompt message가 있을때 주의

이를 이해하지 못하기 때문. 

 

 

<import sys>

<sys.stdin.readline()>

 

1427번 .. 바로 문제가 발생했다 

1. sys.stdin.readline으로 받으면, |n 떄문에 이 배열이 그대로 들어간다.

->

import sys

input = sys.stdin.readline()

num = int(input)

 

바로 int로 바꿔줘서 해결. 

 

2. join함수를 몰랐다..

 

''.join(리스트) -> 해당 리스트를 문자열로 바꾸어서 출력해준다.  

 

++APPEND([A,B])도 당연히 가능하다. 

이 2차원 배열은 , 처음엔 앞 그다음 뒤 순으로 (상식적으로 배열된다) 

 

list의 중복 제거는 그냥 list(set(arrlist))하면 되니까 아주 쉽다.

근데 list의 내부가 , 2차원 배열이거나 하는 상태라면? 이는 문제가 발생한다. 

이럴떄는 setver = set(tuple(x) for x in arrlist)로 한 후 list로 재변경한다! 

arr도, set도 , [[0]*100 for x in range (100)]처럼, 이 표현식 자체를 기억하자 

 

-> 즉시 어떠한 조건에 따른 배열 , set, tuple을 만들고 싶다 -> [ arr[x] for x in arr ] 처럼 이, 방식을 생각하자

*이떄는 in뒤에 배열 그자체를 부름에 주의는 하자! 

 

기억용 정렬에서 가장 많이쓰는것은 quick 도 heap도 아무것도 아니고

 arrayanswer.append([x,y,z])이다. 반드시 기억. 

 

다른꼴보다 , input =  sys.stdin.readline() // 이후 input()로 쓰자.

 

백준 18870 : 1. xarr = list(map(int,input().split())) -> 1개씩 받아서, 그것에 int를 적용시켜 한칸 한칸씩 리스트를 만들겠다는 뜻이다. 이걸 자주 활용하자 .

 

2. Dict의 시간복잡도가 O(1)이다!! 진짜 처음안 사실이다. 

 

 

arr2 = sorted(list(set(arr)))

dic = {arr2[i] : i for i in range(len(arr2))}

for i in arr:

   print(dic[i], end = ' ')

 

여러가지 정보가 숨어있다 .첫번째는 DIC을 생성하는 방법이다. {ARR2[I] ARR2의 I번쨰값 : IFOR I IN RANGE(LEN(ARR)) } -> 이러면 { 4 : 0(번째 INDEX) , -2 :2[번째 INDEX] } 이렇게.
 

DIC[3]은 3번째 INDEX의 KEY값을 출력한다

FOR I IN ARR은 , ARR LIST의 I번째 값을 바로 비교한다. 

 

즉 개념을 생각하면 arr를 만들고, 그 arr에서 중복을 제외한 순위를 메긴다. 그 후 { 그값의 : 순위 } 를 만들고, 원래 arr을 돌면서, dic[-4] -> -4라는 key(아까 그 값)의 순위를 return 한다. 

 

어려운 문제였으나.. 이정도는 풀줄 알아야한다. 1.{안에 for을 넣는 과정을 꼭 기억하자 } or []안에 -> 바로 생성

2. list(map(int,sys.stdin.readline().split))을 꼭 기억하자. 

3. dictionary에 , arr의 값을 key와 value를 반대로 넣고 ,

나중에 for i in arr을 통해서, 해당 arr의 값을 key로 다시 찾자

 

 

돌고 돌아! 모든 내용을 합친 문제가 나왔다.

 

백준 : 20920 . 

import sys

nmlist = list(map(int,sys.stdin.readline().split()))

N = nmlist[0]

M = nmlist[1]

x= 0

Nlist = []

Ninput = ""

dic = {}

while x < N :

    Ninput = sys.stdin.readline().rstrip()

    if len(Ninput) >= M :

        if Ninput in dic :

            dic[Ninput]= dic[Ninput]+1

        else :

            dic[Ninput] = 1

    x= x+1

sorteddic = sorted(dic.items(),key = lambda x : (-x[1],-len(x[0]),x[0]))

for j in sorteddic :

    print(j[0])

 

문제보단, 누가 봐도 정리하기 좋을 정렬 part 최종 정리를 가지고 왔다. 

 

1. DICTIONARY에 몇번 나왔나 기록하기 .

 

dic = {}

while x < N :

    Ninput = sys.stdin.readline().rstrip()

    if len(Ninput) >= M :

        if Ninput in dic :

            dic[Ninput]= dic[Ninput]+1

        else :

            dic[Ninput] = 1

    x= x+1

 

 

2. LAMBDA를 활용해서, 2개 이상의 정렬 조건을 가지고 정렬하기 .

*DICTIONARY.ITEMS()는, DICTIONARY와 같은 값 같은 배열 순을 LIST로만 변경한다. 

* SORTED 함수의 (DICT, KEY  = LABMDA X:  (-X[0],LEN(X[1]),-X[1])등의 변경이 가능하다. 

 

sorteddic = sorted(dic.items(),key = lambda x : (-x[1],-len(x[0]),x[0]))

 

3. DICTIONARY 중에서 가장 많이 나온 것 찾기 .

MAX(DICTIONARY[I])를 찾아서 , 이것들을 배열에 정리한다. 

정리한 이후에 , 그 가장 많이 나온 값만 모여있는  배열을 정리하던 해서 쓴다.

maxcount= max(ndic.values())
maxarr = []

for i in ndic :
    if ndic[i] == maxcount :
        maxarr.append(i)

if len(maxarr) == 1 :
    print(maxarr[0])
else :
    maxarr.sort()
    print(maxarr[1])

 

핵심은, DICTIONARY로 값 : 나온횟수 만들기.

KEY = LAMBDA X : (X[0],-X[1]) -> 배열의 내부 ,내부 조건 설정 가능. 

MAXARR의 값을 가지는 DICT[I] = MAX수 일때,

ARRAY.APPEND(I)를 할 수 있다. 

 

문자열 비교 시에는 왼쪽에서 오른쪽으로 숫자를 비교하며, 첫 번째 자리부터 큰 숫자가 있는 문자열이 큰 숫자로 간주됩니다.

이를 유의하자.