개발자 아지트

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/12906

문제설명

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

• arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
• arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

제한사항

배열 arr의 크기 : 1,000,000 이하의 자연수

배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

입출력 예

arr       answer

[1,1,3,3,0,1,1]      [1,3,0,1]

[4,4,4,3,3]          [4,3]

입출력 예 설명

입출력 예 #1,2

문제의 예시와 같습니다.

문제 해결 방법

stack을 이용하여 문제를 푼다. 
1. stack 구실을 할 임의의 리스트를 하나 만든다. 

2. arr의 원소를 순회하면서 임의의 리스트에 첫번째 원소를 push한다. 

2-1. 첫번째 이후의 원소들은 임의의 리스트의 마지막에 push한 값을 pop을 통해 꺼낸다.

2-2. 2-1번을 통해 꺼낸 값과 현재 넣고자 하는 arr의 원소를 비교하여 값이 같으면 pass하고 같지 않으면 push 한다. 

코드 구현

1. 효율성 통과하지 못한 코드 

def solution(arr):
    answer = []
    
    # pivot 변수 = p
    # 이전 pivot을 기억하는 변수 = pre_p
    check = 0
    pre_p = arr[0]
    l=len(arr)
    for i in range(1, len(arr)):
        p = arr[i]
        #print('p', p, 'pre_p', pre_p)
        if pre_p == p:
            pre_p = p
            arr[i] = 10
            # '-'를 세는 변수 = check
            check+=1
        else:
            pre_p=p
    
    for i in range(check):
        arr.remove(10)
        
    answer = arr
    return answer

2. 효율성 통과한 코드

def solution(arr):
    stack = []
    
    for i in range(len(arr)):
        if i == 0:
            stack.append((arr[i]))
        else:
            top = stack.pop()
            stack.append(top)
            if arr[i]==top:
                pass
            else:
                stack.append(arr[i])
    
    return stack

시간/공간 복잡도

1. 효율성을 통과하지 못한 코드: O(N^2)

2. 효율성을 통과한 코드: O(N)  

최적화 및 개선

처음에 효율성을 통과하지 못한 코드에 대해서 중첩 되지 않는 for문을 썼는데 왜 시간복잡도 효율성이 통과되지 않는지 이해가 안갔다. 혹시 내가 stack자료구조를 고려하지 않고 코드를 작성해서 그 부분에서 오류가 나는건가? 싶었다. 그래서 코드를 stack자료구조를 고려해서 리스트를 stack화 해서 코드를 짰다. 확실히 pop함수를 사용해서 그런가 편리하고 뒷처리를 해주지 않아도 되는 점이 깔끔하고 좋았다. 그리고 효율성에도 통과했다. 

그렇다면 1번 코드는 어디에서 효율성을 많이 잡아먹는가?

바로 for문에 있는 remove함수 때문이다. 

remove함수는 시간복잡도 O(N)을 잡아먹는다. 그런데 이걸 for문으로 처리하고있으니 시간복잡도가 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/42577

문제설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119

박준영 : 97 674 223

지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

phone_book의 길이는 1 이상 1,000,000 이하입니다.

각 전화번호의 길이는 1 이상 20 이하입니다.

같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

입출력 예 설명

입출력 예 #1

앞에서 설명한 예와 같습니다.

입출력 예 #2

한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3

첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

문제 해결 방법

nums를 딕셔너리로 만들고, 파이썬 sort기본 정렬을 한다. 

문자열에 특정 단어가 있는지 확인하기 위해 find함수를 사용하였음

코드 구현

def solution(phone_book):
    answer = True
    dict_phone = {}
    phone_book.sort()
    
    for i in range(len(phone_book)):
        dict_phone.setdefault(phone_book[i])

    for i in range(len(phone_book)):
        if i == len(phone_book)-1:
            break
            
        if (phone_book[i+1].find(phone_book[i])) == -1:
            pass
        else:
            if (phone_book[i+1].find(phone_book[i]))==0:
                answer = False
                return answer
            else:
                pass
        
    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

