블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 1996. The Number of Weak Characters in the Game를 풀고 작성한 글입니다.

문제

요구사항

You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array properties where properties[i] = [attacki, defensei] represents the properties of the ith character in the game.

A character is said to be weak if any other character has both attack and defense levels strictly greater than this character's attack and defense levels. More formally, a character i is said to be weak if there exists another character j where attackj > attacki and defensej > defensei.

Return the number of weak characters.

제약사항

• 2 <= properties.length <= 105
• properties[i].length == 2
• 1 <= attacki, defensei <= 105

풀이

접근법

정렬을 활용한 두 가지 풀이가 존재한다.

1. 내부 정렬 메서드 사용
2. 계수 정렬 사용

첫 번째 풀이

먼저 아래와 같이 내부 정렬 메서드인 sort() 를 사용해서 문제를 해결할 수 있다.

먼저 attack 을 기준으로 내림차순 정렬하고 만약 동등한 경우 defense 를 기준으로 오름차순을 정렬한다.

이렇게 할 경우 동일한 attack 값에 대해 defense 값이 달라지는 경우를 추가적으로 고민하지 않아도 무조건적으로 반복문을 수행하며 현재의 defense 값이 만약 이전의 가장 큰 defense 값보다 작을 경우 무조건 attack 값과 defense 값 모두 작은 경우이기 때문에 셈을 하면 되고 클 경우 이전의 가장 큰 defense 값을 그 값으로 변경하면 된다.

def solution(properties: list[list[int]]) -> int:
    properties.sort(key=lambda x: (-x[0], x[1]))
    maximum_defense: int = properties[0][1]

    answer: int = 0
    for _, defense in properties:
        if defense < maximum_defense:
            answer += 1 
        else:
            maximum_defense = defense

    return answer

두 번째 풀이

다음으로 계수 정렬(Count Sort)를 사용해서 문제를 해결할 수 있다.

주어진 입력값에서 가장 큰 attack 값을 길이로 가진, 해당 attack 값을 인덱스로 하고 값을 defense 로 하는 새로운 배열을 생성한다.

이때 중요한 점은 각 attack 값을 인덱스로 하는 요소를 가장 큰 defense 값으로 해야 한다는 점이다.

이후 배열에 대해 반복문을 가장 마지막 요소부터 역으로 수행하며 만약 현재의 배열 요소가 바로 다음의 배열 요소보다 클 경우 이를 현재의 배열 요소로 바꾼다.

마지막으로 다시 입력값인 properties 배열에 대해 반복문을 수행하며 만약 현재의 attack 값의 인덱스 요소보다 하나 큰 값의 요소인 defense 값이 현재의 defense 값보다 클 경우, 다시 말해 attack 값과 defense 값이 모두 더 작을 경우 셈을 한다.

def solution(properties: list[list[int]]) -> int:
    maximum_attack: int = 0
    for attack, _ in properties:
        if attack > maximum_attack:
            maximum_attack = attack

    bucket: list[int] = [ 0 for _ in range(maximum_attack+2) ]
    for attack, defense in properties:
        if bucket[attack] < defense:
            bucket[attack] = defense

    for idx in range(maximum_attack+1, 0, -1):
        if bucket[idx] > bucket[idx-1]:
            bucket[idx-1] = bucket[idx]

    answer: int = 0
    for attack, defense in properties:
        if defense < bucket[attack+1]:
            answer += 1

    return answer

시간 복잡도

첫 번째 풀이

첫 번째 풀이의 경우 내부 정렬 메서드를 사용하기 때문에 결과적으로 시간 복잡도는 O(NlogN)이다.

두 번째 풀이

두 번째 풀이의 경우 주어진 입력값 N에 대한 반복문 수행과 더불어 최대 attack 값보다 하나 큰 만큼의 크기를 가진 배열을 생성하고 반복문을 수행해야 하기 때문이 시간 복잡도는 O(N+K)이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 637. Average of Levels in Binary Tree를 풀고 작성한 글입니다.

문제

요구사항

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10^-5 of the actual answer will be accepted.

제약사항

• The number of nodes in the tree is in the range [1, 10^4] .
• -2^31 <= Node.val <= 2^31 - 1

풀이

접근법

총 두 가지 풀이가 존재한다.

1. 전위 탐색범(Preorder Traverse)을 활용하여 재귀 함수(Recursion Function)를 호출하는 방법
2. 덱큐(Dequeue)를 활용하여 너비 우선 탐색(Breadth First Search)을 수행하는 방법

첫 번째 풀이

먼저 아래와 같이 재귀 함수를 호출해서 문제를 해결할 수 있다.

def solution(root: "TreeNode") -> list[float]:
    def traverse(depth: int, node: TreeNode) -> None:
        nonlocal tree
        if node:
            if depth in tree:
                tree[depth].append(node.val)
            else:
                tree[depth] = [node.val]

            traverse(depth=depth+1, node=node.left)
            traverse(depth=depth+1, node=node.right)


    tree: dict[int, int] = {}
    traverse(depth=0, node=root)

    answer: list[float] = [ 0 for _ in range(len(tree)) ]
    for index, value in tree.items():
        answer[index] = sum(value) / len(value)

    return answer

두 번째 풀이

다음으로 collections 내장 모듈에 있는 deque 객체를 활용하여 BFS로 문제를 해결할 수 있다.

def solution(root: "TreeNode") -> list[float]:
    from collections import deque


    queue: deque = deque([root])
    answer: list[float] = []
    while queue:
        same_level_count = same_level_length = len(queue)
        same_level_sum: int = 0

        while same_level_count > 0:
            node: TreeNode = queue.popleft()            
            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

            same_level_sum += node.val
            same_level_count -= 1

        answer.append(same_level_sum / same_level_length)

    return answer  

