geonyeongkim

인자로 문자열을 받습니다.

문자열에는 R 혹은 L만 존재합니다.

이때, R과 L의 숫자가 같도록 substring을 하여 가장 많은 substring 갯수를 구해야 합니다.

이 문제는, R과 L의 숫자를 바꿀수 있는 조건이 없습니다.

그렇기 때문에, 단순히 iterate를 돌며 R과 L의 갯수가 같을 때면 그냥 substring을 한다고 생각하시면 됩니다.

저는 아래와 같이 코드를 짰습니다.

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        r_cnt = 0
        l_cnt = 0
        res = 0

        for i in s:
            if i == "L":
                l_cnt += 1
            else:
                r_cnt += 1

            if l_cnt == r_cnt:
                res += 1
                l_cnt = 0
                r_cnt = 0
        return res

감사합니다.

List<int>를 인자로 받습니다.

이것은 각 돌멩이들의 무게입니다.

돌멩이들은 서로 부딪혀 작은 돌멩이로 만들 수 있습니다.

만약 7 돌멩이와 8돌멩이가 부딪히면 1 돌멩이로 되고, 7 돌멩이와 7 돌멩이가 부딪히면 두개는 사라집니다.

이런 규칙에서, 남은 돌멩이의 최소 무게를 구해야 합니다.

논리적으로는 돌멩이 무게가 큰것들끼리 서로 부딪히게 해서 무게를 줄여나가야 합니다.

그렇기 때문에, 저는 아래와 같이 풀었습니다.

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        sorted_stones = sorted(stones, reverse=True)
        for i in range(len(stones) -1):
            if sorted_stones[0] == sorted_stones[1]:
                sorted_stones[0] = 0
                sorted_stones[1] = 0
            else:
                sorted_stones[1] = sorted_stones[0] - sorted_stones[1]
                sorted_stones[0] = 0
            sorted_stones = sorted(sorted_stones, reverse=True)
        return sum(sorted_stones)

부딪히는 횟수는 최대 돌멩이 갯수 -1 입니다.
이유로는, 최소가 되려면 어찌됐든 한번씩은 부딪혀야 하기 때문입니다.

• 무게가 큰 순으로 정렬시킵니다.
• 정렬했기 때문에 첫번째와 두번째만 비교합니다.
  
  • 무게가 같다면 둘다 사라지기 때문에 첫번째, 두번째 자리의 값을 0으로 넣습니다.
  • 무게가 같지 않다면, 첫번째자리에는 0, 두번째자리에는 그 차이값을 넣습니다.
• 무게가 큰것들끼리만 부딪혀야 최소가 나오기 때문에, 마지막으로 다시 정렬시켜 반복되도록 합니다.

감사합니다.

List<List<int>를 인자로 받습니다.

인자는 각 사람이 A 도시로 가는데 드는 비용, B 도시로 가는데 드는 비용을 의미합니다.

예제를 설명드리면 첫번째 사람이 A로 가는데 드는 비용은 10, B로 가는데 드는 비용은 20입니다.

각 사람은 짝수로 들어오고, A도시와 B도시에 동일하게 사람을 가도록 해야합니다.

이 조건에서 가장 적은 돈으로 보내도록 구하는것이 문제입니다.

사람마다 모두 A, B로 가는 금액은 다를것이고, 금액의 차가 큰것부터 보내면 최소금액으로 모두 각 도시로 보낼 수 있을겁니다.

그렇기 때문에, 저의 경우는 아래와 같이 풀었습니다.

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        res = 0
        a_count = b_count = int(len(costs) / 2)
        for cost in costs:
            cost.append(abs(cost[0] - cost[1]))
        sorted_costs = sorted(costs, key=lambda x:x[2], reverse=True)

        for cost in sorted_costs:
            if a_count == 0:
                res += cost[1]
                continue
            if b_count == 0:
                res += cost[0]
                continue
            if cost[0] < cost[1]:
                a_count -= 1
                res += cost[0]
            else:
                b_count -= 1
                res += cost[1]
        return res

• 각 사람의 A, B의 cost의 차를 구해 append 시킨다.
• 차가 큰순으로 정렬시킨다.
• 정렬된 사람들을 iterate 돌며 적은 비용을 선택한다.
  
  • 단, A,B에 모두 동일한 사람수를 보내야 하기 때문에 count를 세어 A에 절반을 보냈다면 어쩔수 없이 B를 선택하도록 한다. (반대의 경우도 마찬가지)

