[PCCP] 3회차 : 정렬 & 자료구조

교육 프로그램명 : 혁신융합대학 프로그래머스 PCCP(Python) 대비 교육

교육 일시 : 2023.08.23 10:00~15:00

강사명 : 김태원 강사님

 

1. 정렬 함수

2. Stack 스택 구현

3. Queue 큐 구현

 

---

1. 정렬 함수

1) sort method

- list나 array를 정렬하는 method

- 새로운 list 객체를 리턴하지 않고 기존 list를 변화시킨다.

list.sort()			# 오름차순
list.sort(reverse = True)	# 내림차순

- key를 지정한 정렬 : 정렬시 사용할 기준값 key를 지정하여 정렬한다.

list = [(x1, y1), (x2, y2),,,] 형식일때

# x값을 기준으로 내림차순 정렬
list.sort(key = lambda v : -v[0])

# y값을 기준으로 오름차순 정렬
list.sort(key = lambda v : v[1])

# x값을 기준으로 오름차순 정렬하고, x값이 같으면 y값을 기준으로 내림차순 정렬
list.sort(key = lambda v : (v[0], -v[1]))

 

2) sorted 함수

- array, tuple, string 등 순회가 가능한 모든 iterable 객체에 사용할 수 있는 정렬 함수

- 기존 list를 변화시키지 않고, 새로운 list 객체를 리턴한다.

new = sorted(list)			#오름차순
new = sorted(list, reverse=True)	#내림차순

- key를 지정한 정렬 : 정렬시 사용할 기준값 key를 지정하여 정렬한다.

# x값을 기준으로 내림차순 정렬
new = sorted(list, key = lambda v : -v[0])

# y값을 기준으로 오름차순 정렬
new = sorted(list, key = lambda v : v[1])

# x값을 기준으로 오름차순 정렬하고, x값이 같으면 y값으로 오름차순 정렬
new = sorted(list, key = lambda v: (v[1], v[0]))

 

- 연습 문제 : 이진수 정렬

- dictionary 대신 [ [숫자, 이진수에서 1의 개수], ,,,] 2차원 배열을 생성해서 각 숫자에 대한 정보를 저장

- key가 있는 정렬을 사용해 v[1] = 이진수에서 1의 개수를 기준으로 list를 정렬

※ 이진수에서 1의 개수 세기 문제
    bin(n) : 숫자 n의 2진수 표현을 string 형태로 반환
    bin(n)[2:] : 2진수 표현의 string type
    bin(n)[2:].count('1')] : string에서 '1'의 개수 세기

def solution(nums):
    ans=[]
    for n in nums:
        ans.append([n, bin(n)[2:].count('1')])

    ans.sort(key = lambda v : (v[1], v[0]))
    #혹은 ans = sorted(ans, key = lambda v: (v[1], v[0]))

    result=[]
    for i in range(len(ans)):
        result.append(ans[i][0])

    return result

 

- 도전 문제 : 귤 고르기

- 귤 사이즈별로 개수 세어서 각 사이즈별 개수 정보를 저장하는 dictionary를 생성

- sorted 함수에 개수값만 넣어서 내림차순 정렬

https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

def solution(k, tangerine):		# tangerine = 귤 사이즈 데이터
    size = Counter(tangerine)		# 귤 사이즈별 개수 dictionary
    freq = sorted(size.values(), reverse=True)	# 사이즈 값을 내림차순 정렬
    
    count=0    
    for i in freq:
        if k>0:
            count+=1
            k-=i
    return count

 

 

 

2. Stack 스택 구현

- Python에서 가장 쉽게 stack를 구현하는 방법은 list 객체를 사용하는 것이다.

stack = list()	#스택 객체 생성

stack.append()	#위에서 넣기
stack.pop()	#위에서 빼기
stack[-1]	#가장 위의 원소

 

 

 

3. Queue 큐 구현

- Python에선 deque 클래스를 이용해 Queue를 구현할 수 있다.

from collections import deque

queue = deque()		#큐 객체 생성

queue.pop()		#뒤에서 뻬기
queue.popleft()	#앞에서 빼기
queue.append()	#뒤에서 넣기
queue.appendleft()	#앞에서 넣기

 

- 도전 문제 : 스킬 트리

https://school.programmers.co.kr/learn/courses/30/lessons/49993#fnref1

프로그래머스

 

- skill에 포함되는 문자가 나온다면 무조건 skill_queue에 저장된 순서대로 나와야하므로

  스킬 트리에서 skill에 포함되는 문자를 만났을 때, 해당 문자 == skill_queue.pop() 인지 확인

- deque(list) : list 원소들로 queue 생성

from collections import deque

def solution(skill, skill_trees):
    count=0
    
    for tree in skill_trees:
        flag=1
        skill_q = deque(skill)
        for char in tree:
            if char in skill_q:
                if char != skill_q.popleft():
                    flag=0
                    break
        if flag==1:
            count+=1
        
    return count