Classic_Blue_Note

문제

programmers.co.kr/learn/courses/30/lessons/42885

풀이

해당 문제도 풀이 과정 자체는 떠올리기가 쉬운 편이다. 하지만 속도를 최적화하는 과정에서 오래 걸린 문제였다.

조건을 생각해 보면, 2명까지만 탑승이 가능하고, 가능한 한 적은 숫자의 보트를 보내는 것이 목표이다. 따라서 무게를 최대한 한계에 맞춰서 태워 보내는 것이 중요하다.

그래서 해당 조건을 만족하기 위해 필연적으로 탐색을 진행해야 한다. 하지만 이 탐색 과정에서, 연산을 최소한으로 사용하는 것이 목표이다.

필자는 다음과 같은 방식으로 그리디 알고리즘을 적용했다.

1. 사람을 무게 오름차순으로 배열한다.
2. 사람 배열을 순환하면서 자기 자신과 바로 앞 위치의 값을 더하면 한계보다 클 경우, 바로 멈춘다.
3. 그게 아닐 경우, rightidx라는 값을 이용한다. 이를 통해 뒤쪽 가장 큰 값부터 차례대로 자기 자신의 값과 더해서 한계보다 크지 않을 경우, 뒤쪽의 값을 리스트에서 빼내고, 이후의 반복은 빼낸 값 바로 앞의 값부터 다시 앞쪽으로 쭉 반복한다.

3번과 같이 반복하는 이유는, 소팅을 진행했기 때문에 맨 앞에는 가장 작은 값, 맨 뒤에는 가장 큰 값이 배치되게 된다. 첫번째 순환을 생각해 보자, 이때 맨 앞의 값과 맨 뒤의 값부터 차례로 앞쪽으로 가면서 비교하게 되는데, 두개의 합이 한계보다 큰 경우 그 다음 값으로 넘어가는 식으로 순환이 진행된다. 그러다 합이 한계값보다 크지 않을 경우, 해당 값을 빼낸 뒤 그 다음 순환에서는 앞쪽은 두번째 값, 뒤쪽은 빼낸 값의 바로 앞쪽 값부터 음의 방향으로 비교한다. 왜냐하면 첫번째 값보다 두번째 값이 무조건 크거나 같기 때문에, 빼낸 값보다 양의 방향에 있는 값은 굳이 비교할 필요도 없이 한계값보다 커지기 때문이다. 이러한 방식으로 앞쪽, 뒤쪽으로 포인터를 사용하였고, 이 역시 투포인터를 사용하여 값을 구하는 편이 pop연산을 사용하는 것보다 속도가 빠르지만, pop연산을 사용해서 코드가 간결해졌고, 문제가 해결되었기 때문에 이 방식을 사용하였다.

마지막에 전체에 대한 순환이 끝나면 전체 리스트의 길이를 구하는 것으로 답안을 구해주면 된다.

코드

def solution(people, limit):
    people.sort()
    rightidx = len(people)
    
    for i in range(len(people)):
        if people[i] + people[i+1] > limit:
            break
            
        while True:
            rightidx -= 1
            
            if people[i] + people[rightidx] <= limit:
                people.pop(rightidx)
                break
                
    answer = len(people)
    
    return answer

문제

programmers.co.kr/learn/courses/30/lessons/42883

풀이

조건을 간단하게 정리해 보면, 전체 숫자에서 몇 개의 숫자를 빼서 가장 큰 숫자를 만드는 게 관건이다. 그래서 필자는 우선 전체에서 숫자를 빼내는 것보다는, 전체 중 숫자들을 골라내서 가져오는 것이 알고리즘 구상에 더 용이하다고 판단하였다.

그래서 처음에 choose라는 전체 길이에서 k값만큼을 뺀, 선택해야 하는 숫자의 개수를 이용하였고, choose가 0이 되면 빠져나올 수 있도록 알고리즘을 작성하였다.

