미정

문제 설명

나의 풀이

def solution(progresses, speeds):
    answer = []
    while progresses:
        for i in range(len(progresses)):
            progresses[i] += speeds[i]
        count = 0
        while progresses and progresses[0] >= 100:
            progresses.pop(0)
            speeds.pop(0)
            count += 1
        if count >0:
            answer.append(count)
    return answer

• progresses에 speeds를 더할 때마다 100이 넘는지 않은지를 확인한다. 반복문을 통해 모든 작업이 완료될 때까지 작업을 한다.
• progresses 순서대로 배포하기 때문에 첫 번째 요소들부터 100이 넘었다면 pop으로 progresses 배열에서 제거하고 count 를 1 늘린다.
• 이 방법을 계속 반복하여 앞에서부터 100이 넘는 요소들을 빼주는데, 이러다가 100이 넘지 않은 요소가 나타나면 반복을 멈추고, count가 0이 아니고 존재한다면 answer에 append 해준다.
• progresses가 없을 때까지 반복한다.
• 모든 작업이 완료했다면 answer를 출력한다.

스택과 큐에 대한 어느정도 지식이 있어야 한다.

쉽게 그림으로 이해해보면,

큐를 사용한 문제 해결 과정

                 progresses                                     speeds                                      return

progresses[i] += speeds[i] 반복

맨 앞 작업이 100 미만 - > 모든  작업 속도 업데이트(현재 결과 리스트 : [ ])

맨 앞 작업이 100 미만 - > 모든 작업 속도 업데이트(현재 결과 리스트 : [ ])

맨 앞 작업이 100 미만 - > 모든 작업 속도 업데이트(현재 결과 리스트 : [ ])

맨 앞 작업이 100 미만 - > 모든 작업 속도 업데이트(현재 결과 리스트 : [ ])

맨 앞 작업이 100 미만 - > 모든 작업 속도 업데이트(현재 결과 리스트 : [ ])

맨 앞 작업이 100 미만 - > 작업 속도 업데이트(현재 결과 리스트 : [ ])

!!!! 맨 앞 작업이 100 이상 - > 해당 기능 배포 , 큐에서 제거, 배포된 기능 개수 1 증가

!!!!! 맨 앞 작업이 100 이상 - > 해당 기능 배포 , 큐에서 제거, 배포된 기능 개수 1 증가

오늘 배포 가능한 기능 더 이상 없음 결과 리스트에 배포된 기능 개수 추가 (현재 결과 리스트 : [2])

맨 앞 작업이 100 미만 - > 반복문 빠져나와서 progresses[i] += speeds[i] 실행

맨 앞 작업이 100 이상 - > 해당 기능 배포 , 큐에서 제거, 배포된 기능 개수 1 증가

오늘 배포 가능한 기능 더 이상 없음 결과 리스트에 배포된 기능 개수 추가 (현재 결과 리스트 : [2, 1])

작업 큐에 남은 작업 없음, 반복 탈출

문제 설명

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

1. crow_mask
2. blue_sunglasses
3. smoky_makeup

나의 풀이

def solution(clothes):
    closet = {}
    answer = 1
    
    # 같은 종류의 옷끼리 묶어서 사전에 저장
    for cloth in clothes:
        if cloth[1] in closet.keys():
            closet[cloth[1]].append(cloth[0])
        else:
            closet[cloth[1]] = [cloth[0]]
    
    # 경우의 수 구하기            
    for value in closet.values():
        answer *= len(value) + 1
    
    # 아무것도 입지 않은 경우 하나 제외
    return answer-1

 ex) output: {'headgear': ['yellow_hat', 'green_turban'], 'eyewear': ['blue_sunglasses']}
     # 위와 같이 딕셔너리가 만들어진다.

•  마지막에 1을 빼주는 이유는 모두 안입은 경우를 제거한다.
• 정리하면 가능한 조합의 수는 headgear 를 두 가지중에 한가지를 입거나 혹은 둘 다 안입거나 (총 세가지)
• 그리고 eyewear 는 한 가지이므로 입거나 혹은 안입거나 (총 두가지)
• 그리고 이것들을 종류를 바꿔서 돌려입기 가능하므로, 조합의 수는 3 * 2 가 된다
• 그러나 모든 종류의 옷을 다 안입은 경우에는, 위장을 한 것이 아니므로 이 경우의 수만 빼주면 된다.

def solution(clothes):
    answer = 1
    dic = {}
    for i in clothes:
        if i[1] in dic:
            dic[i[1]] += 1
        else:
            dic[i[1]] = 1
    for i in dic.keys():
        answer *= dic[i] +1
    answer -= 1

