백준 1920 이진탐색

문제 링크

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

1920번: 수 찾기

문제는 첫번째 배열의 숫자가 있는데 두번째 배열에서 첫번째 배열에 숫자가 있느냐 있으면 1 없으면 0을 만들어서 출력하는 것이다.

 

먼저 내가 짠 틀린 코드를 보면,

코드 풀이

 

1. B 의 배열을 이진탐색을 위해서 오름차순 정렬을 했다. 대신 원본 배열을 잃지않기 위해 복사를 했다.

2. 정답의 길이만큼 0을 채워놓고 조건에 맞는 식만 1을 채우면 편하지 않을까해서 미리 0으로 채운 배열을 만들었다. (이게 틀린 이유)

3. for of 문이 for loop 를 포함한 array method 중 가장 빠르다하여 for 문으로 이진탐색을 했다.

4. 이진탐색의 결과 값이 문제에서 원하는 A 배열의 i 와 같은지 체크했다.

5. 결과 값을 찾으면 B 의 원본배열 (정렬되지 않은) 에서 index 를 찾아서 1로 바꿔주었다.

6. 그대로 한줄씩 출력..

 

테케는 통과했지만 계속 10%에서 틀렸다고해서 테케도 여러가지 변경해보고 했지만 내 코드에는 문제가 없었다.

그러다가 백준 사이트에 문제번호로 질문 올라온 것들을 봤더니 10% 에서 틀리는 사람이 많았는데

그 이유는 정수 중에 - 값이 문제 였다.

 

문제 가장 마지막 단에 -2^31 배수 부터 2^31 라고 되있었는데 이거 외에도 B 의 배열이 [0] 일 때 경우 등등

다른 문제가 생겼다.

 

기존 내 코드에서 유지보수를 해도 되지만 0으로 채운 이 배열 틀에서 수정하기에는 너무 덕지덕지일거 같아서 

코드를 새로 처음부터 작성했다.

 

정답코드

1. A를 정렬하고

2. B 의 값을 A 에서 이진탐색 하도록 했다.

3. 아까와 같이 배열을 미리 만드는 것이 아니라 조건에 부합하면 1 아니면 0 으로 채웠다.

 

ps 정말 간단한 논리인데 너무 돌아온게 아닌가 싶다..