감사합니다.

주어진 A 배열에서 K 번만큼 부호를 변경하여 최대 sumation을 만드는 문제입니다.

(단, 부호는 동일 값을 중복하여 해도됩니다.)

저는 아래와 같이 풀었습니다.

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        for i in range(K):
            if K == 0:
                break
            min_val = min(A)
            index = A.index(min_val)
            if min_val < 0:
                K -= 1
                A[index] = -min_val
            elif (K % 2) == 0:
                break
            else:
                K -= 1
                A[index] = -min_val
        return sum(A)

1. 배열에서 최솟값과 인덱스를 구해옵니다.

2. 음수라면 양수로 변경하여 배열의 값을 변경 및 K도 1 감소시킵니다.

3. 최솟값이 음수가 아니지만 K번이 짝수라면 현재 상태가 sumation 시 최대이기 때문에 연산을 멈춥니다.

4. 최솟값이 양수이고, K번도 홀수라면 그나마 작은 최솟값을 음수로 변경합니다.

감사합니다.

로봇이 commands에 있는 숫자만큼 이동합니다.

이동 중 첫 지점과 로봇의 위치의 두 점으로 이루어진 사각형이 생기며, 사각형이 최대일때의 면적을 구하는 문제입니다.

아래는 조건입니다.

• 시작 위치는 (0, 0)
• commands에서 -1은 turn right
• commands에서 -2은 turn left
• commands에서 -1, -2를 제외하고는 0이상 9이하만이 존재
• obstacles는 장애물 위치이며, 장애물이 있으면 로봇은 전진하지 못함

저의 경우는 아래와 같이 풀었습니다.

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:

        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        direction = 0

        # position (x, y)
        position = [0,0]
        res = 0
        obstacle_set = set(map(tuple, obstacles))

        for command in commands:
            if command == -1 :
                direction = (direction + 1) % 4
            elif command == -2:
                direction = (direction - 1) % 4
            else:
                for i in range(command):
                    if (dx[direction] + position[0], dy[direction] + position[1]) not in obstacle_set:
                        position[1] += dy[direction]
                        position[0] += dx[direction]
                        res = max(res, math.pow(position[0], 2) + math.pow(position[1], 2))
        return int(res)

일단, 동서남북으로 움직이기 위한 dx, dy 배열을 만들어 줍니다.

direction은 배열의 인덱스로 방향을 의미합니다.

그리고 저는 추가로 로봇의 현재 위치를 알기 위해 position 배열을 하나 만들었습니다.

그후는 commands를 이터레이션하며 -1, -2일때는 맞게 방향을 설정합니다.

그리고, 그 외 숫자가 나왔을 경우엔 숫자만큼 for문을 통하여 장애물이 있는지 없는지 체크하고 없다면 전진시킵니다.

전진 후에는 만들어진 사각형이 최대인지 max함수를 통해 구해줍니다.

사실, 여기서 계속 time 초과로 떨어졌었는데요.

그 이유는 위의 obstacle_set = set(map(tuple, obstacles)) 를 안해주었기 때문이였습니다......

장애물들을 list가 아닌 imutable한 tuple로 변환 후 set을 통하여 중복제거하여 불필요한 작업을 하지 않도록 해야합니다.

감사합니다.

이번 문제는 레몬에이드 판매 문제입니다.

레몬에이드는 각 5달러입니다.

인자로 받는 list는 고객이며, 숫자는 각 고객이 보유한 달러입니다. ( 5, 10, 20만 존재한다고 가정합니다. )

각 순서대로 레몬에이드를 끝까지 팔 수 있는지에 대한 문제입니다.

단, 판매 처음 거스름돈은 0달러인 채로 시작하게 됩니다.

아래는 제가 풀은 python code입니다.

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        change = [0, 0]

        for bill in bills:
            if bill == 5:
                change[0] += 1
            elif bill == 10:
                if change[0] > 0:
                    change[0] -= 1
                    change[1] += 1
                else: return False
            else:
                if change[0] > 0 and change[1] > 0:
                    change[0] -= 1
                    change[1] -= 1
                elif change[0] > 2:
                    change[0] -= 3
                else: return False
        return True

저의 경우는 거스름돈인 5달러와 10달러를 관리할 list를 초기에 생성합니다.

( list[0] - 5달러 갯수, list[1] - 10달러 갯수 로 가정하였습니다. )

그 후, 각 [5, 10, 20] 달러가 들어왔을때를 가정하여 문제를 풀었습니다.

