[자료구조] 이중 배열로 데이터 처리

** 읽고 의견 주시면 감사하겠습니다! 고민하고 있는 문제라서요!!

반복문으로 탐색 vs 인덱스배열 참조 

예를들어 토너먼트와 같은 데이터 처리에서

101001010
을
정렬해서
11110000 으로 해서 처리

A배열은 값

B배열은 정렬된 A의 인덱스

접근은 B의 인덱스로 접근

class user{
private String name;
private int age;
private boolean survive;
}

ArrayList<user> userList = new ArrayList<user>();


 

	1	2	3	4	5	6	7
name	a	b	c	d	e	f	g
age	1	2	3	4	5	6	7
survive	true	true	false	false	false	true	false

이렇게 값이 세팅됐다고 치자.

그럼 이제 survive 가 true인 값들만 처리를 해야한다. 즉 3,4,5,7번은 필요가 없는 자료들이다.
그런데 그 자료에 단번에 접근하지 못한다. 어느게 survive가 true인지 모르기 때문이다.

그럼 어떻게 해야하지? 반복문 밖에 없다.
a 야 살았니? b야 살았니? ... g야 살았니?

만약. 자료가 백만, 천만개라면?

그래서 생각한것이 이들의 생존정보를 가진 배열을 만드는것.

ArrayList<int> survivedUser = new ArrayList<int>();

	1	2	3	4	5	6	7
index	1	2	3	4	5	6	7

여기에서 survive is false가 된 자료를 remove한다면

	1	2	3
index	1	2	6

이 될것이고,
survive가 true인 값은 survivedUser.size()의 값은 3개
그 인덱스는 userList의 1번,2번 6번 인것을 알 수 있을것이다.

하지만 이것에는 안좋은 점이 있다.

바로 동기화

userList의 길이와
survivedUser의 길이가 다르다면

이 자료구조는 무너진다.

하지만 시간복잡도를 약간이나마 줄일 수 있다면

두 배열의 싱크를 완벽히 맞추는 작업만 해준다면 더 좋은 방법이 아닐까 생각한다.

*** 이 글을 읽으신 분들의 의견을 구합니다. 저 또한 이 문제로 매우 방황하고 있습니다. ***