풀이는 똑같은데 이게 더 간단한 느낌..!

문제 설명

나의 풀이

def solution(people, limit):

    people.sort()
    # 시작, 끝 인덱스
    start, end = 0, len(people)-1
    # 보트의 수
    count = 0
    while start <= end:
        # 보트의 수 증가
        count += 1
# 두 명(몸무게가 가장 적은 사람, 몸무게가 가장 많은 사람)을 태우거나
        if (people[start] + people[end] <= limit):
            start += 1
            end -= 1

# 한 명(몸무게가 가장 많은 사람)을 태우기 
        else:
            end -= 1
    return count

1. 핵심은 가장 몸무게가 많이 나가는 사람과 적게 나가는 사람을 계속해서 매칭시켜서 최대한 한번에 태워보내주면 최소값을 찾아줄 수 있다.
2. 먼저 people의 list를 정렬을 해주어야한다. 이후 가장 몸무게가 큰 사람과 가장 작은 사람의 무게를 더해 limit와 비교한 뒤, 작으면 둘다 태우고(두 명(몸무게가 가장 적은 사람, 몸무게가 가장 많은 사람)을 태우거나), 크다면 몸무게가 가장 큰 사람만 태운다.(한 명(몸무게가 가장 많은 사람)을 태운다.)

투 포인토 알고리즘을 사용해 풀어 보았다.

Greedy (탐욕법, 탐욕 알고리즘)

Greedy Algorithm은 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다.

위의 그림에서는 가장 숫자가 큰 요소를 찾는데 있어서 해당 분기점마다 보다 큰 수를 찾는 방식으로 최종 해답을 찾아가고 있다. 순간마다 큰 수를 찾아가면 최종 결과는 12이다. 하지만 실제 전체 숫자 중에서 가장 큰 수는 99이다. 이처럼 전체 문제해결에서의 최적 해답을 찾지는 못한다.

하지만 이러한 단점들을 극복하는 Greedy의 가장 큰 장점은 계산 속도에 있다. 그래서 Greedy 방법이 통하는 몇몇의 문제에서는 최적해를 빠르게 산출해낼 수 있다.

투 포인터 (Two Pointer)

• 배열 안에 있는 값들을 연속해서 더하거나 연산하는 경우에 사용 인덱스를 가리키는 두 개의 변수(포인터)를 선언하여 사용하는 특징이 있어 투 포인터라 불림
• 예를 들어 N개의 숫자가 들어있는 배열이 주어질 때, 부분 집합의 합이 특정 숫자인 M인 경우의 수를 구하는 문제에 적용한다면, 배열의 인덱스를 가리키는 startPointer와 endPointer를 생성한 후 특정 규칙에 의해 각 포인터를 움직여 배열을 탐색해 문제를 해결할 수 있으며, 그 규칙은 다음과 같습니다.1-2) 만약 startPointer의 값이 배열의 길이와 같을 경우 탐색을 종료합니다.2) 위의 세 규칙 중 해당하는 연산이 끝난 후 만약 현재까지의 합이 M과 같다면 답을 +1증가 시킵니다.
• 1-3) 나머지 경우(현재까지의 합이 M보다 작을 경우)에는 합에 startPointer가 가리키고 있는 값을 더한 후 startPointer를 +1 증가시킵니다.
• 1-1) 현재까지의 합이 M보다 크거나 같은 경우 합에서 endPoiner가 가리키고 있는 값을 뺀 후 endPointer를 +1 증가시킵니다.
• 투 포인터를 사용한다면 한 번 답이 될 수 없다고 판명된 이후의 값들을 더 이상 탐색하지 않으므로 시간 복잡도가 O(n)이 되어 완전 탐색에 비해 효율이 훨씬 좋음

문제 설명

문제를 풀기에 앞서,

citations = [6,6,6,6,6,1] 일 때, 이 과학자의 H-index는?

이 질문을 풀어보자. 답은 5이다.
이 예시를 든 이유는 일부 사람들이 h 값을 citaions 리스트 안에 있는 값 중에서 고르려고 하기 때문이다. 
즉, 우리는 H-index의 최댓값과 리스트의 길이의 관계를 고려해서 풀어야 한다.

나의 풀이

def solution(citations):
    citations.sort()
    article_count = len(citations) # 5

    for i in range(article_count): #0~4
        if citations[i] >= article_count-i:
            return article_count-i
    return 0

