수학과의 개발자 도전기

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

Lv2. 문제다!

하나의 숫자가 다른 숫자의 접두어에 온다면 이 두수는 정렬했을 때 앞뒤에 위치하게 된다.

따라서 이중 for문으로 다 탐색하지 않아도 되고, 앞 뒤의 숫자만을 가지고 비교하면 된다 

- 정답 풀이 :

def solution(phone_book):
    phone_book.sort()
    answer = True
    for i in range(1, len(phone_book)):
        n = len(phone_book[i - 1])
        if len(phone_book[i - 1]) < len(phone_book[i]):
            if phone_book[i - 1] == phone_book[i][ : n]:                  
                answer = False
                break
                
    return answer

- 시도해본 풀이

정확성은 다 맞았는데, 효율성에서는 시간초과로 틀렸던 문제다

아무래도 이중 for문으로 돌아서 시간 복잡도가 커진게 원인인 것 같다 

def solution(phone_book):
    phone_book.sort()
    answer = True
    for i in range(len(phone_book)):
        n = len(phone_book[i])
        for j in range(i + 1, len(phone_book)):
            if phone_book[i] == phone_book[j][ : n]:                
                answer = False
                break
                
    return answer

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42578

마지막에 answer - 1을 해주는 이유는 아무것도 입지 않는 경우를 빼줘야하기 때문이다 

문제 이해

1. dic에 옷의 종류별로 몇개인지 숫자를 센 다음에

2. 각 옷들로 몇 가지의 조합이 되는지 알아보는 거니까 (각 옷의 종류 + 1)을 해서 다 곱해준다

+ 1을 하는 이유는 그 옷을 입지 않는 경우도 있기 때문이다

3. 이렇게 하면 모든 옷을 입지 않는 경우도 포함되므로 이는 빼주고 반환해주면 답이다

- 정답 풀이 :

def solution(clothes):
    #의상 종류, 의상 이름 리스트 
    dic = {}
    for clothe in clothes:
        a, b = clothe[0], clothe[1]
        if b in dic:
            dic[b] += 1
        else:
            dic[b] = 1
            
    answer = 1
    for i in dic:
        answer *= (dic[i] + 1)
    
    return answer - 1

- 시도해본 풀이 : 

def solution(clothes):
    #의상 종류, 의상 이름 리스트 
    dic = {}
    for clothe in clothes:
        a, b = clothe[0], clothe[1]
        if b in dic:
            dic[b] += 1
        else:
            dic[b] = 1
            
    answer = 1
    
    for i in dic:
    	#여기랑
        answer *= dic[i]
    #여기가 미흡했음
    answer += len(clothes)   
    
    return answer

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42747

Lv2. 문제다!

내가 이해한 방식으로 풀었지만, 계속 틀려서 무엇이 문제인지 몰랐던 문제다. 문제에서는 h index가 citations의 값으로 이루어져있다고 하지 않았는데, 그렇다고 생각해 풀어서 아쉬운 문제다 

문제 이해

h index의 최댓값은 인용횟수에서 최댓값이므로 1부터 해당 숫자까지 반복문을 돌리고, 

h index 후보 i에 대해서 i 이상의 횟수로 인용된 논문의 수를 num에 저장한다 

만약 num >= i 인 i 중에 최댓값을 answer에 저장한 다음 반환하면 된다 

- 정답풀이 :

def solution(citations):
    citations.sort()
    answer = 0
    for i in range(1, len(citations) + 1):
        num = 0
        for j in citations:
            if j >= i:
                num += 1
        if num >= i:
            answer = max(answer,i)
            
    return answer

- 시도해본 풀이 

거의 모든 테스트에 실패했는데, 그 이유가 h는 citations에 있는 숫자가 꼭 아니어도 되는 것을 인지하지 못했다. 

[1, 2, 4, 4, 5] 의 경우 2가 아닌 3이 h index이다. (인용 횟수 3이상인 논문이 3이상이므로) 

def solution(citations):
    citations.sort()
    answer = 0
    
    for h in citations:        
        idx = citations.index(h)
        #h번 이상 인용된 논문의 갯수 
        n = len(citations[idx : ])
        if n >= h:
            answer = max(answer, h)
            
    return answer

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42885

Level2 문제다!

문제 이해

하나의 보트에 최대 2명, 두 사람의 무게 합이 보트 제한 무게보다 적어야 한다 

만약 이웃한 두 사람의 무게의 합이 무게 제한보다 크다면 각각 하나씩 타야한다 

풀이 이해

사용하는 보트 수가 최소가 되기 위해서는 남은 사람 중 몸무게가 가장 작은 사람과 가장 큰 사람을 같이 태워야한다(최적해)

이걸 알기위해 people 리스트를 오름차순 정렬해주고, 빠르게 연산하기 위해 deque()선언을 해준다 

남은 사람이 한 사람이라면 보트 수만 추가하고 끝낸다 

남은 사람이 2명 이상이고, 남은 사람 중 가장 가벼운 사람과 무거운 사람이 보트를 탈 수 있을 때 보트를 추가해주고, 

양 끝 원소를 삭제해준다 

아닌 경우라면 그냥 각자 하나씩 보트를 탄다 

- 정답 풀이 :

from collections import deque

def solution(people, limit):
    people.sort()
    answer = 0 
    people = deque(people)
    
    while people:
        if len(people) == 1:
            answer += 1
            break
        #가장 무거운 사람과 가장 가벼운 사람이 탈 수 있을 때
        elif people[0] + people[-1] <= limit:
            answer += 1
            people.pop()
            people.popleft()
        #가장 무거운 사람이 하나의 보트만 탄다
        else:
            answer += 1
            people.pop()
            
    return answer

- 시도해본 풀이 :

지금보니 완전 삽질한 풀이다,,,

정렬한 후 0 인덱스부터 시작해서 보트에 2명이 있다면 다음 보트를 넘기고

1명이 있고, 보트에 탄 사람의 무게와 아직 보트에 없는 사람의 무게 합이 제한 무게 이하면 추가하고

아니면 각자 타는 걸로 생각했는데 

뭔가 풀이가 명확하지가 않다 

명확하게 해보자

def solution(people, limit):
    people.sort()
    count = 1 #보트 수 
    boat = 1 #보트에 있는 사람 수 
    weight = people.pop(0) #보트에 있는 사람의 총 무게 
    
    for person in people:
        if boat == 2:
            count += 1 
            boat = 1
            weight = person
        elif boat < 2:
            if weight + person <= limit:
                weight += person 
                boat += 1
            else: 
                boat = 1 
                count += 1
                weight = person 
                                
    return count