처음에 while문 하나로 검색하고자 하는 단어를 카운팅 하면서 nums에 있는 모든 단어들을 for문으로 조회하도록 코드를 짰는데, 효율성에서 시간초과가 나서 while문을 없애고 반복문 한번으로 조회할수 있게 해야했다. 

그렇게 하기위해서 파이썬 sort기본 정렬을 사용하였다.

어려웠던 점 및 느낀점

문자열을 sort했을때 맨 앞에 문자일수록 가중치가 높아지고 만약 같은 가중치 선에서 우위를 가릴 수 없다면 그 다음 번호로 넘어가서 우위를 가린다. 나는 sort를 활용할 줄 몰랐다. 그리고 미리 sort를 하는게 이렇게 코드 효율성에 도움이 될줄 몰랐다. 

파이썬 자료형 set에 대해서도 알게되었다. 

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

문제설명

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서N/2마리를 가져가도 좋다고 했습니다.

홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

첫 번째(3번), 두 번째(1번) 폰켓몬을 선택

첫 번째(3번), 세 번째(2번) 폰켓몬을 선택

첫 번째(3번), 네 번째(3번) 폰켓몬을 선택

두 번째(1번), 세 번째(2번) 폰켓몬을 선택

두 번째(1번), 네 번째(3번) 폰켓몬을 선택

세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.

당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.

nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.

폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.

가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

문제 해결 방법

리스트를 해시로 변경하여 문제를 해결하였습니다.

코드 주석을 참고하세요.

코드 구현

def solution(nums):
    answer = 0
    # 총 포켓몬 중에서 N은 데려가도 되는 포켓몬 수임
    N = len(nums) // 2
    
    # 포켓몬 담을 딕셔너리
    # 딕셔너리 key를 nums 값이 중복되지 않게 채우고 value는 0으로 초기화함
    x={}
    for i in range(len(nums)):
        x[nums[i]]= 0
    # 포켓몬 종류대로 수를 세어서 value에 포켓몬 수 만큼 매김
    for i in range(len(nums)):
        tmp = x[nums[i]]
        tmp +=1
        x.update({nums[i] : tmp})
    
    # 포켓몬 종류 수가 포켓몬 잡을 수 있는 수 보다 크거나 같으면 
    # 포켓몬 잡을 수 있는 수를 반환
    if len(x) >= N:
        answer = N
    else:
    # 포켓몬 종류가 포켓몬 잡을 수 있는 수 보다 작으면 
    # 포켓몬 종류 수 반환 
        answer = len(x)
        
    return answer

시간/공간 복잡도

O(n)

최적화 및 개선

하지않음 

어려웠던 점

아직 파이썬 딕셔너리 문법에 익숙하지 않아서 헤멘다.
변수.update({바꾸고싶은 key: 바꾸고 싶은 value})

그리고 내가 변수 이름을 정할 때 너무 생각나는대로 막 정해서 그런지 스스로도 코드 짜면서 헷갈린다....

다음부터는 이런 점을 고쳐나가야겠다. 

문제설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

completion의 길이는 participant의 길이보다 1 작습니다.

참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

참가자 중에는 동명이인이 있을 수 있습니다.

문제 해결 방법

코드를 참고하세요.

코드 구현

def solution(participant, completion):
    answer = ''
    # 참가자들이 완주자들에 들어있는지 조회
    x={}
    y={}
    # 딕셔너리를 key에 participant가 들어가도록 만들고 value값을 0으로 초기화한다.
    for i in range(len(participant)):
        x[participant[i]] = 0
        y[participant[i]] = 0
    # x딕셔너리에는 완주한 사람들의 수를 체크하고 
    for i in range(len(completion)):
        if completion[i] in x:
            x[completion[i]]+=1
    # y딕셔너리에는 참여한 사람들의 수를 체크한다. 
    for i in range(len(participant)):
        if participant[i] in y:
            y[participant[i]]+=1
    # x, y딕셔너리의 value값을 비교한 후 차이가 있는 key값을 answer을 통해 출력한다. 
    for i  in range(len(participant)):
        if x.get(participant[i]) == y.get(participant[i]):
            pass
        else:
            answer = participant[i]
            return answer
            
    return answer