이때 유의할 점은 중첩된 내부 while 문에서 처음에 popleft() 메서드 호출로 인해 queue 객체가 비었을 때 그 외부 while 문의 조건에 위배되어 즉시 반복문이 중단될 줄 알았는데 우선적으로 실행 중이던 반복문은 한 번 다 수행한 뒤에 종료가 된다는 점이다.

그래서 popleft() 메서드 호출로 인해 객체가 비었어도 그 다음 라인에 node 객체에 좌측 혹은 우측에 자식 노드가 존재한다면 다시 객체에 append() 메서드 호출을 통해 추가가 되기 때문에 반복문이 중단되지 않고 원하는 대로 작동한다.

일례로 아래 코드의 경우 "Converted" 까지만 출력하고 프로그램이 종료되는 것이 아닌 "After" 까지 출력한 뒤에 프로그램이 종료된다.

flag: bool = True
while flag:
    print("Before")

    if flag:
        print("Converted")
        flag = False

    print("After")

시간 복잡도

첫 번째 풀이와 두 번째 풀이 모두 주어진 트리의 노드 개수만큼만 반복문을 수행하면 되기 때문에 시간 복잡도는 O(N)이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 869. Reordered Power of 2를 풀고 작성한 글입니다.

문제

요구사항

You are given an integer n . We reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this so that the resulting number is a power of two.

제약사항

• 1 <= n <= 10^9

풀이

접근법

총 두 가지 풀이가 존재한다.

1. 범위를 한정한 뒤 정렬을 활용한 풀이
2. 비트 연산자를 활용한 풀이

첫 번째 풀이

아래와 같이 내장 모듈 math 내에 있는 log() 함수를 활용하여 반복문의 범위를 한정하고 해당 범위 내로 반복문을 수행하며 sorted() 내장 함수를 통해 두 수를 비교해서 2의 제곱수로 만들 수 있는지 여부를 판별한다.

def solution(n: int) -> bool:
    from math import log


    length: int = len(str(n))
    start: int = int(log(10 ** (length - 1), 2))
    end: int = int(log(10 ** length, 2))

    for number in range(start, end + 1):
        if sorted(str(n)) == sorted(str(2 ** number)):
            return True

    return False    

두 번째 풀이

비트 연산자를 활용해서 문제를 풀 수도 있다.

최대 9자리까지인 입력값에 따라 2의 배수 또한 최대 2^30까지만 따지면 되기 때문에 2^0부터 하나씩 비트 연산을 통해서 비교하면 된다.

이때 해당 수의 개수를 따져 비교하면 순서에 상관 없이 비교할 수 있다.

def solution(n: int) -> bool:
    numbers: dict[str, int] = {}
    for number in str(n):
        if number in numbers:
            numbers[number] += 1

        else:
            numbers[number] = 1


    for power in range(30):
        target: int = 1 << power
        target_numbers: dict[str, int] = {}
        for number in str(target):
            if number in target_numbers:
                target_numbers[number] += 1

            else:
                target_numbers[number] = 1

        if numbers == target_numbers:
            return True


    return False    

시간 복잡도

첫 번째 풀이의 경우 sorted() 메서드를 활용하기 때문에 시간 복잡도는 O(NlogN)이고 두 번째 풀이의 경우 O(N)이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 383. Ransom Note를 풀고 작성한 글입니다.

문제

요구사항

Given two strings ransomNote and magazine , return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote .

제약사항

• 1 <= ransomNote.length, magazine.length <= 10^5
• ransomNote and magazine consist of lowercase English letters.

풀이

접근법

해시 테이블 -파이썬에서의 딕셔너리- 을 사용해서 문자를 키로 개수를 값으로 저장한 다음 이를 비교하여 문제를 해결할 수 있다.

나의 풀이

입력값 ransomNote 를 기준으로 해시 테이블을 만들면 아래와 같이 문제를 해결할 수 있다.

def solution(ransomNote: str, magazine: str) -> bool:
    characters: dict[str, int] = {}
    for character in ransomNote:
        if character in characters:
            characters[character] += 1
        else:
            characters[character] = 1

    for character in magazine:
        if character in characters and characters[character] > 0:
            characters[character] -= 1

    return True if sum(characters.values()) == 0 else False

다른 풀이

입력값 magazine 을 기준으로 해시 테이블을 만들면 조금 더 단순하게 문제를 해결할 수 있다.

def solution(ransomNote: str, magazine: str) -> bool:
    characters: dict[str, int] = {}
    for character in magazine:
        if character in characters:
            characters[character] += 1
        else:
            characters[character] = 1

    for character in ransomNote:
        if character not in characters or characters[character] == 0:
            return False
        else:
            characters[character] -= 1

    return True

시간 복잡도

해시 테이블 조회의 경우 상수 시간이기 때문에 시간 복잡도는 최종적으로 반복문 수행에 따라 O(N)이다.

이때 N은 두 입력값 중 길이가 더 긴 문자열에 대한 길이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 2388. Change Null Values in a Table to the Previous Value를 풀고 작성한 글입니다.

문제

테이블

Table: CoffeeShop

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| drink       | varchar |
+-------------+---------+
id is the primary key for this table.
Each row in this table shows the order id and the name of the drink ordered. Some drink rows are nulls.

요구사항

Write an SQL query to replace the null values of drink with the name of the drink of the previous row that is not null . It is guaranteed that the drink of the first row of the table is not null .

Return the result table in the same order as the input.

풀이

접근법

총 세 가지 방법을 통해 문제를 해결할 수 있다.

