수학과의 개발자 도전기

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

Lv2. 문제다!

처음에는 내가 문자 규칙을 다 알아낸 다음 주어진 단어에 따라 규칙을 통해 순서를 찾아내는 거라고 생각했다

근데 규칙을 어떻게 찾아야할지 잘모르겠어서 막막했던 문제다

풀이를 보니까 문자 개수가 5개밖에 안되므로 이들로 만들 수 있는 모든 문자열을 만든다음 정렬한 후 해당 단어의 index + 1을 출력하면 된다 

product가 뭔지 몰라서 알아봤다 

product는 중복 순열을 만들어내는 함수로, 형식은 product(list, reapeat = num)형식으로 하면 list의 원소들 중에서 num 길이 만큼의 중복된 순열을 반환한다 

문제 이해 

1. 1자리수부터 6자리수 만큼의 주어진 문자들로 중복순열을 만들어 낸 다음 words에 추가한다 

2. words에서 주어진 word의 인덱스를 찾고 거기에 +1한 값을 반환한다 

- 정답 풀이 :

from itertools import product
# 갯수가 5개이므로 중복순열을 이용해서 가능한 모든 조합을 구한 후 index구한다
def solution(word):
    words = []
    for i in range(1, 6):
        for c in product(['A', 'E', 'I', 'O', 'U'], repeat = i):
            words.append(''.join(list(c)))
            
    words.sort()
    return words.index(word) + 1

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