이코테 유형별 기출문제

그리디

무지의 먹방 라이브

풀이 특징

• 시뮬레이션 형식으로 완전탐색할 경우 시간초과가 된다.
• 시간초과의 경우 log(N) 형식을 고민해야 한다.
• PriorityQueue (heapq) 를 사용하여 음식시간이 적은 순으로 음식을 확인해야 한다.
• 남은 시간과 한 음식이 제거될 때 까지의 시간(남은 음식수 * 음식시간이 가장 적은 음식)을 비교한다.
• 한 음식이 제거될 수 있을 경우 해당 음식을 heapq 에서 제거, 다음 음식에서 해당음식을 먹은 시간을 빼야하므로 마지막에 제거된 음식의 시간을 저장한다.
• 한 음식이 제거될 때 까지 전체 음식을 못 먹는 경우 해당 음식을 포함하여 음식번호 순서로 정렬한다.
• 정렬 후 남은 시간을 남은 음식개수로 나눈 나머지 값이 k초 후 먹을 음식의 인덱스가 된다.
• 따라서 해당 인덱스의 음식 번호를 반환한다.

import heapq

def solution(food_times, k):
    # k초가 되기전까지 음식을 다 먹을 수 있는 경우
    if sum(food_times) <= k:
        return -1
    
    # 모든 음식을 시간순으로 정렬해야 한다.
    # 마지막에 음식번호를 출력해야 하기 때문에 heapq(시간, 음식번호) 삽입
    q = []
    for i in range(len(food_times)):
        heapq.heappush(q, (food_times[i], i+1))
        
    sumTime = 0 # 섭취 누적시간
    removedTime = 0 # 직전에 제거된 음식의 시간
    foodCount = len(food_times) # 남은 음식의 개수
    
    while True:
        now = heapq.heappop(q)
        nowFoodTime = now[0]
        roundTime = foodCount * (nowFoodTime - removedTime)
        # 남은 시간이 해당 음식기준 전체음식을 먹는데 걸리는 시간보다 작은 경우 -> 먹지못하고 종료
        if (k - sumTime) < roundTime:
            heapq.heappush(q, now)
            break;
        # 누적시간 += 현재 음식기준 전체 음식을 먹는데 걸리는 시간
        sumTime += roundTime
        # 남은 음식의 개수 -1
        foodCount -= 1
        # 직전 제거된 음식 반영
        removedTime = nowFoodTime
    
    # 남은 음식들을 음식번호 순으로 정렬한다
    remainFoods = sorted(q, key=lambda x: x[1])
    # 마지막 음식 + 1 위치는 (남은 시간 % 남은 음식개수)
    return remainFoods[(k - sumTime)%foodCount][1]

구현

럭키 스트레이트

# 럭키 스트레이트를 사용할 수 있는 상태인지 출력
nums = list(map(int, list(input())))
length = len(nums)
leftSum = sum(nums[:length//2])
rightSum = sum(nums[length//2:])
print("LUCKY" if leftSum == rightSum else "READY")

문자열 재정렬

풀이 특징

• str.isalpha(): 알파벳인지 여부
• str.isnumeric(): 숫자인지 여부
• str.join(iterable): 배열 -> 문자열로 합치기

# 알파벳 오름차순 정렬 + 숫자합 출력
inputs = input()
chars = []
sum = 0
for i in inputs:
    if i.isalpha():
        chars.append(i)
    else:
        sum += int(i)
chars.sort()
print("".join(chars) + str(sum))

문자열 압축

풀이 특징

• 비교단위를 1 ~ len(s)//2 까지 증가시키면서 확인
• 비교단위 크기의 이전 문자열, 현재 문자열을 비교하면서 count 증가
• 다른 문자열인 경우 count 가 1보다 큰 경우 숫자와 함께 문자열 추가
• 최종 남은 문자에 대해 count 가 1보다 큰 경우 숫자와 함께 남은 문자열 추가

# 압축 문자열 중 가장 짧은 길이 반환
def solution(s):
    minLength = len(s)
    for width in range(1, len(s)//2+1):
        string = ""
        compare = s[0:width]
        count = 1
        
        for index in range(width, len(s), width):
            current = s[index:index+width]
            if current == compare:
                count += 1
            else:
                if count > 1:
                    string += str(count)
                string += compare
                compare = current
                count = 1
        
        if count > 1:
            string += str(count)
        
        string += compare
        minLength = min(minLength, len(string))
            
    return minLength