백준 - 집합과 맵 10815번 숫자 카드 / 이분 탐색을 활용

= 내가 접급한 방법 = 

 

Map을 이용해서 접근했다.

 

1. 상근이가 갖고 있는 카드를 Map<Integer, Integer>으로 <카드번호, 1> 이렇게 저장

 

2. 주어진 카드를 새로운 Map<Integer, Integer>으로 <카드번호, 0> 이렇게 저장 (result)

( 순서 유지를 위해 LinkedHashMap을 이용 )

3. card에 있는 key값을 for문을 이용해서 뿌려줄 때,

contains메서드를 이용해서

result에 그 key값이 존재한다면 <카드번호, 1>로 수정을 했다.

 

그리고 결과를 그대로 출력해주면 됨.

 

= 이분 탐색을 이용한 방법 =

 

이 문제의 핵심은 이분 탐색 알고리즘을 활용할 수 있냐 없냐 문제였다.

 

시간 복잡도를 logN으로 할 수 있는 최적의 탐색 방법이다.

 

정렬된 배열을 탐색하는 것인데, 반을 쪼개고 반을 쪼개고 반을 쪼개서 찾는 방식이다.

 

1 ~ 10까지의 값이 존재하면 1 2 3 4 5 6 7 8 9 10이고

내가 찾고싶은 값은 7이라고 가정할 때,

중간값 = ( 0 + 9 ) / 2를 이용하면 5임을 알 수 있고

5랑 7이랑 비교해서 7이 더 크기 때문에 5까지의 값은 다 지우고 6 ~ 10까지의 값을 다시 반으로 쪼개서 찾는 방식이다.

 

코드로 한 번 보자.

 

이진 탐색 메서드를 구현했다.

 

처음 배열 arr, start와 end는 arr배열의 시작과 끝, target은 내가 찾고 싶은 값

 

1. 중간값이 target보다 클 때, end를 mid - 1로하고 mid를 다시 정의한 후 while을 돌면 된다.

 

2. 중간값이 target보다 작을 때, start를 mid + 1로 하고 mid를 재정의 후 반복

 

3. 중간값과 target같을 때, 그 때 return 1을 해주면 문제를 해결할 수 있다.

 

4. while을 벗어날 때, target이 배열안에 없기 때문에 0을 돌려주면 된다.

 

이러한 알고리즘으로 풀 수 있다는 것을 새롭게 알았다.

 

처음에는 이해하기 힘들었는데 계속 연습하고 생각하니까 쉽게 이해할 수 있었다.

 

다음 포스팅은 숫자 카드2 문제인데 이건 중복된 값이 존재할 때 어떻게 return을 할 수 있는지 찾는 것이다.

 

더 어렵기 때문에 더 열심히 공부를 해야겠다.