[TIL] Python 쉬운 알고리즘 문제 풀기 + 정리

 

오늘도 소소한 알고리즘 문제를 통해 알게 된 내용 정리 ✍️

 

프로그래머스 Level 1

문제: https://programmers.co.kr/learn/courses/30/lessons/12916

코딩테스트 연습 - 문자열 내 p와 y의 개수

• string.count(): 문자열 메서드. 해당 문자열에 찾고자 하는 문자의 개수 반환. 첫 번째 인자에는 찾고자 하는 문자열, 두 번째 인자에는 시작 인덱스, 세 번째 인자에는 끝 인덱스 (끝 인덱스는 포함되지 않으므로 실제 범위는 끝 인덱스-1)

t = 'FFFDDDJJJ'

t.count('F') # 3
t.count('I') # 0
t.count('J', 6) # 3
t.count('J', 6, 8) #2

 

 

문제: https://programmers.co.kr/learn/courses/30/lessons/12919

코딩테스트 연습 - 서울에서 김서방 찾기

• 파이썬 3.6 이상부터는 f-string으로 문자열과 변수를 합쳐서 사용할 수 있음

['Lee', 'Kim', 'Park']

def solution(seoul):
    return f"김서방은 {seoul.index('Kim')}에 있다" # 김서방은 1에 있다

• string.format(): format()에서 수행한 연산 결과를 문자열의 중괄호에 할당함

['Lee', 'Kim', 'Park']

def solution(seoul):
    return "김서방은 {}에 있다".format(seoul.index('Kim')) # 김서방은 1에 있다

 

 

프로그래머스 Level 2

문제: https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

그냥 직관적으로 풀었을 때:

전화번호부에 있는 번호의 길이를 갖고 오름차순 정렬시킨다. 정렬시킨 다음 0번째 인덱스에 있는 요소를 기준으로 삼는다. 그리고 해당 번호가 다른 번호들의 접두어가 되는지 확인한다. 이 과정을 0번째 인덱스, 1번째 인덱스... len(phone_book) - 2번째 인덱스까지 반복하면 모든 경우를 탐색할 수 있다.

def solution(phone_book):
    phone_book.sort(key=len)
    
    c = 0
    while c < len(phone_book) - 1:
        i = c + 1
        while i < len(phone_book):
            if phone_book[c] == phone_book[i][:len(phone_book[c])]:
                return False
            i += 1
        c += 1
        
    return True

• list.sort(), sorted() 모두 key 매개 변수를 통해 리스트의 각 요소에 적용할 함수를 지정할 수 있음

 

hash를 사용해서 풀었을 때:

전화번호부에 있는 모든 번호를 갖는 딕셔너리 h_map을 만든다. 그리고 전화번호부의 모든 전화번호를 하나하나씩 확인한다. 만약 전화번호의 숫자 조합이 h_map 딕셔너리에 있으면서, 해당 숫자 조합이 전화번호와 다르다면, 이는 h_map 딕셔너리에 있는 번호 하나가 현재 전화번호의 접두어가 된다는 의미이므로 False를 반환한다.

def solution(phone_book):
    h_map = {}
    for phone_number in phone_book:
        h_map[phone_number] = True
    
    for phone_number in phone_book:
        tmp = ''
        for num in phone_number:
            tmp += num
            if h_map.get(tmp) and tmp != phone_number:
                return False
            
    return True

 

딕셔너리에 찾고자 하는 키 값이 있는지 확인하는 법

• dictionary.get('key'): 'key'에 해당하는 키 값이 있다면 해당 키와 대응하는 값을 반환한다. 만약 찾고자 하는 키 값이 없다면 None을 반환한다.

• key in dictionary: 'key'에 해당하는 키 값이 있다면 True를 반환하고, 없으면 False를 반환한다.

 

 

sort하는 것보다 hash map의 key를 통해 값을 찾는 것이 더 효율적일 것이기에 단순히 직관적으로만 생각하지 말고 풀자!

 

 

 

 

 

---

참고 자료

• https://docs.python.org/ko/3/howto/sorting.html
• https://www.pymoon.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%97%90%EC%84%9C-%EB%94%95%EC%85%94%EB%84%88%EB%A6%AC-%ED%82%A4-%EA%B0%92-%EC%B2%B4%ED%81%AC%ED%95%98%EA%B8%B0