1. LEFT JOIN 구와 GROUP BY 구를 활용한 방법
2. WITH 구를 활용하여 ROW_NUMBER() 윈도우 함수(Window Function)를 사용한 부분을 임시 테이블로 만드는 방법
3. WITH RECURSIVE 구를 활용한 방법

첫 번째 풀이

ROW_NUMBER() 윈도우 함수를 활용하여 해당 부분을 LEFT JOIN 구의 조건으로 사용하고 이후 GROUP BY 구를 통해 가장 최신의 값을 얻어 내서 문제를 해결한다.

SELECT
    id,
    IFNULL(drink, SubTable_drink) AS drink
FROM (
    SELECT
        WithRowNum.id,
        WithRowNum.drink,
        MAX(SubTable.row_num) AS latest_one,
        SubTable.drink AS SubTable_drink
    FROM (
        SELECT
            ROW_NUMBER() OVER() AS row_num,
            id,
            drink
        FROM CoffeeShop
    ) AS WithRowNum
    LEFT JOIN (
        SELECT
            ROW_NUMBER() OVER() AS row_num,
            id,
            drink
        FROM CoffeeShop
    ) AS SubTable
    ON (
        WithRowNum.drink IS NULL
        AND
        WithRowNum.row_num > SubTable.row_num
        AND
        SubTable.drink IS NOT NULL
    )
    GROUP BY WithRowNum.id
) AS Result;

두 번째 풀이

앞선 첫 번째 풀이에서 공통으로 사용되는 테이블을 WITH 구를 활용하여 임시 테이블로 만들어서 사용한다.

WITH WithRowNum (row_num, id, drink) AS (
    SELECT
        ROW_NUMBER() OVER() AS row_num,
        id,
        drink
    FROM CoffeeShop
)

SELECT
    id,
    IFNULL(drink, SubTable_drink) AS drink
FROM (
    SELECT
        WithRowNum.id,
        WithRowNum.drink,
        MAX(SubTable.row_num) AS latest_one,
        SubTable.drink AS SubTable_drink
    FROM WithRowNum
    LEFT JOIN WithRowNum AS SubTable
    ON (
        WithRowNum.drink IS NULL
        AND
        WithRowNum.row_num > SubTable.row_num
        AND
        SubTable.drink IS NOT NULL
    )
    GROUP BY WithRowNum.id
) AS Result;

세 번째 풀이

WITH RECURSIVE 구를 활용하여 내부적으로 JOIN 구를 재귀적으로 수행하게 해 문제를 해결한다.

WITH RECURSIVE WithRowNum (row_num, id, drink) AS (
    SELECT
        ROW_NUMBER() OVER() AS row_num,
        id,
        drink
    FROM CoffeeShop
), Result (row_num, id, drink) AS (
    SELECT
        row_num,
        id,
        drink
    FROM WithRowNum
    WHERE row_num = 1
    UNION ALL
    SELECT
        WithRowNum.row_num,
        WithRowNum.id,
        IFNULL(WithRowNum.drink, Result.drink) AS drink
    FROM Result
    JOIN WithRowNum
    ON Result.row_num = WithRowNum.row_num - 1
)

SELECT id, drink
FROM Result;

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 326. Power of Three를 풀고 작성한 글입니다.

문제

요구사항

Given an integer n , return true if it is a power of three. Otherwise, return false .

An integer n is a power of three, if there exists an integer x such that n == 3^x .

제약사항

• -2^31 <= n <= 2^31 - 1

풀이

접근법

총 두 가지 풀이가 존재한다.

1. 반복문을 활용한 풀이
2. 입력값의 한계를 통해 최대값을 구하여 접근하는 풀이

틀린 풀이

풀이를 살펴보기에 앞서 우선 쉽게 틀릴 수 있는 풀이를 먼저 살펴보려 한다.

def solution(n: int) -> bool:
    from math import log


    return True if n > 0 and int(log(n, 3)) == log(n, 3) else False 

위와 같이 단순하게 내장 모듈 math 내에 있는 log 메서드를 활용하여 정수로 변환한 값과 동일한지 확인하는 로직으로 문제를 풀 경우 n이 243일 때 False 를 반환한다.

243은 3^5의 값으로 명확하게 3의 제곱수인데 어째서 False 를 반환한 것일까?

이는 부동 소수점 때문에 발생하는 정밀도 문제다.

관련해서 자세한 부분은 [글또 7기] 243은 3의 제곱수가 아니라는데요?에서 확인 가능하다.

결론만 말하자면 이를 해결하려면 머신 입실론(Machine Epsilon) 값을 추가로 활용해야 한다.

아래와 같이 sys 모듈에 있는 float_info 중 epsilon 값을 불러와 사용할 수 있다.

>>> import sys
>>> sys.float_info.epsilon

2.220446049250313e-16

LeetCode 내에서는 sys 모듈을 사용할 수 없기 때문에 0.0000000000001과 같이 임의적으로 값을 할당해야 한다.

첫 번째 풀이

간단하게 반복문을 통해서도 문제를 풀 수 있다.

def solution(n: int) -> bool:
    if n <= 0:
        return False
    else:
        while (n % 3 == 0):
            n //= 3

        return n == 1

두 번째 풀이

입력값의 한계를 알기 때문에 해당 입력값의 최대값을 기준으로 나올 수 있는 최대 로그값을 구한다.

그리고 이를 기준으로 실제 주어진 입력값을 나누어 나머지가 0인지 확인하면 된다.

def solution(n: int) -> bool:
    from math import log


    max_n: int = (2 ** 31) - 1
    max_x: int = 3 ** int(log(max_n, 3))
    return True if n > 0 and max_x % n == 0 else False   

시간 복잡도

각각의 풀이에 대한 시간 복잡도는 아래와 같다.

첫 번째 풀이

