[BOJ] 1920. 수 찾기.py

#. Problem

https://www.acmicpc.net/problem/1920

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

#. Code

def binarySearch(N, A, key):
    lt, rt = 0, N-1
 
    while lt <= rt:
        mid = (lt + rt) / 2
 
        if A[mid] == key:
            return 1
        elif A[mid] > key:
            rt = mid - 1
        else:
            lt = mid + 1
 
    return 0
 
N = int(input())
A = list(map(int, input().split()))
M = input()
B = list(map(int, input().split()))
 
A.sort()
 
for n in B:
    res = binarySearch(N, A, n)
    print(res)

#. Other Code

N, A = int(input()), {i: 1 for i in map(int, input().split())}
M = input()
 
for i in list(map(int, input().split())):
    print(A.get(i, 0))
    # print(1 if i in A else 0)

line 1) N과 A(dictionary)를 입력받는다.

   dictionary도 list와 유사한 comprehension으로 입력받는다.

   입력받은 값을 key 값으로, value 값은 1로 초기화하여 입력

line 4~5) list를 comprehension으로 입력받음과 동시에 반복문 실행, 

line 5) dictionary의 get method를 사용하면 key에 없는 값를 처리해줄 수 있다.

   (print(A[i]) 로 했을 경우, 입력받은 Key가 KeyError를 발생시킴)

line 6) get method를 사용하지 않더라고 삼항연산자로 풀어낼 수 있다.

   dictionary A에 i가 있다면 1을, 없다면 0을 출력

   

나는 너무나 당연하게 이분탐색으로 불어냈었는데,,

이렇게 단순한 방법이 있엇다.. 하핳

알고리즘을 적용하여 풀어야하는 문제이지만

이렇게 자료구조를 잘 이용하면 단순하게 풀어낼 수 있다는 것..

그리고 Python의 Power..!