오늘의 알고리즘 (4월 13일)

1. 백준, 수 찾기, 1920번 

 

www.acmicpc.net/problem/1920

1920번: 수 찾기

 

---

2. 생각해보자

• 첫 입력값은 숫자의 개수 N이 주어진다.
• 두번째 입력값에는 N개의 숫자만큼 정수가 주어진다. 
• 세번째 입력값에는 찾을 숫자의 개수 M이 주어진다. 
• 네번째 입력값에는 M개의 숫자만큼 정수가 주어진다. 

- 배열 두개를 만들어서 이중 for문을 돌려서 비교하면 될 것 같다.

 

n = int(input())
sample = list(map(int, input().split(' ')))
m = int(input())
compare = list(map(int, input().split(' ')))

for i in compare:
    for j in sample:
        if j == i:
            print(1)
            break
        elif j == sample[-1] and j!=i:
            print(0)

- 내가 작성한 코드는 위와 같다.

- 생각해보니, n과 m은 사용하지 않는 의미없는 변수다. 저건 없어도 되는데 어떻게 써야할지 모르겠다. 

- 출력은 아래와 같이 잘 나왔다. 그래서 제출해 보았는데... 

 

 

- 보이는 바와 같이, 시간초과가 나왔다. 어떻게 해결할까...? 

• 시간초과가 나오는 이유는, 극단적인 입력값이 주어진 경우 해당 알고리즘으로는 처리할 수 없다는 뜻이다.

---

3. 해설 및 코드 분석

n = int(input())
array = set(map(int, input().split(' ')))
m = int(input())
x = list(map(int, input().split(' ')))

for i in x:
	if i not in array:
    	print(0)
    else:
    	print(1)

 

- if ~ not in 을 사용하면 이렇게나 간단하게 풀 수 있는 문제였다. 

- 더불어, 중복값을 포함하지 않는 SET의 특성을 적용하면 해당 문제에 더욱 알맞는 해결책을 구현할 수 있다.

 

 

- 결과는 안봐도 정답. 

- 문제를 꾸준히 풀어서 기본적인 언어의 특성에 익숙해져야겠다.