바위타는 두루미

문제 정수 스트림을 읽는다고 하자. 주기적으로 어떤 수 x의 랭킹(x보다 같거나 작은 수의 갯수)를 확인하고 싶다. 해당 연산을 지원하는 자료구조와 알고리즘을 구현하라. 수 하나를 읽을 때마다 호출되는 메서드 track(int x)와, x보다 작거나 같은 수의 갯수( x자신을 제외)를 반환하는 메서드 getRankOfNumber(int x)를 구현하라 입력 : 5,1,4,4,5,9,7,13,3 출력 : getRankOfNumber(1) = 0 getRankOfNumber(3 ) = 1 getRankOfNumber(4 ) = 3 해법 모든 원소를 정렬된 상태로 보관하는 배열을 사용하면 구현하기가 상대적으로 간단해진다. 새로운 원소를 삽입할때마다 다른 원소들을 옆으로 옮겨 공간을 확보해야하는데 그렇다보면 t..

문제 각 행과 열이 오름차순으로 정렬된 MXN 행렬이 주어졌을대, 특정한 원소를 찾는 메서드를 구현하라 해결법 첫번째 : 행마다 이진탐색을 할 수있다. M개의 행이 있고 각 행을 탐색하는데 O(logN)이 걸리기 떄문에 O(MlogN)이 될 것이다. 두번재 해결법을 생각해보기 전에 규칙을 찾아보자 15 20 40 85 20 35 80 95 30 55 95 105 40 80 100 200 이런 행렬이 주어졌을때 55를 찾아보자. 행의 시작점이나 열의 시작점을 보면 위치를 유추해 볼 수 있다. 열의 시작점 원소의 값이 55보다 크다면 탐색할 필요가 없고, 마찬가지로 행의 시작점 원소의 값이 55보다 크다면 탐색할 필요가 없을 것이다. 그러면 행이나 열의 마지막점에서도 똑같이 적용할 수 있다. 어떤 행이나 열..

문제 음이 아닌 정수 40억 개로 이루어진 입력 파일이 있다. 이 파일에 '없는 정수'를 생성하는 알고리즘을 작성하라. 단, 메모리는 1GB만 사용할 수 있다. - 연관문제 메모리 제한이 10MB라면 어떻게 풀 수 있을까? 중복 되는 값은 없으며, 이번에는 정수가 10억 개만 있다고 가정하자. 접근법 우선 40억개라는 수의 의미를 알아야 했다. 40억개는 즉 2의 32승이 조금 안되는 수이다. 하지만 음이 아닌 정수라고 햇으니 2의 31개의 수가 40억개(2의 32승) 있다고 하니 중복되는 값이 있을 것이다. 제공된 메모리는 1GB => 2^30 *2^3 만큼의 비트를 사용할 수 있을 것이다. 따라서 2의 31 만큼의 수들을 모두 표현하기에 충분한 양이다. 따라서 1. 40억 비트의 크기인 비트벡터를 만..