[TIL] 알고리즘 TIL Day 1

🟢 전화번호 목록

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

My Solution

1. 전화번호를 길이순이 아닌 앞자리부터 작은 순으로 정렬한다.
2. for loop를 돌면서 앞의 전화번호가 다음 전화번호의 접두가사 되는지 확인하고 true/false를 출력한다. 이 때 startswith 함수 사용

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False
            break
    return True

Alternative solution

파이썬을 이용한 알고리즘 PS에서 매우 유용하게 쓰이는 내장함수 zip을 활용한 풀이방법이다.
전화번호를 정렬 후, 정렬된 전화번호와 2번째 요소부터 시작하는 정렬된 전화번호 리스트를 zip에 넣어주면 알아서 매칭을 하면서 접두사 여부 탐색을 시작한다.

cf) zip 안에 들어가는 리스트들은 길이가 달라도 무방하다. 하지만 길이가 다를 경우, 가장 짧은 리스트의 길이까지만 매칭을 진행한다.

def solution(phoneBook):
    phoneBook = sorted(phoneBook)
    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

🟢 기능개발

https://programmers.co.kr/learn/courses/30/lessons/42586

My Solution

1. 각 기능의 개발속도 계산 후 리스트 생성
2. 생성한 리스트에서 for loop 돌면서 뒤에 있는 기능의 개발 속도가 앞에 있는 개발속도보다 빠를 경우 앞에 있는 개발속도로 값 대체 (같은 날 배포되기 때문)
3. Counter을 이용해 배포일별 배포되는 기능 수 계산

def solution(progresses, speeds):
    days = []
    for i, j in zip(progresses, speeds):
        days.append(math.ceil((100-i)/j))
        
    for i in range(len(days)-1):
        if days[i] >= days[i+1]:
            days[i+1] = days[i]
    
    return list(Counter(days).values())

Alternative solution

리스트를 아주 적절하게, 영리하게 사용해서 해결한 풀이방법이다.

Q라는 비어있는 리스트를 생성하는데, 이 리스트는 2차원 array로 만든다. 내부 리스트의 첫번째 요소는 개발속도, 두번째 요소는 해당 배포일에 배포되는 기능 수로 지정한다. zip으로 매칭하면서 현재 기능의 개발속도가 앞선 기능의 개발속도보다 큰 경우에는 그대로 리스트에 추가하지만, 현재 기능이 앞선 기능보다 속도가 빠를 경우, 배포되는 기능 수 +=1 을 하여 해당 배포일에 배포되는 기능의 수를 1씩 늘린다.

def solution(progresses, speeds):
    Q=[]
    for p, s in zip(progresses, speeds):
        if len(Q)==0 or Q[-1][0]<-((p-100)//s):
            Q.append([-((p-100)//s),1])
        else:
            Q[-1][1]+=1
    return [q[1] for q in Q]