IT-garden

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한조건

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

입출력 예 설명

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.

-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

나의 풀이

def solution(routes):
    r=0
    routes=sorted(routes)
    s=routes[0][1]
    routes=routes[1:]
    r += 1

    for i in routes:
        if i[0] <= s:
            s = min(i[1],s)
        else:
            s = i[1]
            r += 1

    return r

프로그래머스 '단속카메라' : https://programmers.co.kr/learn/courses/30/lessons/42884

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

나의 풀이

def solution(number, k):
    a=[]
    for i,v in enumerate(number):
        while a and a[-1] < v and k > 0:
            a.pop()
            k -= 1
        if k == 0:
            a += number[i:]
            break
        a.append(v)
    if k > 0:
        a=a[:-k]

    return ''.join(a)

앞에서부터 큰 숫자를 만들어야 전체적으로 큰 숫자가 될 수 있습니다.

1. 문자열 number를 검사합니다.
2. 리스트 a에 원소가 있고 리스트 a의 마지막 값이 순회하는 v보다 작고 k가 0보다 크면
리스트 a의 마지막 원소를 제거하고 k를 1 줄입니다.
3-1. k가 0이면 리스트 a에 순회하는 뒤의 원소들을 추가해 리턴합니다.
3-2. 순회하는 v를 리스트 a에 추가합니다.
4. k가 0보다 크면 리스트 a의 뒤에서부터 k개를 자릅니다.
5. 리스트 a를 리턴합니다.

프로그래머스 '큰 수 만들기' : https://programmers.co.kr/learn/courses/30/lessons/42883

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

예를 들어 아래의 방법으로 JAZ를 만들 수 있습니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한조건

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

입출력 예

나의 풀이

def solution(name):
    answer = 0
    a=[]
    for i in name:
        a.append(min(ord(i)-ord('A'),1+ord('Z')-ord(i)))    
    if 'A' not in name:
        answer = len(name)-1 + sum(a)
    i=0
    if 'A' in name:
        while True:
            answer += a[i]
            a[i]=0
            if sum(a) == 0:
                break
            left, right = (1,1)
            while a[i-left] <= 0:
                left += 1
            while a[i+right] <= 0:
                right += 1

            if left < right:
                answer += left
                i += -left
            else:
                answer += right
                i += right          
    return answer

문제는 크게 알파벳 조작, 위치 조작으로 나눌 수 있습니다.

알파벳 조작은 쉽게 구할 수 있지만 위치 조작이 어려운 문제였습니다.

gurumee92.tistory.com/182 를 참고했습니다.

프로그래머스 '조이스틱' : https://programmers.co.kr/learn/courses/30/lessons/42860

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 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

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘 

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=[]

for i in range(n):
    a.append(list(map(int,input().split())))
    
a.sort(key = lambda x: (x[1], x[0]))

c=0 # 회의 개수
t=0 # 회의실 시간

for s,e in a:
    if s >= t:
        t = e
        c += 1

print(c)

리스트 a를 끝나는 시간으로 정렬합니다.
끝나는 시간이 같을 경우 시작하는 시간 순으로 정렬합니다.

3 3
1 3
인 경우 답은 2인데 끝나는 시간으로만 정렬 해놓으면 답이 1로 나오는 것을 방지하기 위해서입니다.

리스트 a에서 처음부터 검사해서 시작시간이 t보다 작거나 같으면 해당 시간에 회의실을 사용한다 생각하고 c를 더해주고 t를 e로 바꿉니다.

백준 알고리즘 1931번 : www.acmicpc.net/problem/1931

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘
힙

정답

import heapq
import sys
input = lambda : sys.stdin.readline().strip()

n,k=map(int,input().split())

a=[]

for i in range(n):
    m,v=map(int,input().split())
    heapq.heappush(a, [m,v])

b=[int(input()) for i in range(k)]
b.sort()

c=0
p=[]

for i in range(k):
    capa=b[i] # 현재 가방에 담을 수 있는 무게

    while a and capa >= a[0][0]: # 가방에 담을 수 있는 a에 있는 모든 보석
        [m,v]=heapq.heappop(a) 
        heapq.heappush(p, -v) # 값을 -로 넣기, 최대힙 만들기 

    if p: # 넣을 수 있는 보석이 있는 경우
        c -= heapq.heappop(p)
    elif not a: # 가방에 넣을 수 있는 보석이 없는 경우
        break

print(c)

heapq이용 : heapq는 이진 트리의 최소힙 자료구조 제공합니다.

**백준에서 import queue가 안되서 PriorityQueue를 사용하면 런타임 에러가 납니다.

1. 각 보석의 정보 m과 v를 heapq에 담습니다. 이진 트리는 m이 작은 것부터 최소힙으로 구성됩니다.
2. 가방에 담을 수 있는 최대 무게들을 입력받아 오름차순으로 정렬합니다.
3. 각 가방에 대해 담을 수 있는 보석을 검사하기 위한 for문을 실행합니다.
4. heapq a가 있고 a에 있는 최소 무게(a[0][0])보다 가방(capa)이 더 큰 경우 while문을 수행합니다.
4-1. heapq a에서 가장 작은 값을 받아 heapq p에 -v를 넣습니다. (최대힙으로 만드는 것)
4-2. heapq a에서 하나씩 빼서 while 조건을 만족시키면 계속 while문을 실행합니다.
5. 가방에 들어갈 수 있는 보석이 담긴 heapq p가 있다면 heapq p의 가장 작은 값을 출력해 c에 더합니다.(최종으로 가방에 넣는 것)
(heapq p에 넣을 때 가방의 가치를 -로 넣었기 때문에 가장 가치가 큰 값이 -로 나옵니다.
그래서 c에서 빼줍니다.)
6. 가방의 개수만큼 for문을 반복하여 보석의 최대 가격을 구합니다.

백준 알고리즘 1202번 : https://www.acmicpc.net/problem/1202