[2/5] Kakao Internship 기출문제 풀이

👉 사용 언어 : PYTHON3

주차 요금 계산

✅ Solution

from collections import defaultdict
import math

def solution(fees, records):
    answer = []
    times = defaultdict(list)
    for i in records:
        times[i.split(' ')[1]].append((i.split(' ')[0]))
    for j in sorted(times.keys()):
        time = 0
        while len(times[j]) >= 2:
            before_h, before_m = list(map(int, times[j][0].split(':')))
            after_h, after_m = list(map(int, times[j][1].split(':')))
            before_h *= 60
            after_h *= 60
            time += ((after_h + after_m) - (before_h + before_m))
            del times[j][0:2]

        if len(times[j]) != 0:
            time += ((23*60 + 59) - ((int(times[j][0].split(':')[0])*60) + int(times[j][0].split(':')[1])))

        if time <= fees[0]:
            answer.append(fees[1])
        else:
            answer.append(fees[1] + math.ceil((time-fees[0])/fees[2]) * fees[3])

    return answer

 

👉 문제 설명 및 제한 사항

• 요금 계산식 : 기본 요금 + ⌈(누적 주차 시간 - 기본 시간) / 단위 시간⌉ x 단위 요금
  • 즉, fees[1] + ⌈누적 주차 시간 - fees[0]/ fees[2]⌉ * fees[3]
  • ⌈a⌉ : a보다 작지 않은 최소의 정수 _ 올림
  • 누적 주차 시간 <= 기본 시간 : 기본 요금 5000원만 청구
• fees 배열
  • [0] : 1 <= 기본 시간(분) <= 1439
  • [1] : 0 <= 기본 요금(원) <= 100,000
  • [2] : 1 <= 단위 시간(분) <= 1439
  • [3] : 1 <= 단위 요금(원) <= 1,000
• records 배열 원소
  • "시각 차량번호 내역"
  • 시각 : HH:MM 형식 _ 00:00 ~ 23:59
  • 차량번호 : '0'~'9'로 이루어진 4개의 문자(=문자열)
  • 내역 : IN or OUT
• 어떤 차량이 입차된 후에 출차된 내역이 없다면, 23:59에 출차된 것으로 간주한다.
• 리턴할 아웃풋은 차량번호 작은 순으로 출력한다.
• 같은 차량 번호가 여러번 입/출차하면 누적 주차 시간(합)으로 요금을 계산한다.

👉 아이디어

• defaultdict를 사용하여 리스트를 value로 가지는 딕셔너리를 생성한다.(초깃값 지정)
• 딕셔너리의 Key는 차량번호, Value는 시각 리스트를 맵핑하여 저장한다.
  • IN-OUT 반복 이므로 따로 IN인지 OUT인지 정보를 가지고 있을 필요가 없다.
• 리턴할 아웃풋 배열이 차량번호가 작은 순 으로 저장된 주차 요금이므로 반복문을 사용하여 딕셔너리 요소를 꺼낼 때, sorted()를 통해 차량번호(Key)가 작은 것부터 꺼내도록 작성한다.
• 시각 리스트의 요소 개수가 2개 이상 일 동안 반복문 을 돌린다.
  • 2개씩 잘라서 IN/OUT 시각을 비교 하여 주차 시간을 계산하고 누적 주차 시간에 추가한다.
  • while문이 무한루프 도는 것을 방지 하기 위해 시각 리스트에서 해당 요소 2개 를 삭제 한다.
  • 반복문이 끝난는데도 요소가 남아있다면 (= 원래 시각리스트 요소 개수가 홀수개였다면) 남은 하나는 OUT 시각을 23:59로 하여 누적 주차 시간에 추가한다.
• 차량 번호당 청구해야하는 총 주차 요금을 계산하여 정답 배열에 추가한다.
  • 누적 주차 시간  < 기본 시간 : 기본 요금(fees[1])
  • 누적 주차 시간  >= 기본 시간 : fees[1] + ⌈누적 주차 시간 - fees[0]/ fees[2]⌉ * fees[3] 적용

 

✅ 다른 사람 풀이 참고

from collections import defaultdict
from math import ceil

class Parking:
    def __init__(self, fees):
        self.fees = fees
        self.in_flag = False
        self.in_time = 0
        self.total = 0

    def update(self, t, inout):
        self.in_flag = True if inout=='IN' else False
        if self.in_flag:  self.in_time = str2int(t)
        else:             self.total  += (str2int(t)-self.in_time)

    def calc_fee(self):
        if self.in_flag: self.update('23:59', 'out')
        add_t = self.total - self.fees[0]
        return self.fees[1] + ceil(add_t/self.fees[2]) * self.fees[3] if add_t >= 0 else self.fees[1]

def str2int(string):
    return int(string[:2])*60 + int(string[3:])

def solution(fees, records):
    recordsDict = defaultdict(lambda:Parking(fees))
    for rcd in records:
        t, car, inout = rcd.split()
        recordsDict[car].update(t, inout)
    return [v.calc_fee() for k, v in sorted(recordsDict.items())]

 

👉 깨달은 것 / 알게된 것

• Parking이라는 클래스를 선언하고 그 안에서 변수 4개 및 메서드 2개 선언
  • fees : fees 배열 _ 매개변수로 전달 받음
  • in_flag : IN/OUT인지?
  • in_time : 입차 시각
  • total : 누적 주차 시간
  • update(self, t, inout) : 누적 주차 시간 계산
    • IN : in_time 변수 업데이트 (분 단위)
    • OUT : in_total 변수 업데이트
  • calc_fee(self) : 주차 요금 계산
    • IN : 기본적으로 23:59 출차 고려
