99클럽 코테 스터디
오늘도 greedy를 주제로 한 문제들이었다. 내가 유독 greedy와 dp 유형에 강한 면이 있어서, 금방 풀 수 있었다.
자바 챌린저 발표자가 안 나오길래 끝까지 안 나오면 발표하려고 자바로도 풀어보았다. 다행히 풀고 나니 발표 지원자는 있었다.
비기너 문제 Split a String in Balanced Strings : https://leetcode.com/problems/split-a-string-in-balanced-strings/description/
미들러 문제 구명보트 : https://school.programmers.co.kr/learn/courses/30/lessons/42885
챌린저 문제 단속카메라 : https://school.programmers.co.kr/learn/courses/30/lessons/42884
출처 : 프로그래머스, leetcode
비기너 문제 : Split a String in Balanced Strings
풀이 접근
앞에서부터 세서 L과 R의 개수가 똑같으면 바로 자르고 answer에 1을 더해준다. 전체 문자열이 'balanced'라는 전제가 있으므로, 마지막까지 도달하면 반드시 L과 R이 똑같다.
개수가 같은지 세는 방식은 L과 R을 각각 세서 비교해도 되지만, 0으로 시작하는 값으로 L이면 더하고 R이면 빼거나 반대로 해서 0이 될 때마다 자르는 식으로 하면 변수 하나만으로도 수행 가능하다.
코드(Python3, Accepted, 22ms(상위 0.63%), 16.30MB(상위 1.63%))
오늘은 첫 제출만에 아주 좋은 결과가 나와서 흡족했다. 그만큼 깔끔한 풀이라는 뜻이니까.
L은 왼쪽으로 이동, R은 오른쪽으로 이동이라고 생각했을 때, 제자리로 돌아올 때마다 한 덩어리의 'balanced string'이 완성되므로, 0이 될 때마다 answer를 1씩 늘려준다.
class Solution:
def balancedStringSplit(self, s: str) -> int:
left = 0
answer = 0
for alp in s:
if alp == 'L':
left += 1
else:
left -= 1
if not left:
answer += 1
return answer
미들러 문제 : 구명보트
풀이 접근
이 문제는 어떻게 greedy하면서도 가장 효율적으로 풀 수 있는가? 답은 정렬 후 투포인터에 있다.
우선, 사람을 무게 순으로 정렬한다. 그리고 가장 무거운 사람을 살펴본다.
구명보트엔 최대 2명이 탈 수 있는데, 당연하게도 혼자 타는 것보단 가능하면 둘이 타는 게 더 좋을 것이다.
그렇다면, 가장 무거운 사람은 본인과 '2인승이 가능한 사람 중 가장 무거운 사람'과 타는 게 최선인가?
-> 이것은 반은 맞고 반은 틀렸다.
상식적으로 생각했을 땐 그게 제일 좋긴 하지만, 제일 가벼운 사람과 타도 전혀 지장이 없다.
그리고 이 쪽이 구명보트 타는 조를 짜는 데 코드적으로도, 실제 인간이 짠다고 생각해도 훨씬 편하다.
왜 그럴까?
- limit가 100이고, 가장 가벼운 사람 2명과 가장 무거운 사람 1명이 각각 10, 20, 80인 경우, 80+20으로 100kg를 꽉 채워서 탑승하는 게 일반적인 생각으론 최선이겠지만, 어차피 10kg인 사람을 남겨두면 누군가는 2인으로 데리고 타야 하는데, 그 누군가는 80kg 이하일 것이므로, 10kg인 사람과 20kg인 사람의 자리를 서로 바꿔도 전혀 지장이 없다.
제일 무거운 80kg인 사람이 20kg를 데리고 타도, 어차피 나중에 80kg 이하인 사람이 10kg인 사람을 결국 데려가야 하는데, 80kg인 사람이 10kg를 데려가고 나중에 80kg 이하인 사람은 어차피 20kg를 데려갈 수 있다는 얘기다.
즉, 제일 무거운 사람+제일 가벼운 사람 조합이 가능하면 greedy하게 바로바로 넣어서 보내면 된다.
안 되면 제일 무거운 사람은 반드시 1인으로 타야 하므로 제일 무거운 사람 한 명만 보낸다. 이런 상황을 가장 쉽게 구현하는 방식이 투 포인터이다. 구현 방식은 아래 코드 설명에 적어두었다.
코드(Python3, 통과, 최대 9.04ms, 10.6MB)
프로그래머스는 테케가 너무 가볍다고 불평을 자주 했더니, 효율성 테스트도 있는 문제가 나왔다. 내 코드의 효율성을 증명할 수 있는 모먼트이다.
사람을 무게순으로 정렬하고, 남은 사람 중 가장 가벼운 사람의 번호인 light = 0, 남은 사람 중 가장 무거운 사람의 번호인 heavy = n-1로 시작한다.
두 인덱스에 위치한 사람의 무게의 합이 limit 이하이면 둘을 묶어 보내고 가벼운 사람 번호는 +1, 무거운 사람 번호는 -1을 해 준다.
limit를 초과하면 무거운 사람만 보내므로 무거운 사람 번호만 -1을 해 준다.
보트를 한 대 보낼 때마다 answer를 1씩 늘린다.
이를 남은 사람이 없을 때까지 반복한다.
def solution(people, limit):
people.sort()
light = 0
heavy = len(people) - 1
answer = 0
while light <= heavy:
answer += 1
if people[light] + people[heavy] <= limit:
light += 1
heavy -= 1
return answer챌린저 문제 : 단속카메라
풀이 접근
이 문제도 일단 정렬해놓고 생각을 시작한다.
가장 왼쪽에서 시작하는 구간이 예를 들어 [-50, -20]이라고 하자. 그러면 반드시 이 구간 안에 카메라가 한 개는 있어야 한다.
이걸 어디에 설치해야 하는가? 구간을 정렬했으니 맨 오른쪽에 greedy하게 설치하면 될까? 항상 그렇진 않다. 그 다음 구간들의 구성에 따라 달라질 수 있기 때문이다. 다음 구간은 이 구간과 어떤 관계인가? 이를 분류부터 해야 한다.
- 바로 다음 구간이 예를 들어 [-40, 0]일 수도 있고(앞선 구간과 일부 겹침),
- [-40, -30]일 수도 있고(앞선 구간에 포함됨),
- [-10, 10]일 수도 있다(앞선 구간과 겹치는 부분이 없음).
우선, 맨 오른쪽에 설치했다고 생각하고, 이를 옮기는 경우까지 고려하면 된다.
옮길 때는, 당연하지만, 오른쪽으로는 옮길 수 없고, 왼쪽으로만 옮길 수 있다.
첫 번째 경우(-40,0), 첫 구간의 맨 오른쪽(-20)에 카메라를 설치한 게 유효하다. 첫 구간의 맨 오른쪽이 다음 구간에 포함되어 있기 때문이다.
두 번째 경우(-40,-30), 카메라를 다음 구간의 맨 오른쪽(-30)으로 옮겨야 한다. 이유는 설명하지 않아도 되리라 본다.
세 번째 경우(-10,10), 해당 구간(-10,10)을 포함해서 앞으로 나올 구간들은 더 이상 첫 구간인 [-50, -20]과 연관이 없다. 시작점이 -20 초과일 것이기 때문이다. 그러면, -20에 설치한 카메라에 대해서는 더 생각할 필요가 없고, [-10, 10]을 새로운 카메라를 설치하는 첫 번째 구간으로 인식하면 될 것이다.
이를 모든 구간을 순회하면서 적용하면 된다.
코드(Python3, 통과, 최대 2.40ms, 10.5MB)
greedy가 으레 그렇지만, 근거가 되는 논리는 길고, 코드는 짧다.
cam은 카메라를 설치할 임시 위치이다.
cam의 위치는 가능한 맨 오른쪽으로 설정했으므로, 오른쪽으로는 더 옮길 수 없지만, 왼쪽으로는 옮겨질 수도 있다.
구간을 살펴봤는데 시작 지점이 cam의 위치보다 왼쪽이면, 아직은 cam이 커버할 수 있는 구간이 들어온 것이다. 근데 오른쪽 끝 지점도 cam보다 왼쪽에 있으면, cam을 해당 끝 지점으로 옮겨줘야 한다.
구간을 살펴봤는데 시작 지점이 cam의 위치보다 오른쪽이면, 더 이상 해당 cam이 커버할 수 없는 구간이 새로 들어온 것이므로, 새로운 cam을 임시로 가능한 맨 오른쪽(구간의 끝)에 설치하고 answer를 1 늘려준다.
그리고 이 작업을 반복한다.
def solution(routes):
routes.sort()
cam = routes[0][1]
answer = 1
for i in range(1, len(routes)):
if routes[i][0] > cam:
answer += 1
cam = routes[i][1]
else:
cam = min(cam, routes[i][1])
return answer코드2(java, 통과, 최대 8.82ms, 57.6MB)
자바는 2차원 배열을 생으로 sort 못한다. 시도하면 오류가 뜬다. 그래서 정렬하는 방법을 검색해서 람다식으로 정렬했다. 파이썬에 뇌가 절여진 나에겐 굉장히 불편쓰...
import java.util.Arrays;
class Solution {
public int solution(int[][] routes) {
Arrays.sort(routes, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);
int cam = routes[0][1];
int answer = 1;
for (int i = 1; i < routes.length; i++) {
if (routes[i][0] > cam) {
answer++;
cam = routes[i][1];
} else {
if (routes[i][1] < cam) {
cam = routes[i][1];
}
}
}
return answer;
}
}