수학과의 개발자 도전기

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

문제 이해

1. 해당 던전을 탐색하려면 해당 던전의 0인덱스 값 이상의 k 값을 가지고 있어야한다. 해당 던전을 지나가면 1인덱스의 값만큼 k가 줄어든다 

2. 최대한 많은 던전을 탐색해야한다. 그러기 위해선 큰 진입 피로도 던전부터 시작하고, 적게 피로도가 감소하는 방향으로 가야한다 

search()함수의 작접

1. cnt_list에 전달받은 cnt값을 추가한다

2. dungeons 요소를 하나씩 확인하면서, 만약 현재 최소 필요 피로도가 k보다 작거나 같다면 temp_list에 dungeon 리스트를 복사한다

3. 이후 temp_list의 현재 인덱스 값(i)를 삭제한다

4. search()함수를 재귀 호출하여 반환받은 값을 cnt_list에 추가한다

5. cnt_list 리스트에 존재하는 값 중 최댓값을 반환한다

즉, 던전에 들어갈 때마다 피로도를 감소시키고, 현재 들어간 던전을 제외한 리스트를 다시 search()함수에 전달하여 가장 많이 들어간 값을 반환한다 ????????

- 정답 풀이 :

참고한 블로그

def solution(k, dungeons) :
    return search(k, dungeons, 0)


def search(k, dungeons, cnt) :
    cnt_list = [cnt]

    for i in range(len(dungeons)) :
        if dungeons[i][0] <= k :
            temp_list = dungeons.copy()
            del temp_list[i]
            cnt_list.append(search(k - dungeons[i][1], temp_list, cnt + 1))

    
    return max(cnt_list)

- 시도해본 풀이 :

최대한 많은 던전을 탐색하기 위해 0인덱스와 1인덱스의 차이를 기준으로 내림차순 정렬한 후 탐색 가능한 던전을 탐색한 후 그 수를 세면서 진행했는데 테스트 케이스 몇 개에서 실패했다 

def solution(k, dungeons):
    #해당 피로도랑 기준 피로도랑 제일 차이 많이 안 나면서 감소되는 피로도 제일 적은거
    for i in range(len(dungeons)):
        dungeons[i].append(abs(dungeons[i][0] - dungeons[i][1]))
            
    dungeons.sort(key = lambda x : x[2], reverse = True)

    count = 0
    for dungeon in dungeons:
        a, b = dungeon[0], dungeon[1]
        if k >= a:
            count += 1
            k -= b
    
    return count

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

Lv2. 문제이고, 스스로 푼 문제다!

i번째 인덱스 이상인 수가 i + 1 ~ n -1 인덱스 사이에 총 몇 개 인지 세는 문제이다

문제 이해

시간 초과를 피하기 위해 deque를 이용해서 더 빠르게 계산할 수 있도록 했다

1. prices에서 원소(x)를 하나 pop()한 다음, 나머지 prices 원소들 중에 해당 원소 미만인 수가 있는지 확인하기 위해 for문을 돌린다.

2. 예제에서 멈출 때 마저도 시간을 센다고 했으므로 time += 1을 해주고 for문을 나온다

3. x 이상인 수가 나머지 prices에 있다면 계속해서 time += 1을 해준다

4. x에 해당하는 time을 answer에 추가해 준 후 반환한다 

- 정답 풀이 :

from collections import deque
def solution(prices):
    answer = []
    prices = deque(prices)
    
    while prices:
        x = prices.popleft()
        time = 0
        for price in prices:
            if x > price:
                time += 1
                break
            time += 1
            
        answer.append(time)
        
    return answer

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

Lv2 문제이다. 어려워보이지 않아서 여러번 시도했지만, 실패했던 문제다. 풀이 다시 익히자!

문제 이해 

1. 시작할 때 문제에서 원하는 위치의 값을 가진 걸 식별하기 위해서 priorities를 다시 세팅한다. (위치, 우선순위 값) 으로

2. 0인덱스에 있는 숫자보다 큰 숫자가 더 큰 숫자가 priorities에 있다면 해당 값은 다시 오른쪽 끝에 추가한다

3. 만약 priorities가 우선순위대로 정렬이 되었다면 이제 하나씩 빼면서 count += 1을 해준다

4. while문을 진행하다가 원하는 위치의 값을 마주쳤다면(value[0] == location) 그동안 셌던 count를 반환한다 

- 정답 풀이 : 

def solution(priorities, location):    
    
    for i in range(len(priorities)):
        priorities[i] = (i, priorities[i]) #번호, 중요도
        
    
    count = 0
    while True:
        value = priorities.pop(0)
        flag = True
        for i in range(len(priorities)):
            #더 중요한 프린트물이 뒤에 있다 
            if value[1] < priorities[i][1]:
                priorities.append(value)
                flag = False 
                break
        #가장 중요한 프린트물이 가장 첫번째일 때 
        if flag:
            count += 1
            if value[0] == location:
                return count

- 문제 : 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