시간/공간 복잡도

O(n)

최적화 및 개선

하지않음 

어려웠던 점

딕셔너리 문법을 잘 몰라서 해멧다,, 

해시가 딕셔너리인줄 처음 알았다;;

역시 아는만큼 보인다,,, 

https://school.programmers.co.kr/learn/courses/30/lessons/12981?language=python3

문제설명

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.

마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.

앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.

이전에 등장했던 단어는 사용할 수 없습니다.

한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

tank → kick → know → wheel → land → dream → mother → robot → tank

위 끝말잇기는 다음과 같이 진행됩니다.

1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.

2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.

3번 사람이 자신의 첫 번째 차례에 know를 말합니다.

1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.

(계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

제한 사항

끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.

words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.

단어의 길이는 2 이상 50 이하입니다.

모든 단어는 알파벳 소문자로만 이루어져 있습니다.

끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.

정답은 [ 번호, 차례 ] 형태로 return 해주세요.

만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

문제 해결 방법

문제를 풀기위한 조건들을 하나하나 생각해서 하나하나 제외해가면서 풀었음

코드 구현

def solution(n, words):
    answer = []
    # 1번부터 마지막 순서까지 돌고돈다.
    # 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야한다. 
    # 이전에 등장했던 단어는 사용할 수 없다. 
    # 한 글자 단어 인정안해줌
    newWords=[] #스택에 쌓음
    newWords.append(words[0]) 
    
    cnt = 1 #words에서 어디를 가리키는지 
    big_phase=0
    check = 0
    check2 = 0
    while 1:
        big_phase+=1
        for i in range(1, n+1):
            if check ==1:
                answer.append(i)
                answer.append(big_phase)
                return answer
            
            if check2 == 1:
                answer.append(i)
                answer.append(big_phase)
                return answer
            
            if cnt == len(words):
                break
            
            if words[cnt][0] == newWords[-1][-1]:
                pass
            else:
                check = 1
                
            
            if words[cnt] in newWords:
                check2 = 1
            else:
                newWords.append(words[cnt])  
                cnt+=1
                
        if cnt == len(words):
                break

    answer.append(0)
    answer.append(0)
    
    return answer

시간/공간 복잡도

O(n)

최적화 및 개선

최적화 및 개선하지 않음

어려웠던 점

이렇게 푸는게 맞나 싶다.

아직까지 반복문을 잘 요령껏 못 다루는 것 같다. 

index를 +1 해서 억지로 넘겨서 출력하면 문제가 해결되지 않고

index가 문제 그대로 로직대로 넘어가도록 하는 상황을 유지하면서, 내가 원하는 값을 도출하는것이 어려웠다. 

이렇게 값을 도출하기 위해서는 무조건 다음으로 넘어간 후에 결과를 내야 하는데, 그렇게 하기 위해서 check 라는 변수를 두개 썼다. 

이게 맞나? 나중에 가서 조건이 엄청 많이 달린 문제를 다룰때는 저런 변수들로 문제를 해결 할 수 있을지 잘 모르겠다. 

문제설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.

Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

scoville의 길이는 2 이상 1,000,000 이하입니다.

K는 0 이상 1,000,000,000 이하입니다.

scoville의 원소는 각각 0 이상 1,000,000 이하입니다.

모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

입출력 예 설명

1.

스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.

새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5

가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

 2.

스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.

새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13

가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

문제 해결 방법

heapq 모듈을 사용하여 해결하였다. 

코드 구현

import heapq

def solution(scoville, K):
    answer = 0
    
    # 섞은 음식의 스코빌 지수는 newFood 변수로 표시 
    # 최소 값을 빠르게 찾기 위해서 힙을 쓰는듯 !!
    heapq.heapify(scoville)
    
    cnt = 0 
    #cnt는 음식 섞은 횟수 
    while 1:
        if scoville[0] >= K:
            answer  = cnt
            break
        
        if len(scoville) == 1:
            answer = -1
            break
    
        #print(heapq.nsmallest(2, scoville))
        #result = heapq.nsmallest(2, scoville)
        # 위에 두줄은 시행착오의 흔적이라 놔둠
        
        one = heapq.heappop(scoville)
        two = heapq.heappop(scoville)
        newFood = one + (two * 2)
        heapq.heappush(scoville, newFood)

        cnt +=1
    
    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

처음에 scoville의 최소값을 구할 때 heapq.nsmallest함수를 사용해서 구했더니 시간 복잡도가 많이 잡아먹어서 채점 항목은 효율점에서 점수를 다 깎아먹었다. 

찾아보니까 heapq.nsmallest와 같은 함수는 최소값을 찾을 때 정렬을 한번 해서 그런가 O(n log n)의 시간복잡도를 초래한다. 그래서 해당 함수를 사용하지 않고 어떻게하면 최소값을 찾아서 사용할까 했는데 heappop함수를 활용하면 될 일이였다. 

어려웠던 점

없음 !

문제설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

"()()" 또는 "(())()" 는 올바른 괄호입니다.

")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

문자열 s의 길이 : 100,000 이하의 자연수

문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

입출력 예

입출력 예 설명

입출력 예 #1,2,3,4

문제의 예시와 같습니다.

문제 해결 방법

예시를 찬찬히 살펴보자. 

'('를 괄호가 열렸다고 표현하고, ')'를 괄호가 닫혔다고 표현하겠다. 

괄호가 열려있을 때, 괄호가 열릴수 있음 

괄호가 열려있을 때, 괄호가 닫힐 수 있음

괄호가 닫혔을 때 괄호를 열든 다시 닫든 할 수 있지만, 괄호가 닫히는것 부터 시작하면 안됨

이건 완전히 스택이다. 

괄호가 열려있다는 것을 push, 닫힌다는 것을 pop으로 표현한다고 했을 때 위에 있는 말에 대입 해보자. 

push할 때, push할 수 있음 

push할 때, pop할 수 있음

pop후에 push든 pop이든 할 수 있지만, pop부터 시작하면 안됨

이건 완전히 스택이다. 

pop부터 시작하면 안되는 이유는 스택에서, 스택이 비었을때 pop을 하면 더이상 pop할 게 없어서 따로 처리를 안해주면 오류가 생긴다. 

s에 대한 조회가 끝났을 때 stack에 뭔가 남아있으면 false이다. 

그런데 스택이 비었는데 )가 나오는 경우가 있을 수 있으니, 그럴때는 스택에 뭔가 남아있어서 False하는 경우와 구분하기 위해서 realF라는 변수에 0, 1을 넣어서 체크했다. 

코드 구현

def solution(s):
    answer = True
    
# (는 스택에서 push역할을 하고  )는 pop역할을 함 
# 스택이 빈 채로 끝나지 않으면 false임 

    stack = []
    realF= 0
    for i in range(len(s)):
        if s[i] =='(':
            stack.append(1)
        else:
            if len(stack)<1:
                answer= False
                realF = 1
                break
            else:
                stack.pop()
    
    if stack or realF == 1:
        answer = False
    else:
        answer = True
    
    return answer

시간/공간 복잡도

최악의 경우 n 임 

최적화 및 개선

어디를 최적화 해야하는지 잘 모르겠다! 

어려웠던 점

없었다 ^__^