개발자 아지트

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 라는 변수를 두개 썼다. 

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

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

문제설명

0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.

x의 모든 0을 제거합니다.

x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다.

예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.

0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

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

s에는 '1'이 최소 하나 이상 포함되어 있습니다.

문제 해결 방법

반복문을 통해 구현하였다. 

코드 구현

def solution(s):
    answer = []
    cnt = 0
    total_zero = 0
    while(1):
        if s=='1':
            break

        one_cnt = s.count('1')
        zero_cnt = s.count('0')
        total_zero += zero_cnt
        result = ''
        for i in range(one_cnt):
            result +='1'

        s=len(result)

        s = format(s, 'b')
        cnt+=1

    answer.append(cnt)
    answer.append(total_zero)
    
    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

하지않음

어려웠던 점

없음

문제설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.

1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.

2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

array의 길이는 1 이상 100 이하입니다.

array의 각 원소는 1 이상 100 이하입니다.

commands의 길이는 1 이상 50 이하입니다.

commands의 각 원소는 길이가 3입니다.

입출력 예

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.

[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.

[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

문제 해결 방법

파이썬 슬라이스 활용

코드 구현

def solution(array, commands):
    answer = []
    newArray = []
    for i in range(len(commands)):
        start = commands[i][0]-1
        end = commands[i][1]
        newArray = array[start:end]
        newArray.sort()
        answer.append(newArray[commands[i][2]-1])
        newArray = []
    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

하지않음 

어려웠던 점

문제를 잘 읽고 풀자,,, 

문제설명

매운 것을 좋아하는 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함수를 활용하면 될 일이였다. 

어려웠던 점

없음 !

문제설명

운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.

2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.

3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.

  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.

현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.

제한사항

priorities의 길이는 1 이상 100 이하입니다.

priorities의 원소는 1 이상 9 이하의 정수입니다.

priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다.

location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.

priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.

입출력 예

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2

6개의 프로세스 [A, B, C, D, E, F]가 대기 큐에 있고 중요도가 [1, 1, 9, 1, 1, 1] 이므로 [C, D, E, F, A, B] 순으로 실행됩니다. 따라서 A는 5번째로 실행됩니다.

문제 해결 방법

문제 해결 방법은 코드 주석에 녹였다. 

코드 구현

def solution(priorities, location):
    answer = 0
    
    # 우선 순위대로 몇번이 먼저 실행될지는 priority Queue로 매김 - 1번 llist 리스트 생성
    
    # location을 통해 초기의 priorities list에서 해당 자리의 원소 찾기 -> 출력
    
    llist=[]
    max_qsize = len(priorities)
    
    for i in range(max_qsize):
        llist.append(0)
    
    # 큐 전체에서 우선순위 젤 높은걸 찾아서 위치를 기록 후 삭제함. 단, front랑 rear 움직이지 않음
    # 큐 전체에서 우선순위 젤 높은걸 원소 값을 찾아서 해당 원소값을 아까전에 위치 기록한 지점부터 찾아서 순위 매김 
    
    # 원소가 뽑혔으면 priorities의 원소는 0으로 변경
    
    cnt = 1
    
    while 1:
        if cnt-1 == len(priorities):
            break
        
        if cnt == 1:
        	# king은 priorities에서 가장 큰 값이다 (우선순위 최고)
            king = max(priorities)
            # king의 위치 확인 
            # cnt가 1일 때는 이렇게 진행 
            front = priorities.index(king)
            llist[front] = cnt # 1 = cnt, 루프를 돌 때 마다 1씩 증가함
            priorities[front] = 0 
            front+=1
            cnt+=1
            if front == max_qsize:
                    front = 0
        else:
            # cnt가 2 이상이면 아래의 로직을 진행
            king = max(priorities)
            if priorities[front] == king :
                llist[front] = cnt
                priorities[front] = 0
                front+=1
                cnt+=1
                if front == max_qsize:
                    front=0
            else:
                front+=1
                if front == max_qsize:
                    front = 0
                
    answer = llist[location]
        
    return answer

시간/공간 복잡도

O(N)이 되겠다. 

최적화 및 개선

하지않음

어려웠던 점

이 문제를 풀면서 배열이나 리스트가 선형인게 아니라 원형이였으면 참 좋겠다 이런 생각을 계속 했었다. 

생각만 하고 구현할 줄을 몰랐다. 

그래서 '원형큐' 라는 말을 예전에 어디서 들어본거 같아서 찾아봤다. 

내가 구현할 문제는 이렇게까지 구현할 필요는 없을것 같은데,,, 

그냥 리스트를 원형으로만 만드는게 필요했기 때문이다. 

게다가 priorities의 원소도 1부터 9까지라 빼고 넣고 할 필요도 없고 해서도 안됐다.

0으로 이미 우선순위를 기록한 수 임을 표시할 수 있었다. 

원형큐 개념을 살펴보다가 내가 어떤 원소를 가리키고 있는지에 대한 변수를 만들고 

그 변수가 해당 리스트를 순환하며 조회하게끔 구현하기만 하면 됐었다. 

근데 그게 어려웠는데 해보니까 별거아니네 ㅠ;;

왜 레벨 2 문제인지 이제 알 것 같다.

괜히 쫄았다. 쫄면 더 간단히 생각할 수 있는것도 어렵게 생각하는것 같다. 

쫄지마!!!!!

문제설명

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

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

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

'(' 또는 ')' 로만 이루어진 문자열 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 임 

최적화 및 개선

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

어려웠던 점

없었다 ^__^

오늘도 굉장히 기분이 좋다 이말씀입니다.!!!!!

(조금 애는 먹었지만)

문제설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.

작업 진도는 100 미만의 자연수입니다.

작업 속도는 100 이하의 자연수입니다.

배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

입출력 예 설명

입출력 예 #1

첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.

두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.

세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

입출력 예 #2

모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.

문제 해결 방법

나는 우선 이 문제는 리스트를 잘 다뤄야 잘 풀수 있는 문제라고 생각한다. 

1. 우선 하루하루 가는 날 수를 기준으로 진도가 먼저 끝나는 순으로 리스트를 하나 만들었다. 

리스트에 들어갈 때는 최초 진도가 아닌 진도를 끝냈을 때의 날 수가 들어가도록 했다. 

2. 최초의 progresses의 리스트 형태로 날 수를 매기면 하나의 리스트가 나온다.

이렇게 리스트 1, 2가 나온다. 

가장 빠르게 끝나는게 아닌, 먼저 배포되어야 하는 순서대로  배포가 되어야 하기 때문에 

리스트 2의 첫번째 원소로 리스트 2의 모든 원소를 빼면 음의 정수, 0, 양의 정수가 나오는데 이때 0번부터 조회하기 시작해서 음의 정수와 0이 나오면 카운트를 하고, 양수를 만나면 카운트를 그만두고 answer리스트에 그동안 쌓았던 카운트를 넣고 카운트는 초기화 해준다. 아참 초기화 전에 리스트 2에는 카운트 만큼 popleft해준다.   이를 리스트 2의 크기가 0이 될때 까지 반복해준다.  

코드 구현

from collections import deque

def solution(progresses, speeds):
    answer = []
    #큐 만들기
    days = deque()
    finall = deque()

    # 날짜 카운트는 while문으로 진행
        # progresses에 대한 모든 값을 for문 i로 조회 할 때 
        # speeds도 같이 조회해서 각각에 각각 speeds를 +함
    #days 리스트 만들어줌 
    for i in range(len(progresses)):
        days.append(0)
        
    while 1:
        if len(finall) == len(progresses):
            break
        
        #progresses를 speed만큼 계산함 
        for j in range(len(progresses)):
            if progresses[j]<100:
                progresses[j] = progresses[j] + speeds[j]
                days[j] = days[j] + 1
                if progresses[j]>=100:
                    finall.append(days[j])

    cnt = 0
    while 1 :    
        minus=days[0]
        for i in range(len(days)):
            days[i] = days[i]-minus
            
        for i in range(len(days)):
            if days[i]<=0:
                cnt+=1
                if i==len(days)-1:
                    answer.append(cnt)
                    break
            else:
                answer.append(cnt)
                break
                
        for i in range(cnt):
            days.popleft()
            
        cnt=0
        
        if len(days)==0:
            break

    return answer

시간/공간 복잡도

for문의 반복 횟수는 n에 비례하고 while문의 반복 횟수는 logn에 비례한다.

for문이 while문에 중첩되어 있기 때문에 시간 복잡도는 O(nlgn)입니다.

for문이 while문 안에 중첩

def print_powers_of_two_repeatedly(n):
    i = 1
    while i < n: 
        for j in range(n):
            print(i, j)
        i = i * 2

(출처 - https://velog.io/@tataki26/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%8F%89%EA%B0%80%EB%B2%95-2)

따라서 해당 문제도 시간복잡도는 O(nlogn)이 되겠다.  

최적화 및 개선

아 처음에는 스택인가 싶어서 스택으로 구현했는데 이게 가만보니 큐로 구현해야할 로직이였다. 

사용하는 알고리즘 개선하니 해결점이 보였다.

그 외에 따로 최적화 하지 않음. 

어려웠던 점

스택과 큐의 차이를 직접적으로 알 수 있었던 문제였다. 

맞다고 생각했던 다 짜놓은 로직을 새로 고치기가 싫었지만 맞추기 위해서는 꼭 해야 했다.