반복문을 수행하지만 절반 이상씩 횟수가 줄어들기 때문에 시간 복잡도는 O(logN)이다.

두 번째 풀이

상수 시간으로 시간 복잡도는 O(1)이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 342. Power of Four를 풀고 작성한 글입니다.

문제

요구사항

Given an integer n , return true if it is a power of four. Otherwise, return false .

An integer n is a power of four, if there exists an integer x such that n == 4^x .

제약사항

• -2^31 <= n <= 2^31 - 1

풀이

접근법

총 네 가지 풀이가 존재한다.

1. 로그 함수를 활용한 풀이
2. 입력값의 한계를 통해 최대값을 구하여 접근하는 풀이
3. 반복문을 활용한 풀이
4. 비트 연산을 활용한 풀이

첫 번째 풀이

내장 모듈 math 의 log 메서드를 사용하는 방법이 있다.

이때 n 은 0보다 커야 한다.

def solution(n: int) -> bool:
    from math import log


    return True if n > 0 and int(log(n, 4)) == log(n, 4) else False   

해당 풀이의 문제점은 이후에 [ 알고리즘 ] LeetCode 326. Power of Three에서 다루겠지만 부동 소수점 때문에 정확도 문제가 발생할 수 있다는 점이다.

따라서 해당 방법을 조금 더 제대로 사용하기 위해서는 머신 입실론(Machine Epsilon) 값을 추가해줘야 한다.

두 번째 풀이

입력값 정수 n에 한계가 존재하기 때문에 그 한계 내에서 만들 수 있는 가장 큰 4의 제곱수 n을 구한뒤 입력되는 값 n을 그 최대값에 나눴을 때 반환되는 나머지가 0인지 확인한다.

이때 유의할 점은 4는 곧 2의 제곱수이기 때문에 2의 제곱수인 입력값을 해당 최대값에 나눠도 나머지가 0이 나온다.

따라서 3으로 나눴을 때 나머지가 1인지 한번 더 확인을 해서 2의 제곱수지만 4의 제곱수가 아닌 경우의 수를 제거한다.

def solution(n: int) -> bool:
    from math import log


    max_x: int = (2 ** 31) - 1
    max_n: int = 4 ** int(log(max_x, 4))
    return True if n > 0 and max_n % n == 0 and n % 3 == 1 else False   

세 번째 풀이

간단하게 반복문을 통해서도 문제를 풀 수 있다.

나머지가 0이 아닐 때까지 반복하면서 4로 나눈 값의 몫으로 재할당하면 된다.

이때 최종적으로 값이 1인 경우 4의 제곱수이다.

def solution(n: int) -> bool:
    if n <= 0:
        return False

    else:
        while (n % 4 == 0):
            n //= 4

        return n == 1   

네 번째 풀이

끝으로 비트 연산을 활용해서 문제를 풀 수 있다.

주어진 값에서 1을 뺀 것과 AND 연산을 할 경우 무조건 0이 나와야 우선 2의 제곱수다.

왜냐하면 2의 제곱수는 십진수 8의 값이 이진수 1000(2)와 같이 가장 큰 자리의 값이 1이고 나머지는 0이기 때문에 해당 수에 1을 빼면 0111(2)과 같이 나머지가 전부 1이 되어서 결국 AND 연산의 결과가 무조건 0이기 때문이다.

이후 입력값을 3으로 나누었을 때 나머지가 1이면 4의 제곱수이기 때문에 해당 조건을 하나 더 추가해줘서 2의 제곱수인데 4의 제곱수가 아닌 경우를 제거한다.

def solution(n: int) -> bool:
    return True if n > 0 and n & (n - 1) == 0 and n % 3 == 1 else False

시간 복잡도

각각의 풀이에 대한 시간 복잡도는 아래와 같다.

첫 번째 풀이

시간 복잡도는 상수 시간으로 시간 복잡도는 O(1)이다.

두 번째 풀이

첫 번째 풀이와 마찬가지로 상수 시간으로 시간 복잡도는 O(1)이다.

세 번째 풀이

반복문을 수행할 때 절반 이상씩 줄어들기 때문에 시간 복잡도는 O(logN)이다.

네 번째 풀이

상수 시간으로 시간 복잡도는 O(1)이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ 백준 ] 1874번: 스택 수열을 풀고 작성한 글입니다.

문제

설명

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

풀이

접근법

나의 풀이

접근법을 토대로 문제를 풀면 아래와 같다.

Big-O

주어진 수열의 길이 N만큼 반복분을 수행해야 하기 때문에 시간 복잡도는 O(N)이다.

반복문 내부에서 추가적인 반복문이 수행되더라도 유의미한 결과를 미치지 못하고 O(N^2)보다는 작기 때문에 O(N)이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 13. Roman to Integer를 풀고 작성한 글입니다.

문제

요구사항

Roman numerals are represented by seven different symbols: I , V , X , L , C , D and M .

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII , which is simply X + II . The number 27 is written as XXVII , which is XX + V + II .

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII . Instead, the number four is written as IV . Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX . There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

제약사항

• 1 <= s.length <= 15
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M') .
• It is guaranteed that s is a valid roman numeral in the range [1, 3999] .

풀이

접근법

주어진 로마 숫자 문자열을 뒤집어서 계산하면 된다.

나의 풀이

접근법을 토대로 문제를 해결하면 아래와 같다.

def solution(s: str) -> str:
    answer: int = 0
    rome_to_integer: dict[str, int] = {
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000
    }
    is_minus: bool = False
    previous_symbol: str = ""
    for symbol in s[::-1]:
        if symbol == "I":
            if previous_symbol == "V" or previous_symbol == "X":
                is_minus = True

        elif symbol == "X":
            if previous_symbol == "L" or previous_symbol == "C":
                is_minus = True

        elif symbol == "C":
            if previous_symbol == "D" or previous_symbol == "M":
                is_minus = True

        if is_minus:
            answer -= rome_to_integer[symbol]
        else:
            answer += rome_to_integer[symbol]

        is_minus = False
        previous_symbol = symbol


    return answer    