이후 반복 과정에서의 아이디어는, 뒤쪽 숫자를 모두 선택한다고 가정했을 때, 앞쪽에서 가장 큰 숫자를 고를 때가 가장 큰 값이 된다는 점이다. 이후 앞쪽에서 숫자를 고르면, 그 숫자 이후로 다시 반복을 진행하면 된다. 그러다가 고른 숫자가 앞쪽에서 맨 뒤 숫자일 경우, 그 이후의 숫자들을 모두 선택한다고 판단하면 된다. 또한 시간을 줄이기 위해, 큰 값을 선택할 때 숫자가 9가 나오는 경우에는 그 뒤쪽을 확인할 필요가 없기 때문에 바로 넘어가는 방식으로 시간을 줄여 주었다.

처음에는 pop 연산을 이용하여 프로그램을 진행했는데, pop 연산 자체가 O(n)의 시간 복잡도를 갖기 때문에, 시간 초과가 자주 일어났다. 그래서 이 시간 초과를 해결하기 위해 startidx와 endidx를 통해 투포인터 알고리즘을 적용하였다. 반복을 idx를 이용해 주고, 앞쪽 값들의 시작점과 끝점을 각각 포인팅하여 문자열의 슬라이싱 없이도 순환할 수 있도록 적용하였다.

해당 알고리즘 문제에서는 알고리즘 구상 단계에서 k를 이용해서 단순히 빼내는 것이 아니라 유효한 숫자들을 골라내는 방식으로 반대로 생각하는 것, 시간 관련해서는 pop을 사용하지 않고 투포인터를 사용하여 시간을 줄이는 것, 그리고 9가 나오는 경우 뒤쪽을 확인할 필요 없이 바로 넘어간느 방식으로 시간을 줄이는 것이 주요했다.

코드

def solution(number, k):
    answer = ''
    startidx = 0
    endidx = 0
    choose = len(number) - k
    
    while True:
        idx = -1
        endidx = len(number)-1 - (choose-1)
        
        if endidx < startidx or choose == 0:
            break
            
        elif startidx == endidx:
            answer += number[startidx:]
            break
            
        maxval = -1
        
        for i in number[startidx:endidx+1]:
            if maxval < int(i):
                maxval = int(i)
                
            if maxval == 9:
                break
                
        idx = number[startidx:endidx+1].find(str(maxval))
        answer += str(maxval)
        startidx += idx+1
        choose -= 1
        
    return answer

문제

programmers.co.kr/learn/courses/30/lessons/42860

풀이

속을 많이 썩인 문제였다. 해당 문제도 조건이 다양한 문제로, 문제에 제시되어 있긴 하지만, 조건이 다양하면 그리디를 사용해 보면 좋다는 생각을 갖고, 조건을 정리하면서, 세 가지 경우 중 최솟값을 구하면 된다는 생각이 들었다.

1. 조이스틱으로 오른쪽으로 쭉 가는 경우
2. 조이스틱으로 왼쪽으로 쭉 가는 경우
3. 조이스틱으로 오른쪽으로 가다가 왼쪽으로 가는 경우

해당 3가지 경우를 제외하고는 없기 때문에, 셋 중 최소인 값을 구해주면 좌우로 이동하는 횟수가 계산된다.

그리고, 위아래로 움직여야 하는 경우를 계산해야 하는데, 위아래로 움직이는 경우는 각 문자마다 위로 움직이는 경우, 아래로 움직이는 경우 중 작은 값을 이용하면 된다. 해당 값을 계산하기 위해, 알파벳 문자열을 선언한 뒤, 해당 인덱스까지 가기 위해 위로 눌러야하는 횟수와 아래로 눌러야 하는 횟수를 계산하여 둘 중 작은 값을 더해주었다.

해당 문제는 좌우로 움직이는 경우의 수 중 3번째 경우를 고려하지 않고 풀이를 진행하면서 막혔었는데, 갔다가 다시 오는 경우도 있다는 것을 판단하는 게 조금 어려울 수 있다. 하지만 해당 경우를 파악한다면 금방 풀 수 있는 문제로, 갔다 오는 경우 A가 가장 많은 위치에서 전진하는 방향을 돌려야 하기 때문에, A가 가장 많은 위치를 찾아서 돌려 주었다.

