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

언어, 프레임워크/Python & Django

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

jaee 2020. 8. 21. 20:01

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

프로그래머스 Level 1

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

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

대문자와 소문자가 섞여있는 문자열 s가 주어집니다. s에 'p'의 개수와 'y'의 개수를 비교해 같으면 True, 다르면 False를 return 하는 solution를 완성하세요. 'p', 'y' 모두 하나도 없는 경우는 항상 True를

programmers.co.kr

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

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

String형 배열 seoul의 element중 Kim의 위치 x를 찾아, 김서방은 x에 있다는 String을 반환하는 함수, solution을 완성하세요. seoul에 Kim은 오직 한 번만 나타나며 잘못된 값이 입력되는 경우는 없습니다. 제

programmers.co.kr

파이썬 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

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

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조��

programmers.co.kr

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

전화번호부에 있는 번호의 길이를 갖고 오름차순 정렬시킨다. 정렬시킨 다음 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를 통해 값을 찾는 것이 더 효율적일 것이기에 단순히 직관적으로만 생각하지 말고 풀자!

티스토리