[Python] BOJ 1920 : 수 찾기

https://www.acmicpc.net/problem/1920 <- 문제 click

 

1. 요구사항 분석

- N과 M 은 서로 다른 값이 될 수 있다.

- M개의 수들이 N개의 수에 있는 지 확인할 것.

- N에서 M의 여부를 순서대로 0,1 을 사용해서 보여줄 것.

 

2. 설계

• 우선, 구현을 한 뒤 리팩토링 해보자. 
• 구현 설계
  • 여러 요소를 한번에 int 형으로 바꾸기 위해서 map으로 N과 M 의 개수를 받는다.
  • for 문을 이용하여  arr1 안에 arr2 가 있는 지 확인한다. 
  • 존재 유무를 가시적으로 보여줄 arr2만큼의 리스트를 초기화해준다.
  • for 문을 이용하여 check_arr 를 하나씩 출력한다. 

3. 실수

[실수 1 : TypeError]

# 오류 예시

arr_list = [1, 2, 3, 4]

for index in len(arr_list):
	print(index)

• len(arr_list) 는 4를 반환하며, for 루프는 반복 가능한 객체(리스트, 튜플, 문자열 등)에만 사용할 수 있다.
• 정수는 (여기서는 4) 반복 가능한 객체가 아니기 때문에 TypeError 가 발생하는 것이다.
• 따라서 for문을 for index in range(len(arr_list)) 로 바꾸면 해결이 된다. 

[실수 2 : TypeError]

# 오류 예시

arr_list = [1, 2, 3, 4]

print(arr_list.index[4])

• index() 는 리스트의 메서드이기 때문에 호출하려면 소괄호를 사용해야 한다. index[4] 는 index라는 메서드에 대괄호로 접근하는 시도인데, 이는 타입에러를 발생시킨다. 

[실수 3 : SyntaxError]

arr_list = [1, 2, 3, 4]
1 = arr_list[2]

• 위 코드에서 의도는 arr_list의 인덱스 2번에 1을 위치시키고 싶었던 것이다. 
• 에러가 발생하는 이유는 값에 변수를 할당하려고 했기 때문이다. 왼쪽에 있는 값(1)은 수정할 수 없는 리터럴이므로 오류가 발생한다.

[실수 4 : ValueError]

# 오류 예시

arr1 = [1, 2, 3, 4]
arr2 = [2, 3, 4, 5]
print(arr1.index(arr2[3]))

• 에러가 발생하는 이유는 없는 arr2[3] 값을 arr1 에서 찾을 때, 해당 값이 arr1 에 존재하지 않기 때문이다.
• 2가지 방법으로 해결할 수 있겠다.
• 1번째 방법) in 연산자를 사용해 값이 리스트에 있는 지 확인한 후에 index()를 호출해보자. 

arr1 = [1, 2, 3, 4]
arr2 = [2, 3, 4, 5]

if arr2[3] in arr1:  # arr2[3]이 arr1에 있는지 확인
    print(arr1.index(arr2[3]))
else:
    print(f"{arr2[3]} is not in arr1")

• 2 번째 방법) try except 구문을 이용해보자

# 오류 예시

arr1 = [1, 2, 3, 4]
arr2 = [2, 3, 4, 5]

try:
    arr1.index(arr2[3])
    print('arr1에 arr2에서 찾는 값이 존재합니다.')
except:
    print('찾는 값이 arr1에 존재하지 않습니다.')

[실수 5 : <map object at 0x00000210194E96C0>]

# 오류 예시 

arr = map(int, input().split())

print(arr)

 

• map() 함수는 출력 기능은 없고 메모리상에서만 계산이 이루어진다.
• 따라서 위 코드를 출력하고 싶을 때, arr = list(map, (int, input().split())) 으로 바꿔주자. 

[실수 6 : 백준 시간초과]

• 짜둔 코드의 시간복잡도가 O(n^2) 이 되서 아마 그런 거 같다. 
• 하나의 리스트의 자료구조를 list 가 아닌 set으로 변경해주었다.
• set 자료구조는 해시 테이블을 사용하여 원소의 존재 여부를 평균적으로 O(1) 로 확인할 수 있다고 한다. 
• 따라서 해당 값이 있는 지 없는 지 확인하는 배열에 set 자료구조로 초기화 해주었다.

[실수 7 : 백준 런타임 에러(AttributeError]

• set 으로 변경 하였더니 발생한 오류이다. 
• 오류가 발생한 원인은 set 객체에는 index() 메서드가 없기 때문이다. set은 순서가 없는 자료구조이기 때문에 인덱스 기반 접근이 불가능하며, index 메서드가 존재하지 않는다.
• 따라서 set 객체의 특정 원소를 찾을 때는 in 키워드를 이용하여, 원소가 set에 있는 지를 빠르게 확인할 수 있다. 

 

* 최종 코드

arr1_N = int(input())
arr1 = set(map(int, input().split()))  # set으로 변환하여 탐색 시간 O(1)로 줄임
arr2_N = int(input())
arr2 = list(map(int, input().split()))

# check_arr 초기화
check_arr = [0] * len(arr2)

# arr2의 각 원소가 arr1에 있는지 확인
for i in range(len(arr2)):
    if arr2[i] in arr1:  # O(1)로 탐색 가능
        check_arr[i] = 1
    else:
        check_arr[i] = 0

# 결과 출력
for num in check_arr:
    print(num)