• if citations[i] >= article_count-i는 "주어진 h번 이상 인용된 논문이 h편 이상"이라는 조건을 그대로 풀어쓴 것이었다.
• citations[i]는 i번 논문이 인용된 횟수이고 article_count - i는 인용된 논문의 개수를 최댓값부터 하나씩 줄여나간 것이다. (최댓값을 찾아야 하므로 가장 큰 값부터 시작)
• 정렬된 citations에서 한칸씩 가다가 그 값이 나머지 길이보다 크거나 같다면 그 편수가 h다.
• 그리고 리스트는 오름차순 정렬된 상태이므로 i번째 이후는 모두 i번째보다 큰 값을 가질 것이다.

 
https://www.ibric.org/myboard/read.php?Board=news&id=270333

신박한 풀이

def solution(citations):
    citations.sort(reverse=True)
    answer = max(map(min, enumerate(citations, start=1)))
    return answer

문제 설명

문제를 풀기전, 최소공배수를 구하는 방법에 대해 알아보자.

간단한 예로 최소공배수를 구해보자.

def ex_gcd(a, b): 	# a=18, b=24라고 가정
    A = a
    B = b
    while b > 0:
        a , b = b, a % b
    gcd = a 	# 최대공약수
    return A*B // gcd

위의 예시는 최소공배수를 구하는 문제이다. 18과 24의 최소공배수를 구해보자.

밑의 그림과 같이 구하면 되고, 최소공배수는? 2*3*3*4를 해서 72가 나올 것이다.

또 하나, 최대공약수는 6이 나올 것이다.

규칙을 찾았는가?

바로 최소공배수는 최소공배수를 구할 두 수를 서로 곱하여 최대공약수로 나누면 최소공배수가 된다는 것이다.

즉, 18 과 24를 서로 곱하여 나온 수를 최대공약수(6)로 나누면 최소공배수(72)가 나온다.

본 문제에 대한 나의 풀이

def solution(arr):
    from math import gcd                           
    answer = arr[0]                                 
    for num in arr:                                
        answer = answer*num // gcd(answer, num)     
    return answer

1.  최대공약수를 구하는 gcd() 함수를 import 한다. ((gcd() 함수는 두 수의 최대공약수를 구해주는 함수))

2. answer을 arr[0]으로 초기화

3. 반복문을 처음부터 끝까지 돈다.

4. arr[0], arr[1])의 최소공배수를 구한 후 answer에 저장

5. 4번에서 구한 최소공배수, arr[2])의 최소공배수를 구한 후 answer에 저장