다른 풀이

아래와 같이 더 간단하게 문제를 해결할 수 있다.

로마 숫자 문자열을 뒤집어서 하나씩 확인할 때 이전 로마 숫자보다 현재의 로마 숫자가 더 작은 경우 빼고 그렇지 않은 경우 더해주면 된다.

def solution(command: str) -> str:
    rome_to_integer: dict[str, int] = {
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000
    }
    reversed_s: str = s[::-1]
    answer: int = rome_to_integer[reversed_s[0]]
    for idx in range(1, len(reversed_s)):
        current_value: int = rome_to_integer[reversed_s[idx]]
        previous_value: int = rome_to_integer[reversed_s[idx-1]]

        if current_value < previous_value:
            answer -= current_value
        else:
            answer += current_value

    return answer    

시간 복잡도

유효한 로마숫자 표현은 최대 3999까지이고 이미 정해진 이때도 결국 반복문은 총 10회 돌기 때문에 시간 복잡도는 상수 시간으로 O(1)이다.

그 아래의 경우 무조건 10보다 적게 반복문이 반복되기 때문이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 1678. Goal Parser Interpretation를 풀고 작성한 글입니다.

문제

요구사항

You own a Goal Parser that can interpret a string command . The command consists of an alphabet of "G" , "()" and/or "(al)" in some order. The Goal Parser will interpret "G" as the string "G" , "()" as the string "o" , and "(al)" as the string "al" . The interpreted strings are then concatenated in the original order.

Given the string command , return the Goal Parser's interpretation of command .

제약사항

• 1 <= command.length <= 100
• command consists of "G" , "()" , and/or "(al)" in some order.

풀이

접근법

정규표현식을 사용해서 문제를 풀 수 있다.

이때 [] 를 사용할 경우 내부에 있는 문자들 중에 하나여야 한다는 의미이기 때문에 주의해야 한다.

따라서 () 를 사용해서 그룹으로 만들어주거나 아니면 개별적으로 단어를 입력하면 된다.

이때 몇몇 특수문자의 경우 위에 사용된 것처럼 아예 다른 의미를 가지기 때문에 이스케이프 문자( \ )를 사용해서 해당 문자가 어떤 문법적 의미로서 사용된 것이 아닌 문자 자체로 사용된 것임을 선언해줘야 한다.

나의 풀이

접근법을 토대로 문제를 해결하면 아래와 같다.

def solution(s: str) -> str:
    import re


    return re.sub(r"\(\)", "o", re.sub("\(al\)", "al", command))

다른 풀이

아래와 같이 해시 테이블 -파이썬에서의 딕셔너리- 을 사용해서 문제를 해결할 수도 있다.

def solution(command: str) -> str:
    answer: str = ""
    converted_table: dict[str, str] = { "()": "o", "(al)": "al" }

    for character in command:
        if character == "G":
            answer += character

        elif character == "(":
            consecutive_word: str = "("

        elif character == ")":
            consecutive_word += character
            answer += converted_table[consecutive_word]
            consecutive_word = ""

        else:
            consecutive_word += character

    return answer

좀 더 견고한 풀이는 아래와 같다.

단어가 더 추가되면 해시 테이블에 키와 값만 추가해주면 되기 때문이다.

def solution(command: str) -> str:
    answer: str = ""
    consecutive_word: str = ""
    converted_table: dict[str, str] = {"()": "o", "(al)": "al", "G": "G"}

    for character in command:
        consecutive_word += character
        if consecutive_word in converted_table:
            answer += converted_table[consecutive_word]
            consecutive_word = ""

    return answer

시간 복잡도

길이가 N인 문자열에 대해 반복문을 그 길이만큼 수행하면 되기 때문에 시간 복잡도는 O(N)이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 2372. Calculate the Influence of Each Salesperson을 풀고 작성한 글입니다.

문제

테이블

Table: Salesperson

+----------------+---------+
| Column Name    | Type    |
+----------------+---------+
| salesperson_id | int     |
| name           | varchar |
+----------------+---------+
sales_person_id is the primary key for this table.
Each row in this table shows the ID of a salesperson and the price of one unit.

Table: Customer

+----------------+------+
| Column Name    | Type |
+----------------+------+
| customer_id    | int  |
| salesperson_id | int  |
+----------------+------+
customer_id is the primary key for this table.
salesperson_id is a foreign key from the Salesperson table.
Each row in this table shows the ID of a customer and the ID of the salesperson 

Table: Sales

+-------------+------+
| Column Name | Type |
+-------------+------+
| sale_id     | int  |
| customer_id | int  |
| price       | int  |
+-------------+------+
sale_id is the primary key for this table.
customer_id is a foreign key from the Customer table.
Each row in this table shows ID of a customer and the price they paid for the sale with sale_id.

요구사항

Write an SQL query to report the sum of prices paid by the customers of each salesperson. If a salesperson does not have any customers, the total value should be 0 .

Return the result table in any order.

풀이

접근법

Salesperson 테이블을 기준으로 Customer 테이블을 LEFT JOIN 구를 활용해 수평 연결하고 다시 연결된 Customer 테이블을 기준으로 Sales 테이블을 LEFT JOIN 구를 활용해 수평 연결하면 된다.

GROUP BY 구를 활용하여 salesperson_id 필드를 기준으로 필드를 묶고 SUM() 집계 함수를 사용하여 price 테이블의 합계를 구하면 되는데 이때 IFNULL() 함수를 사용해 NULL 값을 반환하는 경우에 대해 0 으로 치환하면 된다.

