개발자 아지트

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

문제설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

k는 1 이상 5,000 이하인 자연수입니다.

dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.

dungeons의 가로(열) 길이는 2 입니다.

dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.

"최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.

"최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.

서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입출력 예

k         dungeons         result

80        [[80,20],[50,40],[30,10]]      3

입출력 예 설명

현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.

남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.

남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.

남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.

남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

문제 해결 방법

1. dungeons에서 모두 나올 수 있는 순서에 대해 경우의 수를 순열로 뽑는다.

2. 리스트를 하나 만들고, 순열로 뽑은 모든 경우의 수에 대해서 조건을 따져가면서 던전에 방문한 횟수를 카운트 하여 최종적으로 카운트 한 수를 해당 리스트에 추가한다. 

2-1. 위에서 말한 조건으로 각 던전의 최소 필요 피로도가  k와 같거나 커야지 던전에 방문할 수 있으니 해당하는 조건을 체크한다. 

2-2. 만약 k가 특정 던전에 방문할 수 있다면 k에서 소모 피로도를 빼준다. 

3. 2번에서 만든 리스트에서 max값을 구하여 출력한다. 

코드 구현

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    
    cpk=k
    cases = list(permutations(dungeons, len(dungeons)))
    checkList=[]
    
    for i in range(len(cases)):
        cpK=k
        checkcheck = 0
        for j in range(len(cases[i])):
            if cpK >= cases[i][j][0]:
                cpK = cpK - cases[i][j][1]
                checkcheck += 1
            else:
                pass
            
            if j == len(cases[i])-1:
                checkList.append(checkcheck)

    answer = max(checkList)
    
    return answer

주석 포함 코드

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    
    #print('k', k, 'dungeons', dungeons)
    # 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"
    # 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"
    
    #최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됨
    
    #하루에 한 번씩 탐험할 수 있는 던전이 여러개
    
    # 1. dungeons는 [0]기준 MAX를 뽑는다. 
    # 2. dungeons의 순열을 뽑는다. 
    
    
    cpk=k
    
    
    cases = list(permutations(dungeons, len(dungeons)))
    #print(cases)
    
    checkList=[]
    #print("")
    
    for i in range(len(cases)):
        #maxx = cases[i][0][0]
        cpK=k
        #print("1 cpK", cpK)
        checkcheck = 0
        #print('i', i, cases[i])
        for j in range(len(cases[i])):
            #print('j', j, cases[i][j])

            if cpK >= cases[i][j][0]:
                cpK = cpK - cases[i][j][1]
                #print('cpK', cpK)
                checkcheck += 1
            else:
                pass
            
            if j == len(cases[i])-1:
                checkList.append(checkcheck)
            
        #print("")
        #print("")


    #print(checkList)
            
    answer= max(checkList)
    
    return answer

시간/공간 복잡도

최악의 경우 O(N^2)

최적화 및 개선

하지않았다. 

어려웠던 점

안풀어본 문제유형(완전탐색)이라 완전 쫄았다. 완전탐색 문제를 풀기위해서 대략 어떤 알고리즘이 필요한지 찾아보고 일단은 대충이라도 공부했다. (요즘 좀 바쁨) 암튼 대충 이런저런 방법으로 생각해보다가 문제를 풀었다 .

진짜 내가 이 문제를 푼거에 대해서 아주 놀랍다 하하 박수 ~~~ 짝짝~~

생각보다 진짜 별거아니네 !!! 쫄지마 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

https://school.programmers.co.kr/learn/courses/30/lessons/42839

문제설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다.

numbers는 0~9까지 숫자만으로 이루어져 있습니다.

"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers return

"17"      3

"011"    2

입출력 예 설명

예제 #1