1. 5달러인 경우

• 거스름돈이 5달러가 추가되어 list 0번째 값을 1 증가시킵니다.

2. 10 달러인 경우

• 거스름돈 5달러를 주어야하기 때문에 list의 0번째는 1 감소시키며, list의 2번째는 1 증가시킵니다.

• 거스름돈인 5달러가 없는 경우에는 실패로 간주하여 False를 반환합니다.

3. 20달러인 경우

• 먼저 10달러짜리와 5달러로 거스름이 가능하다면,  list의 0번째, 1번째 모두 1 감소시킵니다.

( 10달러를 받을 시 5달러로 거스름을 주어야 하기 때문에 10달러, 5달러 조합을 먼저 if 문에 걸리게 해야 합니다. )

• 5달러짜리로만 거스름이 가능하다면, list의 0번째를 3 감소시킵니다.

• 거스름이 불가능하다면 실패로 간주하여 False를 반환합니다.

거스름이 가능한지에 대한 문제로 배열에 20달러를 보유한 케이스는 제외하였습니다.

감사합니다.

이번 문제는 두개의 int 리스트를 인자로 받습니다.

첫번째 인자의 의미는 각 아이들이 만족할 수 있는 쿠키 크기입니다.

두번째는 인자의 의미는 현재 가지고 있는 쿠키입니다.

첫번째 예시를 본다면, 3명의 아이들은 각 1, 2, 3의 쿠키를 원합니다.

하지만 현재 쿠키는 1, 1 만 가지고 있어 아이 한명을 충족시킬 수 있습니다.( 그래서 output이 1입니다. )

두번째 예시를 본다면, 2명의 아이들은 각 1, 2의 쿠키를 원하며

쿠키는 1, 2, 3을 가지고 있어 두명의 아이를 모두 충족시킬 수 있습니다.( 그래서 output은 2입니다. )

저의 경우는 아래와 같이 풀었습니다.

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        res = 0
        idx = 0

        for greedy in g:
            for j in range(idx, len(s), 1):
                if greedy <= s[j]:
                    res += 1
                    idx = j+1
                    break
        return res

아이들의 원하는 쿠키를 가지고 있는지 체크를 하며 있다면, 다음 아이로 대상을 바꾸도록 하였습니다.

단, 많은 아이를 충족하여야 하기 때문에 욕심이 적은 아이에게는 딱 맞는 쿠키를 주어야 합니다.

그렇기 때문에, 체크하기 전 두 리스트를 sorting 작업을 추가하였습니다.

감사합니다.

s 문자열이 t 문자열의 subsequence인지 여부를 반환하는 문제입니다.

subsequence의 경우에는 문자의 연속성 또한 맞아야 합니다.

예시로 abcde 문자열에서 ace는 subsequence가 맞지만, aec는 맞지 않다고 나와있습니다.
이것은, 연속성이 맞지 않기 때문입니다.

그렇기 때문에, 단순히 for문을 통해 문자 비교를 하고 동일한 문자를 찾는다면, 다음 문자부터 재탐색하여 찾으시면 됩니다.

만약, 탐색이 되지 않는다면 주어진 문자열은 subsequence가 아닌 것으로 판명되어집니다.

아래는 제가 풀은 python code입니다.

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        index = 0
        for s_char in s:
            flag = True
            for t_idx in range(index, len(t), 1):
                if t[t_idx] == s_char:
                    index = t_idx +1
                    flag = False
                    break
            if flag:
                return False
        return True

감사합니다.

주어진 int 배열은 하나의 주가이며, 이 주가에서 얻을 수 있는 최대 수익을 출력하는것이 문제입니다.

낮은가격에 사 높은 가격에 판다면 이익을 얻습니다.

그렇기 때문에, 현재 시점의 주가와 다음 시가의 주가를 비교하여 차익이 있는 것들만 sumation하면 되는 문제입니다.

(차익이 난다면 바로 팔기때문에 greedy 분류의 문제입니다.)

아래는 제가 푼 python 코드 입니다.

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        prices_len = len(prices)
        for i in range(0, prices_len, 1):
            if i+1 < prices_len and prices[i] < prices[i+1]:
                res += (prices[i+1] - prices[i])
        return res

if __name__ == '__main__':
    s = Solution()
    s.maxProfit([7,1,5,3,6,4])

저의 경우, 배열의 인덱스를 넘지 않기 위해 if 문에 다음 인덱스가 있는지의 체크가 추가되었습니다.

감사합니다.