나의 풀이

접근법을 토대로 풀면 아래와 같다.

SELECT
    Salesperson.salesperson_id,
    Salesperson.name,
    IFNULL(SUM(Sales.price), 0) AS total
FROM Salesperson
LEFT JOIN Customer
USING (salesperson_id)
LEFT JOIN Sales
USING (customer_id)
GROUP BY Salesperson.salesperson_id;

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ 백준 ] 11660번: 구간 합 구하기 5를 풀고 작성한 글입니다.

문제

설명

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

풀이

접근법

이차원 배열에 대한 접두사 합계(Prefix Sum)을 구하면 된다.

일차원 배열과 다른 점은 (2, 2) ~ (3, 4)까지의 합을 구한다고 했을 때 (2, 1), (1, 3) 같은 값들은 합에 들어가지 않는다는 것이다.

따라서 단순히 선형으로 모든 수의 합을 쭉 구하면 문제를 풀 수 없다.

나의 풀이

접근법을 토대로 문제를 풀면 아래와 같다.

import sys


input = sys.stdin.readline
N, M = map(int, input().split())
array: list[int] = list(map(int, input().split()))
dp: list[int] = [ [0] * (N+1) for _ in range(N+1) ]

for i in range(N):
    for j in range(N):
        dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + array[i][j]

for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    print(dp[x2][y2] - (dp[x2][y1-1] + dp[x1-1][y2]) + dp[x1-1][y1-1])

Big-O

길이가 N인 배열에 대해 (N+1) * (N+1) 길이의 이차원 배열을 생성한 뒤 반복문을 수행하며 합을 미리 계산해서 문제를 해결했기 때문에 시간 복잡도는 O(N)이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 709. To Lower Case를 풀고 작성한 글입니다.

문제

요구사항

Given a string s , return the string after replacing every uppercase letter with the same lowercase letter.

제약사항

• 1 <= s.length <= 100
• s consists of printable ASCII characters.

풀이

접근법

간단하게 문자열 객체에 사용할 수 있는 내장 메서드인 lower() 함수를 사용하면 된다.

나의 풀이

접근법을 토대로 문제를 해결하면 아래와 같다.

def solution(s: str) -> str:
    return s.lower()

다른 풀이

문자 사이의 차이를 계산하여 문자를 해결할 수도 있다.

ASCII 문자가 주어지기 때문에 영어 소문자가 대문자보다 이후에 나온다.

따라서 소문자 a와 대문자 A의 ASCII 코드 상에서의 차이를 계산한 다음 만약 주어진 문자열의 개별 문자가 대문자일 경우 그 차이만큼 더해주면 된다.

소스 코드는 아래와 같다.

def solution(s: str) -> str:
    difference: int = ord("a") - ord("A")
    return "".join([
        chr(difference + ord(character))
        if ord(character) >= ord("A") and ord(character) <= ord("Z")
        else character
        for character in s
    ])

시간 복잡도

주어진 문자열 s 의 길이 N만큼 반복문을 수행해서 리스트를 만든 다음 이를 문자열로 반환하기 때문에 시간 복잡도는 O(N)이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ 백준 ] 11659번: 구간 합 구하기 4를 풀고 작성한 글입니다.

문제

설명

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

풀이

접근법

접두사 합계(Prefix Sum) 알고리즘을 활용해서 문제를 해결할 수 있다.

이때 제시되는 i번째 수부터 j번째 수가 인덱스와 동일하게 0부터 시작하는 것이 아닌 1부터 시작하기 때문에 최종적으로 계산 결과를 반환할 때 주의해야 한다.

나의 풀이

접근법을 토대로 문제를 풀면 아래와 같다.

import sys


input = sys.stdin.readline
N, M = map(int, input().split())
numbers: list[int] = list(map(int, input().split()))
dp: list[int] = [0]
for idx, number in enumerate(numbers):
    dp.append(dp[idx] + number)

for _ in range(M):
    i, j = map(int, input().split())
    print(dp[j] - dp[i-1])

다른 풀이

추가적으로 아래와 같이 내부 intertools 모듈 내에 있는 accumulate() 함수를 사용하여 더 쉽게 누적 합을 저장할 수 있다.

이때 accumulate() 내장 함수의 경우 첫 번째 매개변수로 이터러블(Iterable)한 객체를, 두 번째 매개변수로 연산의 종류를 -이때 기본값은 operator 모듈의 add() 함수- 마지막 매개변수로는 초기값 -이때 기본값은 None - 을 설정해줄 수 있다.

예를 들어 accumulate(iterable, function, inital) 와 같은 형태다.

import sys
from itertools import accumulate


input = sys.stdin.readline
N, M = map(int, input().split())
dp: list[int] = list(
    accumulate(list(map(int, input().split())), initial=0)
)
for _ in range(M):
    i, j = map(int, input().split())
    print(dp[j] - dp[i-1])

Big-O

구간합의 경우 N개의 배열이 주어졌을 때 N+1개의 누적합 요소를 가지고 있는 배열을 만들어주기만 하면 계산은 상수 시간의 시간 복잡도로 작업을 수행하기 때문에 결국 초기 누적합에 대한 배열을 만들어주기 위해 시간 복잡도는 O(N)이다.

기타

해당 문제는 다이나믹 프로그래밍(Dynamic Programming) 문제의 한 종류로 볼 수 있는데 이전에 저장한 값을 토대로 다음 값을 구해야 하기 때문이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 167. Two Sum II - Input Array Is Sorted를 풀고 작성한 글입니다.

문제

요구사항

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length .

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

제약사항

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

풀이

접근법

