[백준] 이분탐색 실버

백준 1920번

---

☄️ 문제 풀기 전 내 생각

1. 문제만 보았을 때 이분탐색이라는 카테고리에서 선택하지 않았다면 배열 안에 특정 값이 있는지 확인할 수 있는 내장 메서드인 in을 사용했을 것 같다. 그래서 True인 경우에는 1을 출력하도록하면되니깐 int()를 통해서 boolean을 변환한다면 원하는 문제를 해결할 수 있다고 생각하였다.
2. 앞으로 이러한 문제를 풀 때에는 정수의 범위를 반드시 확인하고 넘어가야할 것 같다. 크다 싶으면 그냥 이분탐색으로 문제를 풀어보자.
3. 이분탐색 가장 기본적인 문제이기에 이분탐색을 구현할 수 있는지 한 번 해보자.

 

---

 

🌈 Python 코드

📦 이분탐색

def 이분탐색(array, goal):
    left = 0
    right = len(array) - 1
    # 여기서 / 만 하면 소수자리 값이 나오니깐 정수나누기 사용해야 함
    
    # 여기서 return문 사용되니깐 걍 탈출 조건을 안 넣었었는데 그러면 안된다고 한다.
    while left <= right:
        half = (right + left) // 2
        if array[half] > goal:
            right = half - 1
        elif array[half] < goal:
            left = half + 1
        elif array[half] == goal:
            return 1
    """
    기존에는 while문 안에 있었는데 도달할 수 없는 조건이라고 해서 while문 밖으로 옮김
    이러면 while문에서 만족하지 못했을 때 0을 return하도록 설계가 된다.
    """
    return 0

• 중간 중간 모르는 점이 생겨서 GPT를 사용해서 완성을 하긴했지만 기본적으로 문제가 된 부분을 생각하면서 나중에 구현할 때에는 좀 더 자연스럽게 구현할 수 있을 것 같다.

📦 완성 코드

# 수찾기 1920 실버 4

def 이분탐색(array, goal):
    ...
    return 0

def sol1920():
    N = int(input())
    arrayN = sorted([int(x) for x in input().split()])
    M = int(input())
    arrayM = [int(x) for x in input().split()]
    for i in range(M):
        print(이분탐색(arrayN, arrayM[i]))

sol1920()

• 중간중간 모르는 내용에 대해서는 GPT를 좀 참고한 부분이 있으나 거의 구현 가능임

 

---

백준 10816번

---

☄️ 문제 풀기 전 내 생각

1. 기존에 만든 이분탐색 함수를 이용할 수 있으니 전체적인 틀만 생각하자.

 

🌈 Python 코드

📦 완성 코드

def sol10816():
    N = int(input())
    dict1 = {}
    """
    for i in [int(x) for x in input().split()]:
        if i in dict1:
            dict1[i] += 1
        else:
            dict1[i] = 1
    """
    # 너무나도 간단하게 바뀔 수 있는 구문
    for i in map(int, input().split()):
        dict1[i] = dict1.get(i, 0) + 1
    arrayN = sorted(dict1.keys())
    result = []
    N = int(input())
    for j in map(int, input().split()):
        if 이분탐색(arrayN, j):
             result.append(str(dict1[j]))
        else:
            result.append('0')
    print(" ".join(result))

sol10816()

 

• 기존에 구현했던 코드에서 좀 더 간단하고 깔끔하게 나타낼 수 있는 부분을 찾았다.
• 반복문에서 이분탐색이 true인 조건의 실행문에서 str을 append하지 않았을 때에는 typeError의 문제점이 있었다.

---

 

🔥 새롭게 알게 된 내용

1.  Python은 호이스팅이 될까?

-> 안된다.

2.  Python에서 dict는 오름차순이나 내림차순으로 순서가 보장이 될까?

-> 된다.

python3.7부터 공식적으로 dict의 순서가 보장이 된다고 한다. 그렇기에 정렬을 하게 되면 key값에 따라서 정렬이 된다. 다만 자동정렬은 아니기에 sorted()를 이용해야한다.

d = {"b": 2, "a": 1, "c": 3}
sorted_d1 = dict(sorted(d.items()))  # key 기준 오름차순 정렬
print(sorted_d1)  # {'a': 1, 'b': 2, 'c': 3}

sorted_d2 = dict(sorted(d.items(), reverse=True))  # key 기준 내림차순 정렬
print(sorted_d2)  # {'c': 3, 'b': 2, 'a': 1}

# 값 기준 오름차순 정렬
sorted_d3 = dict(sorted(d.items(), key=lambda x: x[1]))
print(sorted_d3)  # {'a': 1, 'b': 2, 'c': 3}

# 값 기준 내림차순 정렬
sorted_d4 = dict(sorted(d.items(), key=lambda x: x[1], reverse=True))
print(sorted_d4)  # {'c': 3, 'b': 2, 'a': 1}

 

3.  Python에서 "".join(array)를 할 때 array에는 str type만 존재해야하는가?

-> YES