leetcode.com 763. Partition Labels

문제 링크: https://leetcode.com/problems/partition-labels/description/

파이썬 소스: https://bit.ly/48LfUEP

스트링 s에서 첫 글자를 때서, 2개의 리스트로 나눠 보겠습니다.

s[:1] , s[1:]으로 나누고, 2개의 리스트를 set()으로 변환한 뒤에, intersection() 메서드로 공통된 원소가 있는지에 확인해 봅니다. s[:1]의 길이가 1이기 때문에, intersection()의 리턴값인 set의 길이는 1또는 0 입니다. 코드로 구현하면 아래와 같습니다.

set_part = set(s[:1]) set_right = set(s[1:]) intersection = set_part.intersection(set_right)

 

-      Intersection의 길이가 0 이라는 의미는 s[1:] 과 s[:1]사이에 같은 원소가 없다는 뜻 입니다. 따라서, 1이 partition할 위치가 됩니다.

-      반대로 1이라는 의미는 s[:1]과 같은 글자가 s[1:]안에 포함되어 있다는 의미입니다. 문제에 따라서, parts as possible so that each letter appears in at most one part. 이 문장대로, 하나의 파트에 최대한 같은 글자가 많이 들어 있도록 partition을 해야 합니다. 그러므로, s[1:]과 같은 글자가 s[1:]에 들어 있기 때문에, 인덱스 2를 확인해 봐야 합니다.

 

s의 길이로 루프를 만들고, 파티션에 포함될 부분을 set_part = set()로, 파티션에 포함되지 않을 부분을 set_right = set(s[i:])로 아래와 같이 구현합니다. 두 set 사이에 intersection이 0이면 파티션을 나눠야 하구요, 0 보다 크다면, 파티션의 크기를 더 크게 할 수 있습니다.

 

from typing import List class Solution:     def partitionLabels(self, s: str) -> List[int]:         set_part = set()         partition_length = 0         answer = []         for i in range(len(s)):             if len(set_part) > 0:                 set_right = set(s[i:])                 intersection = set_part.intersection(set_right)                 if len(intersection) == 0:                     set_part.clear()                     answer.append(partition_length)                     partition_length = 0             set_part.add(s[i])             partition_length += 1         if partition_length != 0:             answer.append(partition_length)         return answer

 

코데풀 유튜브 구독 부탁드립니다.
https://www.youtube.com/@codapul

 

programmers.co.kr 코딩테스트 연습 > 탐욕법(Greedy) > 구명보트

 

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42885

보트에는 최대 2명까지 탈 수 있습니다.

2명의 몸무게의 합이 limit 보다 작다면, 몸무게가 작은사람 + 몸무게가 큰 사람

이렇게 짝을 지어서 보트에 태워야, 보트의 수를 최소화 할 수 있습니다.

몸무게가 가장 작은 사람을 찾기 위해서, 사람들의 몸무게를 정렬 합니다.

(limit - 첫번째 사람의 몸무게) 보다 작지만, 이 보다 작은 사람들 중에서는

가장 큰 몸무게를 가진 사람을 찾아야 합니다.

그러면 제일 오른쪽 사람 부터 왼쪽 방향으로 확인합니다.

이 때, (limit - 첫번째 사람의 몸무게) 몸무게 보다 큰 사람은,
같이 탈 수 있는 작은 몸무게를 가진 사람이 없기 때문에, 혼자서 보트를 타야 합니다.

몸무게가 작은 사람을 가리키고 있는 idx_left 와,

몸무게가 큰 사람을 가리키고 있는 idx_right 2개의 인덱스가 있습니다.

 

from typing import List

def solution(people: List, limit: int):
    people.sort()
    answer = 0
    idx_left, idx_right = 0, len(people) -1

 

2개의 인덱스는 배열의 시작과 끝을 가리키는 초기값을 가집니다.

from typing import List

def solution(people: List, limit: int):
    people.sort()
    answer = 0
    idx_left, idx_right = 0, len(people) -1

    while idx_left < idx_right:
        if people[idx_right] > limit - people[idx_left]:
            idx_right -= 1
            answer += 1
        else:
            idx_left += 1
            idx_right -= 1
            answer += 1

    if idx_left == idx_right:
        answer += 1

    return answer

