[PCCP] 2회차 : 시간 복잡도 & 해시 테이블

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

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

강사명 : 김태원 강사님

 

 

1. string에서 문자 counting

  1) string.count

  2) Counter 클래스

2. 시간복잡도와 Hash table

  1) defaultdict

---

1. string에서 문자 counting

 

1) string.count(char, start, end)

- 주어진 string에서 특정 문자 하나의 빈도수를 출력한다.

- char를 검색할 검색 구간을 지정할 수 있다.

  start : 검색을 시작할 index  / end : 검색을 끝낼 index

 

 

2) Counter 클래스

- string에 등장하는 각 char를 key로, char의 등장 횟수를 value로 하는 dictionary를 반환한다.

- char 빈도수의 내림차순 + 문자열 내 char의 순서대로 dictionary의 key로 등록한다.

- Counter 객체 간 (+), (-), 교집합, 합집합 연산이 가능하다.

from collections import Counter

#Counter 객체 생성
cnt = Counter(string)

cnt.most_common(n)	#개수 상위 n개 출력
cnt.elements()		#개수만큼 각 char를 출력

 

 

 

2. 시간복잡도와 Hash table

: Python에서는 dictionary 자료구조로 hash table를 구현한다. hash table은 탐색, 삽입, 삭제 작업의 시간복잡도는 평균 O(1)이다. 다만 충돌이 빈번하게 일어나면 최악의 경우 O(n)의 시간복잡도로 수렴할 수 있다.

 

1) defaultdict

- dictionary 자료형을 사용하다보면 key가 사전에 존재하지 않을때 error가 발생하는 경우가 많다. 이로 인해 value를 추가/삭제 등의 작업에서 key가 존재하는지 if문으로 확인하는 과정을 포함해야하는 번거로움이 있다.

- defaultdict는 사전에 지정하지 않은 key에 대하여 0 value를 자동적으로 가진다.

- defaultdict(value의 dtype)로 객체 생성

- key값을 사전에 지정하지 않아도 접근 가능하기 때문에 if문을 처리하는 번거로움을 줄일 수 있다.

- 문자열 count를 하는 경우 예시

# 일반 dictionary로 구현하는 경우
# char가 이미 key로 포함되어 있는지 확인하고
# 포함되어 있지 않은 경우 1로 초기화하는 과정 필요
cnt_dict = dict(int)
for char in s:
	if char in cnt_dict.keys():
    	cnt_dict[char]+=1
    else:
    	cnt_dict[char]=1
        

# defaultdict로 구현하는 경우
# 사전에 지정하지 않은 key의 value는 0으로 인식되기 때문에
# 바로 key에 접근 가능
from collections import defaultdict

cnt_defaultdict = defaultdict()
for char in s:
	cnt_defaultdict[char]+=1

 

 

 

- 도전문제 : 한 번만 등장한 문자

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

프로그래머스

from collections import defaultdict, Counter

#count method 이용
def sol_count(s):    
    return ''.join(sorted([ch for ch in s if s.count(ch)==1]))


#Counter 클래스 이용
def sol_Counter(s):
    cnt = Counter(s)
    
    ans=[]
    for key in cnt.keys():
        if cnt[key] == 1:
            ans.append(key)
    return ''.join(sorted(ans)) if len(ans)>0 else ""
            
                 
            
#defaultdict이용
def sol_defaultdict(s):

    cnt = defaultdict(int)
    for char in s:
        cnt[char]+=1 #key의 존재여부에 대한 if문 포함 안해도 가능
        
    ans=[]
    for key in cnt.keys():
        if cnt[key] == 1:
            ans.append(key)
    return ''.join(sorted(ans)) if len(ans)>0 else ""

 

 

- 연습 문제 : 두 수의 합

- list에 target-n 숫자가 존재하는지 확인하는 방법 => for문 한번만 돌면 되므로 O(1)의 시간복잡도

from collections import defaultdict

# 이진 탐색 이용
# 시간 복잡도 O(nlogn)
def solution_1(nums, target):
    answer = []

    nums.sort()
    i, j = 0, len(nums)-1
    while(i<j):
        sum = nums[i]+nums[j]
        if sum==target:
            answer+=[nums[i], nums[j]]
            i+=1
        elif sum<target:
            i+=1
        else:
            j-=1

    return answer if len(answer)>0 else [0,0]


# hash table 이용
# for문 1번만 => 시간 복잡도 O(n)
# 공간 복잡도 O(n)
def solution_2(nums, target):
    answer = []

    exist = defaultdict(int)

    for n in nums:
        if target - n in exist.keys():
            answer+=[n, target-n]
        else :
            exist[n]=1

    return sorted(answer) if len(answer)>0 else [0,0]

 

 

 

 

※ 문자 list를 string으로 변환하기

str = ''.join(chr list)

※ 문자 list 정렬 함수

# 1) sorted 함수
# 기존 list를 변화시키지 않음
# 새로운 list 객체를 리턴할 수 있음
sorted(char_list)
new = sorted(char_list)		# new와 char_list는 다름


# 2) sort() method
# 기존 list를 변화시킴
# 새로운 list 객체를 리턴하는 것이 아님
char_list.sort()
new = char_list.sort() 	# new에는 None이 리턴됨

 

 

 

 

 

 

Reference

https://dongdongfather.tistory.com/70
https://dongdongfather.tistory.com/69