코드

def solution(name):
    answer = 0
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    
    for i in name:
        answer += min(alphabet.index(i), 26-alphabet.index(i))
        
    mov1 = len(name.rstrip("A")) - 1    # 앞으로만 가는경우
    mov2 = len(name.lstrip("A"))        # 뒤로만 가는경우
    
    idx = 0
    n = 1
    while True:
        tmp = name.find("A"*n)
        if tmp == -1:
            break
        idx = tmp
        n += 1                      # A가 가장 많은 곳 위치 찾기
        
    mov3 = 1000000000000
    
    if idx != 0 and idx != len(name.rstrip("A"))-1:
        # A가 가장 많은 곳이 맨앞 또는 맨 뒤쪽인 경우 배제
        mov3 = (idx-1)*2 + len(name) - (idx + n - 1)    
        # A가 가장 많은 곳을 기준으로 갔다가 돌아오는 경우
        
    answer += min(mov1, mov2, mov3)
    
    return answer

문제

programmers.co.kr/learn/courses/30/lessons/42862

풀이

프로그래머스 그리디 문제의 첫번째 문제이다. 간단하게 문제를 소개하면, 학생들 중 체육복을 도난한 학생과 여벌의 체육복을 갖고 있는 학생이 있는데, 바로 앞번호 또는 바로 뒷번호의 학생들에게만 빌려줄 수 있다. 수업을 들을 수 있는 학생의 최댓값을 구하는 문제이다.

조건이 복잡한만큼, 각 조건들을 하나하나 고려해가면서 구현해 주기만 하면, 그리디 알고리즘으로 문제를 해결할 수 있을 것으로 보인다. 따라서 조건들을 정리해 주었다. 이때, 우선적으로 고려되어야 할 조건들부터 차례대로 정리했다.

1. 여벌 체육복을 가져온 학생이 체육복을 도난했을 경우, 본인이 사용해야 하기 때문에 체육복을 빌려줄 수 없다.
2. 앞 번호 또는 뒷 번호 학생에게만 빌려줄 수 있다.

우선 여벌 체육복을 가져왔는데 잃어버린 학생들을 찾기 위해, set을 이용하여 lost와 reserve 배열을 합치고, 해당 set에서 각각 reserve와 lost를 빼서 새로운 lost_new와 reserve_new 리스트를 만든다. 이 과정은 reserve와 lost에 겹치는 학생들의 경우 자기가 사용해야 하기 때문에, 우선 배제해주는 과정이다.

이후 앞 번호 또는 뒷 번호 학생에게만 빌려주는 과정을 거치는데, 단순하게 reserve_new 리스트를 순환하면서 1 작은 값 또는 1 큰 값이 하나라도 있으면 그 값을 lost_new 리스트에서 빼내는 방식으로 알고리즘을 작성하였다.

해당 코드를 리뷰하면서 생각해 보면, 그다지 괜찮은 코드는 아닌 것 같다. 문제에서는 n이 30 이하라고 주어져서 시간 문제는 없긴 했지만, 만약 N이 커진다면 n^2만큼의 시간 복잡도에 pop의 n만큼의 시간 복잡도까지 합쳐져 n^3의 시간 복잡도가 나타나게 된다.

아이디어만 안다면 금방 풀 수 있는 문제였지만, 나중에는 시간 복잡도까지 고려해가면서 문제를 풀 필요가 있어 보인다.

코드

def solution(n, lost, reserve):
    answer = 0
    lost.sort()
    reserve.sort()
    
    lost_reserve_set = set(lost + reserve)
    lost_new = list(lost_reserve_set - set(reserve))
    reserve_new = list(lost_reserve_set - set(lost))
    
    for i in reserve_new:
        j = 0
        while j < len(lost_new):
            if i-1 == lost_new[j] or i+1 == lost_new[j]:
                lost_new.pop(j)
                break
            j = j+1
            
    answer = n - len(lost_new)
    
    return answer