220902_프로그래머스 : 코딩테스트 문제4

Csw·2022년 9월 2일

TIL programmers python 코딩테스트

TIL

목록 보기

7/18

220901에 보았던 코딩테스트 문제 4개 관련 코드 및 풀이

4. 택시 배치

문제 안내

상세 설명

철수의 생일을 맞아 XX 식당에서 생일 파티를 하기로 했습니다.

생일 파티를 하는 XX 식당까지는 택시를 타고 이동하기로 했습니다.

철수의 친구들은 친한 친구들끼리 그룹을 구성하고 있으며, 한 사람당 하나의 그룹에만 속해 있습니다.

택시를 탈 때는 반드시 같은 그룹에 속한 친구들은 같은 택시를 타기로 했으며, 한 택시에는 여러 그룹이 함께 탈 수 있습니다.

단, 택시에는 최대 4명까지 함께 탑승 가능합니다.

각 그룹의 구성원 수가 들어있는 배열 s가 매개변수로 주어질 때, 필요한 택시의 수의 최솟값을 return 하도록 solution 함수를 완성해주세요.

제한사항

s는 각 그룹별 구성원 수가 들어있는 배열이며, 배열의 길이(그룹의 수)는 100,000 이하의 자연수입니다.

각 그룹의 구성원 수는 4 이하의 자연수입니다.

입출력 예

s output
[1,2,4,3,3] 4
[2,3,4,4,2,1,3,1] 5

s	output
[1,2,4,3,3]	4
[2,3,4,4,2,1,3,1]	5

입출력 예 설명

입출력 예 #1

한 그룹당 하나씩의 택시를 이용한다면 총 5대의 택시가 필요합니다.그러나 다음과 같이 탑승한다면 4대의 택시만으로도 충분합니다.

첫 번째 그룹(1명)과 네 번째 그룹(3명)이 같은 택시를 탑니다.

그 외 나머지 그룹은 모두 다른 택시를 탑니다.

입출력 예 #2

한 그룹당 하나씩의 택시를 이용한다면 총 8대의 택시가 필요하지만, 다음과 같이 탑승한다면 5대의 택시만으로도 충분합니다.

첫 번째 그룹(2명)과 다섯 번째 그룹(2명)이 같은 택시를 탑니다.

두 번째 그룹(3명)과 여섯 번째 그룹(1명)이 같은 택시를 탑니다.

일곱 번째 그룹(3명)과 여덟 번째 그룹(1명)이 같은 택시를 탑니다.

그 외 나머지 그룹은 모두 다른 택시를 탑니다.

풀이 및 코드

풀이

로직 설명

단계	요약	설명
1단계	인원별 그룹의 숫자 파악	-리스트의 각 요소는 그룹별 구성원 수를 의미하므로, 1명/2명/3명/4명 그룹이 각각 몇 개 있는지 카운트
2단계	그룹별 인원수에 따라 1차 처리	- 4명 그룹은 해당 그룹의 숫자가 곧 필요한 택시 수를 의미 - 3명 그룹은 1명 그룹과 매칭 시, 총 4명이 되므로 해당 매칭 수가 곧 필요한 택시 수를 의미 - 2명 그룹은 그룹을 2개씩 매칭 시, 총 4명이 되므로 해당 매칭 수가 곧 필요한 택시 수를 의미
3단계	2단계까지 진행 후 남은 그룹들에 대한 처리	- 3명 그룹의 잔여 수 계산 - 1명 그룹의 잔여 수 계산 - 2명 그룹의 잔여 수 계산
4단계	경우의 수를 나누어 생각	- 인원 수가 많은 그룹부터 고려하여 경우의 수를 나누어 생각 - 3명 그룹의 잔여 수에 대한 경우 → 2명 그룹의 잔여 수에 대한 경우 → 1명 그룹의 잔여 수에 대한 경우

코드 구현 및 라인별 풀이

Code

def solution(s):
    A = s.count(4)
    B = s.count(3)
    C = s.count(1)
    D = s.count(2)

    E = min(B,C)
    F = D//2
    G = (C-E)//4

    H = B-E
    I = C-E-G*4
    J = D%2

    mid = A + E + F + G 
    # 아래에서 경우를 나눠 생각하게 되더라도 변하지 않는 고정 값들을 더해서 중간 계산 결과를 뜻하는 mid로 할당해놓음

    if H > 0:
        return mid + H + J
    else:
        if J>0:
            if I == 3:
                return mid + 2
            else:
                return mid + 1
        else:
            if I == 0:
                return mid
            else:
                return mid + 1