Upperbound , Lowerbound

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

 

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

 

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

 

LG CNS 사전 코딩테스트 문제를 가벼운 마음으로 풀었는데, 두번째 문제를 테스트 케이스만 통과하고 전체 히든 케이스는 다 틀렸다. 나의 접근 방법이 아예 틀렸음을 깨닫고 구글링을 해서 유형을 찾아보니 up, lb 문제와 똑같았다. 이번 기회에 다시 복습을 해야겠다고 느꼈다.

숫자카드 2

해당 문제가 동일한데,

 

6

3

2

10

10

10

-10

-10

7

3

 

이 문제에서 10의 등장 횟수를 구하려면 어떻게 해야할까? 배열을 순회하며 등장횟수를 계산해줄 수도 있지만, 더 간단하게 풀 수 있다.

 

 

 

 

-10

-10

2

3

3

6

7

10

10

10

 

정렬을 해주면, 10이 있는 위치가 더욱 명확해진다. 

10이 처음 등장하는 index와 10을 초과하는 index를 각각 구한 다음에, 빼주면 등장 횟수를 간단하게 구할 수 있다.

이 때, 10을 초과하는 index는 배열 길이를 넘어가기 때문에 `int hi = arr.length` 이런식으로 설정을 해야한다.

 

int k = upperbound(arr, 10) - lowerbound(arr, 10); 를 해주면 등장 횟수를 구할 수 있다. 

 

 

 

https://st-lab.tistory.com/267

[백준] 10816번 : 숫자 카드 2 - JAVA [자바]

해당 블로그에서 정말 설명을 잘 해놔서 감사하게 참고하고 있다.