6. 모든 배열을 돌면서 최소공배수를 구하고, 저장하고 하는 방식을 진행 ((최소공배수 = (x*y) / gcd(x,y))

정리하자면 이렇다.

• 최소공배수를 계속해서 answer에 저장시켜 answer와 arr[index]를 통해 계속해서 최소공배수를 구해야 함
• gcd() 함수는 두 수의 최대공약수를 구해주는 함수
• // 연산자는 몫만 구하는 연산자

문제 설명

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

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

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

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예brownyellowreturn

10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

풀이

def solution(brown, yellow):

    answer = []
    yellow_x = 0
    yellow_y = 0
    for i in range(1, yellow+1) :
        if yellow % i == 0 :
            yellow_x = int(yellow/i)
            yellow_y = i
            if yellow_x*2 + yellow_y*2 + 4 == brown :            
                answer.append(yellow_x+2)
                answer.append(yellow_y+2) 
                return sorted(answer, reverse = True)
    return answer

노란 격자의 가로(yellow_x)와 세로(yellow_y)를 이용해서 위와 같은 코드로 해결할 수 있다.

1부터 노란색의 개수만큼 for문으로 반복하면서 노란색의 수가 i로 나누어 떨어지면 노란색의 가로는 노란색을 i로 나눈 몫이되고, i는 노란색의 세로가 된다.

이때 위에서 언급한 수식을 사용하여 answer 리스트에 yellow_x+2와 yellow_y+2를 넣어준다.

가로가 세로보다 크거나 같아야 하기 때문에 내림차순으로 정렬을 한 리스트가 반환되도록 했다.

다른사람 풀이

def solution(brown, yellow):
    n = (brown-4)//2
    for i in range(n):
        x, y = i, n-i
        if x*y == yellow:
            return [y+2, x+2]

갈색 공간의 4개의 꼭짓점을 빼고 반으로 나누면, 노란색 구역의 가로+세로가 나오게 되며, for문을 돌면서 가로 * 세로가 노란색이 될 때, 가로+2, 세로+2 가 정답이 된다.

def solution(brown, yellow):
    total = brown + yellow
    # 카펫의 가로길이가 세로길이보다 크거나 같기 때문에 큰수에서 작은수로 반복
    for weight in range(total, 2, -1):
        if total % weight == 0: # 카펫넓이에서 가로길이 탐색
            height = total // weight # 카펫넓이 / 가로길이를 통해 세로길이 탐색
            # 구해진 카펫의 길이에서 테두리길이(2)만큼 빼주고 면적을 구한뒤 yellow의 면적과 같다면 해당 값 return
            if yellow == (weight-2) * (height-2):
                return [weight, height]

카펫의 넓이 = brown + yellow = width x height
외부 사각형 갯수(brown) = 2w + 2h + 4
내부 사각형 갯수(yellow) = (x-2) * (y-2)

문제 설명

풀이

def solution(n, words):
    rs=[] # 나온 단어 확인할 리스트
    for i in words:
        if i in rs: #같은 단어를 말했을때
            break
        if len(rs)!=0 and (rs[-1][-1]!=i[0]): # 앞단어의 뒷부분과 일치하지 않은 단어를 말했을때
            break
        rs.append(i)
        
    if len(rs)==len(words): # 문제없이 진행됐을시
        return [0,0]
    return [(len(rs)%n)+1, (len(rs)//n)+1]

1. word를 저장할 rs을 생성한다. rs는 나온 단어를 확인할 리스트이다.

2. words를 탐색하며 현재 word가 rs에 없고, rs의 마지막 원소의 마지막 문자가 현재 word의 첫번째 문자와 같다면 rs에 추가한다.

3. 위 조건에 맞지 않는다면 잘못된 단어이므로, 현재 word의 인덱스를 사용하여 탈락자 번호와 순서를 알아낸다.

result[0] = (len(rs) % n) + 1

result[1] = (len(rs) // n + 1

위 코드를 짧게 줄여보았다.

def solution(n, words):
    for i in range(1,len(words)):
        if words[i] in words[:i] or words[i][0]!=words[i-1][-1]:
            return [(i%n)+1,(i//n)+1]
    return [0,0]

• return 값은 >> 번호 = (i%n)+1, 차례 = (i//n)+1 << 이다.
• 비교를 할 때 words[i][0] != words[i-1][-1] 을 하기 때문에 반복문 범위는 1~len(words)로 해야한다.(0~len(words)로 하면 안 됨)

다른 사람의 풀이

def solution(n, words):
    answer = [0,0]

    cnt = 0  # 탈락번호,차례 계산할 변수
    checks = []  # 나온 단어 확인할 리스트
    checks.append(words[0])
    for i in range(1, len(words)):  # 단어 순회하면서
        cnt += 1
        # 아직 안나온 단어이면서 & 앞 단어의 마지막 알파벳과 일치하면 checks 리스트에 넣음 (pass)
        if words[i] not in checks and list(words[i-1])[-1] == list(words[i])[0]:
            checks.append(words[i])
        else:  # (fail)
            answer[0] = cnt%n +1  # 탈락번호
            answer[1] = cnt//n +1  # 탈락차례
            break

    return answer

Python의 if in 문법

문제가 좀 길어서 당황 했지만, 의외로 이런 문제가 더 쉬운 경향이 있다.

문제 설명

나의 풀이

def solution(s):
    answer = 0
    s = list(s)
    stack = []
    for i in s:
        if len(stack) == 0:
            stack.append(i)
        elif i == stack[-1]:
            stack.pop()
        else:
            stack.append(i)

    if len(stack) == 0:
        return 1  
    else:
        return 0

두 가지를 비교해서 같으면 pop, 아니면 남긴다는 말에 stack이 생각났다.

1. stack을 활용할 것. 이 문제는 스택을 이용해서 풀었다.
2. s에 들어있는 문자를 하나씩 뽑아 스택에 있는 문자랑 비교하고
3. 만약 같다면 스택에 있는 문자 pop
4. 만약 다르다면 s에 들어있는 문자를 스택에 넣기

stack을 사용하지 않고 while, for문으로 앞 뒤 값을 비교 후 replace() 함수를 사용하는 방식으로 처음에 풀었는데, 시간 초과문제가 발생한다. 문자열 길이가 1,000,000이하이기 때문에 너무 큰 배열이 들어온다면 그럴 수 밖에 없을 것이라고 생각되었다. 그러다 stack이 생각이 났고, stack을 활용해 쉽게 문제를 해결할 수 있었다.