IT-garden

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한조건

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

입출력 예

나의 풀이

def solution(people, limit):
    people.sort()
    f=0
    a=[False]*len(people)
    b=len(people)-1
    c=0
    
    while f < b:
        if people[f] + people[b] <= limit:
            a[f]=True
            a[b]=True
            c += 1
            f += 1
        b -= 1

    return c+a.count(False)

1. 사람들의 몸무게를 오름차순으로 정렬하고 가장 가벼운 사람과 무서운 사람부터 함께 구명보트에 탈 수 있는지 검사합니다. 구명보트를 최대한 적게 사용하기 위해서입니다.
2. 몸무게를 앞에서부터 확인하기 위한 변수 f, 몸무게를 뒤에서부터 확인하기 위한 변수 b

리스트 a는 해당 사람이 구명보트를 탔는지 확인하기 위한 리스트입니다. (True이면 탄 것, False면 타지 않은 것)

3-1. 두 몸무게를 더해 구명보트의 무게 제한보다 적다면 구명보트의 개수(c)를 1개 더하고 f는 1 더하고 b는 1 뺍니다.

3-2. 두 몸무게를 더해 구명보트의 무게 제한보다 적지 않다면 b만 1 뺍니다.

4. f가 b와 같아지거나 더 커지면 while문을 나와 구명보트의 개수와 구명보트를 타지 못한 사람의 개수를 더해 리턴합니다.

다른 사람의 풀이

def solution(people, limit) :
    answer = 0
    people.sort()

    a = 0
    b = len(people) - 1
    while a < b :
        if people[b] + people[a] <= limit :
            a += 1
            answer += 1
        b -= 1
    return len(people) - answer

풀이는 거의 흡사하나 마지막에 값을 구할 때 따로 리스트로 검사하지 않고 len(people)-answer를 썼습니다. 이렇게 하면 전체 사람에서 2명이서 탄 구명보트의 수를 빼주는 것으로 바로 답을 구할 수 있습니다.

프로그래머스 '구명보트' : https://programmers.co.kr/learn/courses/30/lessons/42885

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한조건

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

나의 풀이

def solution(numbers):
    a=list(map(str,numbers)) 
    a.sort(key=lambda x : x*3, reverse=True)
    
    if len(a) == a.count('0'):
        return '0'
    else:
        return  ''.join(a)

1. 입력받은 numbers를 문자열 형태로 바꿔 리스트 a에 저장합니다.
2. 리스트 a의 요소들을 3번씩 곱해 비교하여 내림차순으로 정렬합니다.

ex) '3' = '333', '30'='303030'

각 앞자리부터 비교하여 '3'과 '3'을 비교하여 같으니 '3'과 '0'을 비교하여 '3'이 더 크기 때문에 '333'을 큰 것으로 인식합니다.

3. 리스트 a의 모든 요소가 0일 경우 '0'을 리턴하고 그 외의 경우는 a를 하나의 문자열로 리턴합니다.

프로그래머스 '가장 큰 수' : https://programmers.co.kr/learn/courses/30/lessons/42746

문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한조건

• W, H : 1억 이하의 자연수
  
  

입출력 예

입출력 예 설명

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

나의 풀이

import math

def solution(w,h):
    if w > h:
        w, h = h, w
    
    return w*h - (h+w-math.gcd(w,h))

다른 사람의 풀이

def gcd(a,b): return b if (a==0) else gcd(b%a,a)    
def solution(w,h): return w*h-w-h+gcd(w,h)

import math 대신 직접 최대공약수 알고리즘을 만들었습니다.

프로그래머스 '멀쩡한 사각형' : https://programmers.co.kr/learn/courses/30/lessons/62048

문제 설명

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

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]

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

나의 풀이

import heapq

def solution(scoville, K):
    
    heapq.heapify(scoville)
    c = 0
    
    while True:
        if scoville[0] >= K:
            return c
        elif scoville[0] < K and len(scoville) == 1:
            return -1
        else:
            a = heapq.heappop(scoville) + ( heapq.heappop(scoville) * 2 )
            heapq.heappush(scoville, a)
            c += 1

1. heapq에서 최소힙을 이용합니다.

2. 힙의 첫번째 요소(가장 맵지 않은 스코빌 지수 요소)와 두번째요소(두번째로 맵지 않은 스코빌 지수 요소)를 이용해 새로운 음식을 만들어 힙에 넣습니다.

3. 힙의 첫번째 요소가 K보다 큰 경우 횟수를 출력합니다.

4. 힙의 요소가 1개밖에 남지 않고 첫번째 요소가 K보다 작은 경우 -1을 출력합니다.

5. 2번 과정을 반복하다 3번이나 4번을 충족할경우 해당 값을 리턴하고 종료합니다.

프로그래머스 '더 맵게' : https://programmers.co.kr/learn/courses/30/lessons/42626

문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한조건

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.
  
  

입출력 예

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

나의 풀이

def solution(citations):
    for i in range(len(citations),-1,-1):
        c=[j for j in citations if i<= j]
        if i <= len(c):
            return i

1. i보다 큰 논문의 수를 세서 개수가 i보다 많거나 같으면 i를 리턴합니다. 

다른 사람의 풀이

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

프로그래머스 'H-Index' : programmers.co.kr/learn/courses/30/lessons/42747

문제 설명

수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다.

송신 탑(높이)수신 탑(높이)

맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 return 하도록 solution 함수를 작성해주세요.

제한조건

• heights는 길이 2 이상 100 이하인 정수 배열입니다.
• 모든 탑의 높이는 1 이상 100 이하입니다.
• 신호를 수신하는 탑이 없으면 0으로 표시합니다.

입출력 예

입출력 예 설명

입출력 예 #1
앞서 설명한 예와 같습니다.

입출력 예 #2

[1,2,3] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다.
[4,5,6] 번째 탑이 쏜 신호는 3번째 탑이 수신합니다.
[7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.

입출력 예 #3

[1,2,4,5] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다.
[3] 번째 탑이 쏜 신호는 2번째 탑이 수신합니다.
[6] 번째 탑이 쏜 신호는 5번째 탑이 수신합니다.
[7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.

나의 풀이

def solution(heights):
    answer = [0] * len(heights)
    for i in range(1,len(heights)):
        for j in range(i-1,-1,-1):
            if heights[i] < heights[j]:
                answer[i] = j + 1
                break
    return answer

1. i는 쏘는 신호, j는 받는 신호
2. j가 더 클 경우 answer의 값을 바꾸고 다음으로 넘어갑니다.

프로그래머스 '탑' : https://programmers.co.kr/learn/courses/30/lessons/42588