투 포인터(Two Pointer) 접근을 통해 문제를 해결할 수 있다.

입력되는 numbers 배열이 이미 오름차순 정렬되어 매개변수로 넘어오기 때문에 단순히 반복문을 수행하며 만약 두 수의 합이 대상이 되는 값보다 클 경우 우측 인덱스를 한 칸 줄이고 클 경우 좌측 인덱스를 한 칸 늘리면 된다.

나의 풀이

접근법을 토대로 문제를 해결하면 아래와 같다.

def solution(numbers: list[int], target: int) -> list[int]:
    left, right = 0, len(numbers)-1
    while left < right:
        sum_of_two_numbers: int = numbers[left] + numbers[right]
        if sum_of_two_numbers == target:
            return [left+1, right+1]
        elif sum_of_two_numbers > target:
            right -= 1
        else:
            left += 1

시간 복잡도

양쪽 끝에서 점점 범위를 줄여나가기 때문에 최악의 경우에도 길이가 N인 배열의 모든 요소를 한 번만 확인하면 되기 때문에 시간 복잡도는 O(N)이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ 백준 ] 2110번: 공유기 설치를 풀고 작성한 글입니다.

문제

설명

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

풀이

접근법

거리를 기준으로 이진 탐색이 이뤄지는 부분까지는 생각했는데 집까지의 거리를 구해서 C개의 공유기를 설치하는 방법에 대한 접근법이 떠오르지 않아 다른 사람의 접근법을 참고했다.

시작값과 끝값은 1과 가장 거리가 먼 경우, 다시 말해 오름차순으로 정렬된 집에 대해 첫 집과 끝 집의 거리로 할당하면 된다.

이후 반복문을 수행하며 해당 거리의 중간값을 계속해서 구하며 집에 대해 내부적으로 반복문을 한번 더 수행해서 만약 중간값보다 집 사이의 거리가 길면 갯수를 늘리고 그렇지 않으면 늘리지 않는다.

이렇게 구한 갯수가 C보다 크거나 같은 경우 집 사이의 거리를 더 늘려도 되기 때문에 시작값을 중간값에 1을 더한 값으로 재할당하고 그렇지 않으면 집 사이의 거리를 더 줄여야 하기 때문에 끝값을 중간값에 1을 뺀 값으로 재할당한다.

추가적으로 입력값이 매우 크기 때문에 내부 sys 모듈 내에 있는 readline() 내장 함수를 사용해서 입력값을 받아야 시간 초과가 되지 않는다.

나의 풀이

접근법을 토대로 문제를 풀면 아래와 같다.

import sys


input = sys.stdin.readline
N, C = map(int, input().split())
houses = [ int(input()) for _ in range(N) ]

houses.sort()
answer = 0
start, end = 1, houses[-1] - houses[0]
while start <= end:
    count = 1
    middle = (start + end) // 2
    previous_idx = 0
    previous_distance = end
    for idx in range(1, len(houses)):
        distance = houses[idx] - houses[previous_idx]
        if distance >= middle:
            count += 1
            previous_idx = idx
            if distance < previous_distance:
                previous_distance = distance

    if count >= C:
        if answer < previous_distance:
            answer = previous_distance
        start = middle + 1

    else:
        end = middle - 1

print(answer)

Big-O

정렬 메서드를 사용했기 때문에 시간 복잡도는 O(NlogN)이다.

추가적으로 이진 탐색의 시간 복잡도는 O(logN)인데 내부적으로 N-1번 반복문이 수행되기 때문에 시간 복잡도는 O(NlogN)이 된다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ 백준 ] 2504번: 괄호의 값을 풀고 작성한 글입니다.

문제

설명

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

풀이

접근법

결국 못 풀어서 다른 사람의 접근법을 확인했다.

이후에도 접근법을 토대로 혼자 풀이했는데 계속해서 IndexError 를 반환했다.

이전에 베어로보틱스 인턴 라이브 코딩 테스트를 했을 때도 느낀 부분이지만 구현 문제를 풀 때는 무조건 안 되는 경우에 대한 예외 처리를 우선하는 걸 생각해야겠다.

올바르지 않는 경우에 대해 먼저 정리를 하고 문제를 접근했으면 조금 더 쉽게 풀 수 있었을 것 같다.

풀이의 경우 괄호를 열 때는 임시 변수에 곱해주고 괄호를 닫을 때는 곱했던 값을 실제 정답으로 반환할 변수에 더해주면 된다.

이때 유의할 점은 연속해서 괄호가 닫히는 경우 이미 여는 과정에서 곱했기 때문에 실제 정답에 더해주면 안 된다는 것이다.

따라서 이전 괄호가 무엇인지 계속해서 확인하는 조건문도 필요하다.

나의 풀이

접근법을 토대로 문제를 풀면 아래와 같다.

S: str = input()

values: dict[str, int] = {"(": 2, "[": 3}
brackets: dict[str, str] = {")": "(", "]": "["}

temp, answer = 1, 0
stack: list[str] = []
previous_bracket: str = ""
is_validated_brackets: bool = True
for bracket in S:
    if not bracket in brackets:
        temp *= values[bracket]
        stack.append(bracket)

    else:
        if not stack:
            is_validated_brackets = False
            break

        else:
            compare_bracket: str = stack.pop()
            target_bracket: str = brackets[bracket]
            if compare_bracket != target_bracket:
                is_validated_brackets = False
                break

            else:
                if not previous_bracket in brackets:
                    answer += temp

                temp //= values[target_bracket]

    previous_bracket = bracket

if stack or not is_validated_brackets:
    print(0)

else:
    print(answer)

Big-O

시간 복잡도의 경우 문자열의 길이 N만큼 반복문을 수행하면 되기 때문에 O(N)이다.

