[Python] 백준 알고리즘 배열 기억할 것들

백준 2750 - 수 정렬하기

a = int(input())

b=[]

for i in range (a):

     b.append(int(input()))

b.sort()

for i in range (a):

     print(b[i])

Python List 조작함수

∙ a.sort() : 리스트 원소 오름차순 정렬

∙ a.reverse() : 리스트 항목 순서 역순

∙ a.insert(위치, 값) (append()와 구분)

∙ a.extend(추가할리스트) : 리스트에 또다른 리스트를 추가한다

∙ a.count(찾을 값) : 리스트에서 해당 값의 개수를 센다

∙ a.clear() : 리스트 원소를 모두 지운다

∙ del(리스트명[i]) : 리스트 해당 인덱스의 값을 지운다

∙ 새로운리스트 = a.copy() : 리스트를 새로운 리스트에 복사한다

∙ 새로운리스트 = a.sorted() : 새로운 리스트에 정렬해서 복사한다

 

 

백준 2587 - 대표값2 (평균, 중앙값 구하기)

a = []

for i in range (5):

     a.append(int(input()))

 

a.sort()

print(sum(a)//5)

print(a[2])

위와 같은 방법은 입력 갯수가 5개로 정해져있어 가능했고, 가변적이라면

import statistics 라이브러리 (수학적 통계기능 제공) 를 통해

∙ statistics.mean() 평균값

∙ statistics.median() 중앙값

등 구할 수 있다.

 

 

백준 26305 - 커트라인

import sys

input = sys.stdin.readline

a, b = map(int, input().split())

c = list(map(int, input().split()))

c.sort(reverse=True)

print(c[b-1])

c.sort(reverse=True)를 통해 내림차순 구현 가능하다.

 

 

백준 10989 - 수 정렬하기 3

import sys

a = int(sys.stdin.readline())

b = [0] * 10001

for i in range (a):

     c = int(sys.stdin.readline())

     b[c]+=1

 

for i in range (10001):

     for j in range (b[i]):

          print(i)

바로 위 문제처럼 파이썬 리스트 sort 문제를 통해서도 풀 수 있겠지만,

현재 예제는 입력값이 10,000개 까지 들어오는 상당히 메모리가 큰 테스트값을 갖는다.

(sort는 원소값을 하나하나 비교해서 정렬하는 함수이므로 시간도, 메모리도 소요 多)

따라서 모든 원소를 전부 리스트에 append 한다면, 당연히 제한된 메모리크기인 8 MB를 넘게 됨.

 

따라서 일반적인 비교기반 정렬과 다르게 직접 원소값을 비교하지 않는 '계수정렬 (Counting sort)' 사용시

매우 큰 메모리의 입력값이 들어와도 메모리 초과없이 수행 가능하다.

① 최대 입력값 크기의 원소 0으로 구성된 리스트를 만들고

② 들어오는 입력값에 해당하는 리스트 원소의 인덱스에 갯수를 count 하는 것이다.

→ 만약 b = [0,1,1 .... ] 과 같다면, b[1] = 1 이므로 자연수 1은 1개, 자연수 2는 1개 .... 등으로 표현된다.

* 어차피 입력값이 자연수이므로, 따로 0에대한 처리 안 해줘도 결국 0은 +1 될 일이없어 계속 0개이므로 출력 안 된다.

 

따라서 리스트에 직접 데이터를 append 하는 것 보다 훨씬 작은 메모리로 수행이 가능하다.

✓ 함수 sort 를 이용했을 때 시간복잡도 O(nlogn)

✓ 계수정렬 사용시 최악의 경우 시간복잡도 O(N+K) (*N=배열크기, K=데이터 중 최댓값), 평균적으로 O(N) 이므로

계수정렬이 훨씬 시간복잡도가 나음을 알 수 있다.

 

 

백준 11650 - 좌표 정렬하기1

import sys

input = sys.stdin.readline

a = int(input())

b=[]

for i in range (a):

    b.append(list(map(int, input().split())))

b = sorted(b)

for i,j in b:

    print(i,j)

➝ 기본적으로 sort함수에 x, y 비교하는 기능이 들어있다는 점

 

[ 오류점 ]

✓  b.append(list(map(int, input().split()))) 에서 맵함수 안 쓰고 그냥 list(int(")) 했더니 런타임에러 뜸

✓  print부분 이중for문 쓸 필요없이 간단하게 출력 가능하다는 점

 

 

백준 11651 - 좌표 정렬하기2

import sys

input = sys.stdin.readline

a = int(input())

b=[]

for i in range (a):

    b.append(list(map(int, input().split())))

b.sort(key = lambda x : (x[1], x[0]))

for i,j in b:

    print(i,j)

✓  y축기준으로 먼저 정렬, 이후 x축으로 정렬하기 ➝ b.sort(key = lambda x : (x[1], x[0]))

✓  y축기준으로만 정렬 ➝ b.sort(key = lambda x : x[1])

➝  이 문제에선 y축 다음 x축도 고려해야하는것이 키포인트이다.

 

 

백준 1181 - 단어정렬

1) 리스트 ➝ 집합 ➝ 리스트

import sys

input = sys.stdin.readline

a = int(input())

b = []

for i in range (a):

    b.append(input().rstrip())

b = list(set(b))

b.sort()

b.sort(key = len)

for i in b :

    print(i)

2) 집합 ➝ 리스트 (메모리나 시간등은 1번과 동일하다)

import sys

input = sys.stdin.readline

a = int(input())

b = set()

for i in range (a):

    b.add(input().rstrip())

b = list(b)

b.sort()

b.sort(key = len)

for i in b :

    print(i)

✓  길이순으로 정렬, 길이 같으면 사전순 정렬이라면 사전순 정렬 선행, 길이순 정렬 마지막이다!

(길이 ⇨ 사전순 정렬하면 길이순 정렬 다 해놨는데 다시 사전순 정렬되어서 길이순 무효화 됨)

 

✓ 입력된 예제단어들 오른쪽에 " " 공백이 있으므로 input.rstrip()을 통해 공백제거 해야한다.

(아니면 첫번째 출력이 " " 가 됨.) *함정 빠지지 않도록 주의

 

✓ 중복제거를 위해 set 사용한다는점 (set은 set()로 선언, append 아닌 add 라는 점)

+ 한 원소 내 알파벳의 중복제거가 아닌, 단어의 중복제거라는 것 이해

 

 

백준 10814 - 나이순 정렬

import sys

input = sys.stdin.readline

a = int(input())

b = []

for i in range (a):

    x, y = input().split()

    b.append([int(x), y, int(i)])

b.sort(key=lambda x : (x[0],x[2]))

for i in b: print(i[0], i[1])

➝ x,y 받고 따로 append 하면 해결되는 문제. 입력받을 떄 한번에 b.append(input().split()) ... 로 접근하면 안된다.

 

 

⭐️ 백준 18870 - 좌표압축

1. 잘못 푼 코드 : 시간복잡도가 O(N^2) 로 시간초과.

a가 최대 1,000,000 개이므로 이중 for문 인덱스 수행시 시간 오래걸릴것이다.

#로직 = 주어진 인덱스 값보다 작은것 갯수세기

import sys

input = sys.stdin.readline

a = int(input())

b = list(map(int,input().split()))

c = [0]*a

d = list(set(b))

for i in range (a):

    for j in range (len(d)):

        if b[i] > d[j]:

            c[i]+=1

for i in c:

    print(i, end = " ")

 

* 해결방법 ➝ 계수정렬 했듯이 1차원적으로 접근

2. 제대로 푼 코드

import sys

input = sys.stdin.readline

a = int(input())

b = list(map(int,input().split()))

c = sorted(list(set(b)))

d = dict()

for i in range (len(c)):

        d[c[i]] = i #딕셔너리 형식으로 인덱스 부여

for i in b:

        print(d[i], end = " ")

✓  sort()는 정렬된 리스트를 반환하지 않는다. 정렬된 리스트를 할당하려면 sorted()함수를 이용.

[로직 이해]

예) b = [2, 4, -10, 4, -9] 라면 c = [-10, -9, 2, 4] 저장될 것이다. (중복제거, 오름차순 정렬)

∙ d[c[0]] (= d[-10]) = 0 *얘보다 작은거 0개

∙ d[c[1]] (=d[-9]) = 1 *얘보다 작은거 1개 ... 

와 같이 값이 저장된다. 딕셔너리의 값-키 속성 활용하는 것! (key -10일 때 value 0, key -9일때 value 1 ... )

따라서 출력 시 입력받은 원 리스트 b의 원소값으로 d[i] 출력하면 원소값이 키값이 되어 해당되는 밸류값이 출력된다.