이 방식으로 문제를 풀면 O(n) 으로 문제를 풀 수 있습니다.

같은 O(n)이지만, 리스트에서 몸무게가 적은 사람, 또는 많은 사람을 빼는 방식으로

pop(0) 또는 pop()을 사용해서 문제를 풀수도 있습니다.

하지만, 인덱스를 이동하는 방식보다, pop() 조금 느리기 때문에,

테스트 케이스를 조금 스포하자면, 이 문제의 효율성 테스트 1번을 통과 하는 것이 쉽지 않습니다. 

 

따라서 실행속도가 최대한 빠르게 구현을 하기 위해서, 리스트의 pop()메서드를 사용하기 보다는

배열의 index를 옮기는 방식으로 구현 해야 합니다.

programmers.co.kr 코딩테스트 연습 > 탐욕법(Greedy) > 단속카메라

 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42884

 여러대의 차량의 고속도로 진입시점과 진출시점이 주어지고, 진입/진출 시점이 겹치는 부분을 찾아서,
단속카메라를 몇대를 설치할 것인지 개수를 알아내는 문제입니다.

 이 문제 처럼 X 축에 평행하는 여러개의 직선의 시작점과 끝나는 점이 주어지고,
이직선 들의 관계를 문제에서 주어진 조건에 따라서 푸는 문제들은 interval 카테고리에 해당합니다.

interval 카테고리의 문제를 풀 때, 조심해야 할 부분이, 어떤 직선의 시작점/끝나는 점이
다른 직선의 시작점/끝나는 점과 만났을 때, 어떻게 처리해야 하는지,
문제를 꼼꼼히 읽어 보아야 합니다.

• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난 것으로 간주합니다.

위와 같은 조건이 문제에 기술되어 있습니다. 따라서, 어떤 직선의 끝나는 점과 다른 직선의 시작점이

같으면 2개의 직선이 서로 만나게 되는 것입니다.

( * 이렇게 시작점과 끝나는 점이 만났을 때 도, 의미가 있는 경우를 폐구간 이라고 말하구요,

inclusive 라고 표현하기도 합니다. )

어떤 두대의 차량(A,B)이 모두 지나가는 고속도로 구간이 있는지 확인하려면

총 2가지 경우를 확인해 봐야 합니다.

1. A진입 <= B진출 <= A진출

2. B진입 <= A진출 <=B진출

두대의 차량(A,B)이 1~2 경우 중에 한개의 경우에 해당 한다면,

두대의 차량이 모두 지나가는 구간은 아래와 같이 계산할 수 있습니다.

 max(A진입, B진입), min(A진출, B진출)

특정구간(진입,진출) 을 지나가는 차량을 최대한 빨리 계산해 내기 위해서는,

진입, 진출 구간의 차이가 적은 순서로 정렬해야 합니다.

answers 는 이미 지나간 차량의 진입/진출이나, 2대 이상의 차량이 모두 지나가는 구간을
가지고있는 리스트 입니다. 초기값이 없으므로, 진입이 가장 빠른 차량을 넣어줍니다. 

    routes.sort()
    answers: List = [routes.pop(0)]

입력으로 주어지는 routes를 for 루프 에서 하나씩 꺼냅니다
앞에서 말한 2가지 경우에 해당하는지 확인하고, 2대의 차량이 모두 지나가는 구간을
min(), max() 함수를 사용해서 계산합니다.

from typing import List

def solution(routes: List[List]):
    if len(routes) == 0:
        return 0

    routes.sort()
    answers: List = [routes.pop(0)]

    for car_in, car_out in routes:
        prev_in, prev_out = answers.pop()

        if prev_in <= car_out <= prev_out \
            or car_in <= prev_out <= car_out:
            answers.append([max(prev_in, car_in), min(prev_out, car_out)])
        else:
            answers.append([prev_in, prev_out])
            answers.append([car_in, car_out])

    return len(answers)