• str2int(string) : (문자열) HH:MM > (정수) 분 단위로 변환
  • 문자열 슬라이싱을 사용하여 코드를 가독성있게 작성하였다.
  • HH는 [:2]로 잘라 *60 해주어서 분으로 변환, MM는 [3:]로 잘라주었다.
• 딕셔너리 value에 Parking 클래스 인스턴스를 사용할 수 있다.
• 마찬가지로 차량번호 작은 순이기 때문에 반복문 내에서 딕셔너리의 Key를 기준으로 오름차순 정렬하여 요소를 뽑아내었다.

메뉴 리뉴얼

✅ Solution

from itertools import combinations
from collections import deque

def solution(orders, course):
    answer = deque([])
    result = deque([])
    for i in range(len(orders)):
        for j in range(i+1, len(orders)):
            inters = set(orders[i]).intersection(set(orders[j]))
            for k in course:
                if len(inters) >= k:
                    [answer.append(''.join(sorted(c))) for c in list(combinations(''.join(list(inters)), k))]
    orders_dict = dict.fromkeys(list(set(answer)))
    for key in orders_dict.keys():
        orders_dict[key] = answer.count(key)
    for k in course:
        _max = -1
        for key in orders_dict.keys():
            if len(key) == k and _max <= orders_dict[key]:
                _max = max(_max, orders_dict[key])
        for key in orders_dict.keys():
            if len(key) == k and orders_dict[key] == _max:
                result.append(key)
    return sorted(result)

 

👉 문제 설명 및 제한 사항

• orders : 각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열
  • 길이 : 2 이상 20 이하
  • 각 원소 크기 : 2 이상 10 이하
  • 알파벳 대문자로만 & 알파벳 중복 X
• course : 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열
  • 길이 : 1 이상 10 이하
  • 각 원소 크기 : 2 이상 10 이하
  • 오름차순으로 정렬 & 알파벳 중복 X
• 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return
  • 오름차순으로 정렬 & 배열 길이 1 이상
  • 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성 

👉 아이디어

• 중첩 반복문을 통해 두 개의 원소씩 묶어서 교집합을 구한다.
• 내부에 course 배열에서 반복문을 또 다시 돌려 배열 원소와 교집합의 길이를 비교한다.
  • course 배열 원소(k) <= 교집합 길이일 때, Combinations를 사용하여 k개의 문자를 뽑아 리스트를 만들고 해당 리스트의 원소들을 모두 오름차순 정렬한 뒤 문자열로 변환(''.join())하여 새로운 배열(answer)에 추가한다.
• answer 배열에서 중복된 원소를 제거한 뒤, 배열 원소를 key 로 하는 딕셔너리를 생성한다.
  • 딕셔너리의 value로 answer 배열에서의 각 원소(문자열)의 개수를 넣어준다.
• course 배열에서 반복문을 돌려
  • 각 원소(= 문자열 길이)에 해당하는 딕셔너리 key의 value 중 max 값을 찾는다.
  • 딕셔너리에서 max값을 value로 갖는 모든 key를 정답 배열에 추가한다.
• 정답 배열을 오름차순 정렬하여 반환한다.

 

✅ 다른 사람 풀이 참고

import collections
import itertools

def solution(orders, course):
    result = []

    for course_size in course:
        order_combinations = []
        for order in orders:
            order_combinations += itertools.combinations(sorted(order), course_size)

        most_ordered = collections.Counter(order_combinations).most_common()
        result += [ k for k, v in most_ordered if v > 1 and v == most_ordered[0][1] ]

    return [ ''.join(v) for v in sorted(result) ]

from itertools import combinations
from collections import Counter

def solution(orders, course):
    answer = []
    
    for c in course:
        candidate = []  # 가능한 모든 조합을 저장할 리스트
        for order in orders:
            candidate += combinations(sorted(order), c)
        count = Counter(candidate)  # 각 조합이 몇 번 주문되었는지 세기 (course로 나올 수 있는 모든 조합)
       
        if count:
            max_count = max(count.values())  # 가장 많이 주문된 조합의 주문 횟수
            print(max_count)
            if max_count >= 2:  # 최소 2번 이상 주문된 조합
                answer += [''.join(key) for key in count if count[key] == max_count]
                
    
    return sorted(answer)

 

👉 깨달은 것 / 알게된 것

• Collections.Counter()
  • Counter 생성자 : 여러 형태의 데이터를 인자로 받으며 중복된 데이터가 저장된 배열을 인자로 넘기면 각 원소가 몇 번씩 나오는지가 저장된 객체(= 딕셔너리)를 반환한다.
  • 내가 풀이한 코드에서 배열을 사용하여 딕셔너리를 만들고 반복문을 돌려 카운트 값을 딕셔너리의 value에 저장한 과정을 collections 모듈의 Counter 클래스 하나로 구현해낼 수 있다.
  • 파이썬의 기본 자료구조인 사전(dictionary)를 확장하고 있기 때문에, 사전 에서 제공하는 API를 그대로 다 사용 가능 하다.
  • 데이터의 개수가 많은 순으로 정렬된 배열을 리턴하는 most_common()이라는 메서드를 제공한다.
• 참고 : Counter는 마치 숫자처럼 산술 연산자를 사용할 수 있다❗️

counter1 = Counter(["A", "A", "B"])
counter2 = Counter(["A", "B", "B"])

counter1 + counter2

# Counter({'A': 3, 'B': 3})