dongwooklee96

import time
import random

import pytest

nums = list(random.randint(1, 100) for _ in range(100))


@pytest.mark.benchmark(
    min_rounds=10000000,

dongwooklee96

"""
# 문제 : 3번째 큰 수

- 배열에서 3번재로 큰 수를 찾아서 반환하도록 하자.
- 만약 3번째로 큰 수가 없다면 가장 큰 수를 반환하면 된다. 예를 들어서 배열에 [1, 2, 3] 이 있다면 1을 반환하고
3번째가 없는 배열 [2, 3] 이라면 3을 반환하면 된다.

### 아이디어 (정렬)

1. 배열을 역순으로 정렬한다.

dongwooklee96

"""
# 문제 : 부족한 금액 계산하기

- 놀이기구의 원래 이용료는 price 원이다.
- 놀이기구를 N 번째 이용한다면 원래 이용료의 N배를 받는 패널티가 있다.
- 예를 들어서, 처음 이용료가 100원 이였다면, 2번째는 200원 3번째는 300원이다.

-> 놀이기구를 {count} 번 타게 되면, 현재 자신이 가지고 있는 금액에서 얼마가 모자라는지를 반환 하는 함수를 작성하라
-> 단 금액이 부족하지 않으면 0을 반환하라.

dongwooklee96

"""
문제 6.6 트리 경로의 합

노드에 정수형 데이터가 있는 이진 트리가 입력으로 주어진다.
각 경로에 있는 노드의 데이터 합이 특정 값이 되는 경우가 몇 개인지 확인하라.
꼭 루트 노드에서 시작할 필요는 없으며, 시작은 부모 노드에서 자식 노드 쪽으로 이동하여 합을 만들어
나가야 한다. 자식 노드에서 위로 올라가는 경우는 없다.

### 제한 사항

dongwooklee96

"""
# 깊이 우선 탐색, 너비 우선 탐색, 그리고 이진 힙

### 깊이 우선 탐색 (Depth-First Search)

깊이 우선 탐색의 키워드는 '스택 (Stack)' 이다.
앞 예제에서 사용한 트리에 깊이 우선 탐색으로 노드를 방문을 해보자.

### 너비 우선 탐색 (Breadth-First Search)

dongwooklee96

"""
이진 트리를 구현하여라.
"""


class Node:

    def __init__(self, data):
        self.left = None
        self.right = None

dongwooklee96

"""
문제 : 버블 정렬을 구현하시오.

"""
from typing import List


def bubble_sort(arr: List[int]):
    n = len(arr)

dongwooklee96

"""
문제 : 배열의 두 부분집합의 최소 차이 만들기

배열을 두 부분집합을 만들고 각 부분집합의 합 차이가 최소가 되는 값을 반환하라
예를 들어서 [3, 2, 7, 4, 1]이 주어지면 부분집합의 합 차이가 최소가 되게 하려면,
하나는 [1, 7]이 되고, 다른 하나는 [2, 3, 4]가 되었을 때 각 부분집합의 합은 8과 9가 되어서 차이가 1이 된다.
이때 1을 반환하도록 구현하는 것이다.
"""

import sys

dongwooklee96

"""
문제 4.4.3 동전 교환

가게에 가서, 물건을 사고 물건 값을 지불하고 남은 잔돈을 거슬로 주는 과정을 코딩하는데
가장 적은 개수의 동전으로 반환해야하는 것이 문제이다. 잔돈으로 거슬러 주는 동전의 값을
배열로 입력 받는데, 예를 들어 [1, 2, 5] 이고 거슬러줘야 하는 돈이 11이라면 [5, 5, 1] 로 3개를
거슬러 주는 것이 가장 적은 동전의 개수로 반환한 것이다.
"""
import sys
from typing import List

dongwooklee96

"""
문제 4.4.2 모든 문자열 치환

입력으로 주어진 문자열의 가능한 치환을 모두 출력해보는 문제이다.
예를 들어, 입력된 문자열이 'abc' 라면 결과는 ["abc", "acb", "bac", "cab", "cba"] 가 되어야 한다.
각 문자가 놓이는 모든 위치의 조합을 만들어라.
"""

from typing import List