[Greedy] 이코 기출문제

모험가 길드

입력 

N(2 ≤ N ≤ 100,000)

N명의 공포도(1 ≤ 공포도≤ N) 공백으로 구분

 

출력

공포도가 x인 모험가는 반드시 x명 이상으로 구성한 그룹으로 참여 가능할 때, 여행을 떠날 수 있는 그룹 수의 최댓값 출력.

(모든 모험가를 그룹에 넣을 필요 없음)

 

그룹 수의 최댓값 -> 가장 공포도가 작은 사람들부터 그룹만들기

> python

더보기

import sys

n = int(input())
data = list(map(int, input().split()))

data.sort()

result = 0
count = 0

for degree in data:
    count += 1
    
    if count >= degree:
        result  += 1
        count = 0
        
print(result)

> java

더보기

 

---

곱하기 혹은 더하기

 

입력 

여러개의 숫자로 구성된 하나의 문자열S (1 ≤ S의 길이 ≤ 20), (0 ≤ S의 구성 숫자 ≤ 9)

 

출력

왼쪽부터 오른쪽으로 하나씩 ' * ' 혹은 ' + ' 연산자를 넣어 차례로 계산할 때, 만들어 질 수 있는 가장 큰 수 출력

 

> python

더보기

import sys

s = input()

result = int(s[0])
for i in range(1, len(s)):
    
    if int(s[i]) <= 1 or result <= 1:
        result += int(s[i])
    else:
        result *= int(s[i])
        
print(result)

> java

더보기

 

---

문자열 뒤집기

 

입력 

0과 1로만 이루어진 문자열 S (1 ≤ S의 길이 ≤ 1000,000) 

 

출력

연속된 하나 이상의 숫자를 잡고 뒤집는 행위를 반복해 모두 같은 숫자로 만들 때, 최소 횟수 출력

 

나는 나동빈선생님의 아이디어를 따라가지 모댓다,,.

> python

더보기

data = input()
count0 = 0 # 전부 0으로 바꾸는 경우
count1 = 0 # 전부 1로 바꾸는 경우

if data[0] == '1':
    count0 += 1
else:
    count1 += 1

for i in range(len(data) - 1):
    if data[i] != data[i + 1]:
        
        if data[i + 1] == '1':
            count0 += 1
        else:
            count1 += 1

print(min(count0, count1))

s = input()

change_count = 0
before = s[0]

for i in range(1, len(s)):
    
    now = s[i]
    if before != now:
        change_count += 1
    
    before = now
    
print(int(change_count/2))

> java

더보기

 

---

만들 수 없는 금액

 

입력 

N(1 ≤ N ≤ 1,000)

N개의 동전의 화폐단위(1 ≤ 화폐단위≤ 1,000,000) 공백으로 구분

 

출력

주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값 출력

 

한번 더 봐야 제대로 설명할 수 있을 것 같음.

> python

더보기

n = int(input())
coins = list(map(int, input().split()))
coins.sort()

target = 1
for i in coins:
    
    if target < i:
        break
    
    target += i
    
print(target)

> java

더보기

 

---

볼링공 고르기

 

입력 

N(1 ≤ N ≤ 1,000) M(1 ≤ M ≤ 10)  공백으로 구분

N개의 볼링공의 무게 (1 ≤ 볼링공의 무게 ≤ M) 공백으로 구분

 

출력

순서대로 1번 부터 N번의 볼링공 중 서로 다른 무게를 사용해야 할 때, 두 사람이 고를 수 있는 조합 수 출력.

 

조합문제.

> python

더보기

n, m = map(int, input().split())
data = list(map(int, input().split()))

data_of_weight = [0] * (m+1)

for x in data:
    data_of_weight[x] += 1
    
result = 0
for i in range(1, m+1):
    n -= data_of_weight[i]
    result += data_of_weight[i] * n
    
print(result)

> java

더보기

 

---

무지의 먹방 라이브

입/출력
https://school.programmers.co.kr/learn/courses/30/lessons/42891?language=python3 

프로그래머스

 

> python

def turn_table(length, now):
    
    if now == length:
        return 1
    else:
        return now + 1

    
def solution(food_times, k):
    answer = 0    
    now = 0
    count = 0

    while count < k+1 :
        
        now = turn_table(len(food_times), now)
                    
        if sum(food_times) == 0:
            return -1

        if food_times[now-1] == 0:
            continue
        else:
            food_times[now-1] -= 1
            count += 1
              
    answer = now    
    return answer

> 효율성 생각 x

 

import heapq

def solution(food_times, k):
    
    if sum(food_times) <= k:
        return -1
    
    food_info = []
    i = 1
    for food_time in food_times:
        heapq.heappush(food_info, (food_time, i))
        i += 1
    
    remain_food = len(food_info)
    ated_food = 0
    while k>0:
        
        print(food_info)
        turn_time_by_min = (food_info[0][0] - ated_food) * remain_food
        
        if turn_time_by_min < k:
            ated_food = heapq.heappop(food_info)[0]
            k -= turn_time_by_min
            remain_food -= 1
            continue
        
        if turn_time_by_min >= k:
            index = k % remain_food
            food_info.sort(key = lambda x:x[1])
            answer = food_info[index][1]
            break
                
    return answer

> java

더보기

 

---

이것이 코딩테스트다_나동빈 정리허긔