추가적으로 해시 테이블의 경우 어떤 값이 존재하는지, 다시 말해 일치하는 키가 존재하는지 확인하는 시간 복잡도는 O(1)로 상수 시간이기 때문에 별도의 영향을 끼치지 못한다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ 백준 ] 1654번: 랜선 자르기를 풀고 작성한 글입니다.

문제

설명

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

풀이

접근법

이전 2805번: 나무 자르기와 풀이가 거의 동일하다.

다만 시작 값을 1로, 끝 값을 가장 긴 랜선의 길이를 가져가려는 수와 가지고 있는 수를 나눈 값의 몫 만큼 나눈 값에서 1을 더해 할당한다.

나무 자르기 때와 마찬가지로 결국 K개의 랜선을 가져가기 위해 기존의 가져고 있는 N개의 랜선을 나눠야 하기 때문이다.

나의 풀이

접근법을 토대로 문제를 풀면 아래와 같다.

import sys


input = sys.stdin.readline
K, N = map(int, input().split())
lans: list[int] = [ int(input()) for _ in range(K) ]

answer: int = 0
start, end = 1, (max(lans) // (N // K)) + 1
while start <= end:
    middle: int = (start + end) // 2
    target: int = sum([lan // middle for lan in lans])

    if target >= N:
        if answer < middle:
            answer = middle
        start = middle + 1
    else:
        end = middle - 1

print(answer)   

Big-O

이분 탐색을 수행하기 때문에 O(logN)의 시간 복잡도가 필요하지만 추가적으로 반복문을 돌며 내부에서 매번 가져갈 수 있는 랜선의 개수를 구해야 하기 때문에 배열의 길이인 N만큼 더 반복되어 결국 시간 복잡도는 O(NlogN)이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ 백준 ] 2805번: 나무 자르기를 풀고 작성한 글입니다.

문제

설명

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

풀이

접근법

이진 탐색을 통해 문제를 해결할 수 있다.

시작 값의 경우 0, 끝 값의 경우 주어진 나무의 높이 중 가장 긴 나무로 한다.

이때 반복문을 돌면서 대상이 되는 나무의 길이보다 길이가 긴 나무들만 해당 대상 만큼 자른 합산을 구하여 집에 가져가려는 나무의 높이와 비교해야 한다.

또한 비교의 대상이 되는 높이가 집에 가져가려는 나무보다 긴 경우 너 길게 나무를 잘라도 되기 때문에 시작 값을 자르려 하는 나무의 높이보다 길이가 1만큼 길게 재할당한다.

그리고 해당 대상이 만약 이전 값보다 큰 경우 재할당하여 최댓값을 구할 수 있다.

나의 풀이

접근법을 토대로 문제를 풀면 아래와 같다.

N, M = map(int, input().split())
trees = list(map(int, input().split()))

answer = 0
max_heigth = max(trees)
left, right, target = 0, max_heigth, max_heigth // 2
while left <= right:
    total = sum([ tree - target for tree in trees if tree > target ])

    if total >= M:
        if answer < target:
            answer = target
        left = target + 1

    else:
        right = target - 1

    target = (left + right) // 2            

print(answer)

다른 풀이

아래와 같이 똑같은 이진 탐색이지만 조금 다르게 접근해서 문제를 해결할 수도 있다.

끝 값을 가장 길이가 긴 나무를 M을 N으로 나눈 몫만큼 나눈 것으로 할당하면 된다.

결국 M의 높이 만큼을 집에 가져가기 위해 N개의 나무를 나눠서 가져가야하므로 이러한 계산을 통해 끝 값을 구할 수 있는 것이다.

N, M = map(int, input().split())
trees: list[int] = list(map(int, input().split()))

start, end = 0, max(trees) - (M // N)
while start <= end:
    middle: int = (start + end) // 2
    target: int = sum([tree - middle for tree in trees if tree > middle])

    if target >= M:
        start = middle + 1

    else:
        end = middle - 1

print(end)

Big-O

이진 탐색을 통해 O(logN)의 시간 복잡도가 필요한데 추가적으로 내부에서 N의 길이 만큼 배열을 돌며 잘린 나무의 합산을 계산해야 하기 때문에 최종적으로 시간 복잡도는 O(NlogN)이다.

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다. 이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ 백준 ] 1966번: 프린터 큐를 풀고 작성한 글입니다.

문제

설명

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

풀이

접근법

주어진 문서의 우선순위를 담은 배열을 하나 만든 뒤 반복문을 계속 돌면서 만약 현재 인쇄되어야 하는 문서, 다시 말해 우선순위가 담긴 배열의 첫 번째 요소가 남은 요소들보다 큰 경우 해당 요소를 파이썬 리스트 내장 메서드인 pop() 을 사용해서 배열에서 삭제한다.

만약 크지 않은 경우 append() 를 사용해서 배열의 맨 마지막에 다시 삽입한다.

이때 배열에서 삭제되는 요소가 문제에서 몇 번째로 인쇄되는지 궁금했던 요소인지 확인하기 위해 N의 길이 만큼 M번째 인덱스를 제외하고 전부 False 값인 배열을 하나 만든다.

나의 풀이

접근법을 토대로 문제를 풀면 아래와 같다.

for _ in range(int(input())):
    N, M = map(int, input().split())
    queue: list[int] = list(map(int, input().split()))
    check: list[bool] = [ False for _ in range(N) ]
    check[M]: bool = True
    count: int = 0
    while queue:
        highest_priority: int = max(queue)
        target: int = queue.pop(0)
        is_target: bool = check.pop(0)
        if target == highest_priority:
            count += 1
            if is_target:
                print(count)
                break

        else:
            queue.append(target)
            check.append(is_target)