[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2

[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

11과 011은 같은 숫자로 취급합니다.

문제 해결 방법

1. numbers 문자열을 문자로 떼내어 리스트에 정리한다. 

2. 정리한 리스트를 permutations함수를 통해 각 원소들을 통해 만들 수 있는 조합 모든 경우(한자리, 두자리, 세자리 ,, numbers의 길이만큼의 자리)를 리스트에 정리한다. 

3. 소수판별 함수를 만들어서 위의 리스트 원소들을 대상으로 소수 판별을 한다. 

4. 결과 출력

코드 구현

from itertools import permutations

def solution(numbers):
    answer = 0
    numbers= str(numbers)
    Nlist=[]
    
    for i in range(len(numbers)):
        Nlist.append(str(numbers[i]))
        
    totalList = []
    for i in range(len(numbers)):
        if i == len(numbers):
            break
        totalList += list(map(''.join, (permutations(Nlist, i+1))))
    
    totalList=list(map(int, totalList))
    totalList=set(totalList)
    totalList=list(totalList)
    
    if 0 in totalList:
        totalList.remove(0)
    
    if 1 in totalList:
        totalList.remove(1)
    
    
    def primenumber(x):
        # 2부터 x-1까지 순회
        for i in range(2, x):
            if x % i == 0:
                # 하나라도 나눠 떨어지면 False 반환
                return False
        # 아무것도 나눠 떨어지는게 없으면 True 반환
        return True
    
    for i in range(len(totalList)):
        if primenumber(totalList[i])== True:
            answer+=1
            
    
# 어둠의 잔해 소수 판별기 
    
#     topic=2
#     check=0

#     for i in range(len(totalList)):
#         while 1:
#             if totalList[i] == 0:
#                 # 원소 0은 pass
#                 pass
            
#             if totalList[i] % topic == 0:
#                 check+=1
#                 if check ==1:
#                     break
#                 topic+=1   
#             else:
#                 topic+=1
            
#             if topic == totalList[i]:
#                 topic = 2
#                 break
                
#         if check == 1:
#             answer+=1
#             check=0
#         else:
#             check=0
#             pass
        

    
    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

하지않음 

어려웠던 점

문제를 어떻게 풀어야하겠다는 것은 알겠지만서도, 자잘한 문법, 함수 사용법을 정확하게 몰라서 좀 시간이 걸렸다. 

생각하는데로 출력하고 활용하는것이 좀 어려웠다. 

특히 튜플 자료형, join함수, map함수, map객체, set함수 등에 대해서 잘 몰라서 새로 찾아봤다. 

소수를 찾는 로직도 예전에 문제를 한번 풀어봤었는 경험으로 코드를 짜봤는데(어둠의 잔해 소수 판별기), 시간초과가 나왔다. 왜그럴까??? 빈틈없이 짰다고 생각했는데, 시간날때 다시 한번 봐야겠다.  

https://school.programmers.co.kr/learn/courses/30/lessons/42840#

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...

2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...

3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

시험은 최대 10,000 문제로 구성되어있습니다.

문제의 정답은 1, 2, 3, 4, 5중 하나입니다.

가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

answers return

[1,2,3,4,5]          [1]

[1,3,2,4,2]          [1,2,3]

입출력 예 설명

입출력 예 #1

수포자 1은 모든 문제를 맞혔습니다.

수포자 2는 모든 문제를 틀렸습니다.

수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2

모든 사람이 2문제씩을 맞췄습니다.

문제 해결 방법

1. 수포자 1, 2, 3의 정답 패턴이 들어있는 리스트 생성

2. 각각의 정답을 answers와 대조하여 각각의  score을 매김

3. score중에서 max가 있으면 해당 값을 answer리스트에 삽입, 만약 max값을 가지는 사람이 여러명이거나 셋다 값이 같다면 해당 케이스에 대해서 처리해줘야함

코드 구현

def solution(answers):
    answer = []
    
    l1=[1,2,3,4,5]
    l2=[2,1,2,3,2,4,2,5]
    l3=[3,3,1,1,2,2,4,4,5,5]
    
    len_a = len(answers)
    cnt = 0
    score1 = score2 = score3 = 0
    for i in range(len(answers)):
        cnt = i
        if cnt >= len(l1):
            cnt = cnt % len(l1)
        if l1[cnt] == answers[i]:
            score1+=1 
            
    cnt = 0  
    for i in range(len(answers)):
        cnt = i
        if cnt >= len(l2):
            cnt = cnt % len(l2)
        if l2[cnt] == answers[i]:
            score2+=1 

    cnt = 0
    for i in range(len(answers)):
        cnt = i
        if cnt >= len(l3):
            cnt = cnt % len(l3)
        if l3[cnt] == answers[i]:
            score3+=1 

    total_list=[]
    total_list.append(score1)
    total_list.append(score2)
    total_list.append(score3)
    
    if score1==score2==score3:
        answer.extend([1,2,3])
    else:
        maxx=(max(total_list))
        answer.append(total_list.index(max(total_list)) + 1)
        total_list[total_list.index(max(total_list))] = 0
        if maxx in total_list:
            answer.append(total_list.index(maxx)+1)

    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

하지않음

어려웠던 점

문제 이해를 잘 못했어서 하루를 날렸다. 

세세한 조건 따질줄 아직 잘 모르는것 같다. 

그리고 조건을 따질 줄 안다 하더라도 이걸 이렇게까지 해야한다고? 싶은 생각에 자꾸 막히는듯 함

https://school.programmers.co.kr/learn/courses/30/lessons/42842#

문제설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.

노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.

카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

brown   yellow   return

10        2         [4, 3]

8         1         [3, 3]

24        24        [8, 6]

문제 해결 방법

1. 가로>=세로 라는 조건에 유의한다. 

2. 노란 박스는 1층일 수도 있고, 2층일 수도 있고, ... N층일 수도 있다. 

3.  2번에 의해 노란박스가 1층이면 노란박스의 가로길이는 yellow값이 된다. 

4. 노란박스의 층수가 정해지면 그에 따라 brown을 가늠해볼 수 있게된다. 
    brown은 노란박스 층수+2가 세로가 되고,  노란박스+2가 가로가 된다. 이게 노란박스를 품은 brown이다. 

    즉, brown+yellow의 값인 total 격자 수가 된다. 

5. 4번을 충족하는 노란박스의 층수를 찾으면 문제가 풀린다. 

코드 구현

def solution(brown, yellow):
    answer = []
    total = int(brown) + int(yellow)
    
    x = 1
    
    while 1:
        if yellow%x==0:
            y = yellow//x
        
        if (x+2)*(y+2) == total and y+2 >= x+2:
            answer.append(y+2) # 가로
            answer.append(x+2) # 세로
            break
        else:
            x+=1
        
    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

처음에 답이 안나왔는데, 다음 값의 정확도를 개선하였음

yellow를 x로 나누면 y값이 나온다. 이때 yellow가 x로 나누어떨어져서 나머지가 없는 x의 값에 의한 y를 찾게끔하였음. 

어려웠던 점

없음. 항상 괜히 쫄지마 !