백준 21756 자바(Java) 지우개 - 역순 삭제

태그

• 리스트
• 역순 삭제(Reverse Deletion)

풀이

Java의 ArrayList와 같은 자료구조는 요소를 제거하면 나머지 요소들이 왼쪽으로 당겨지며 인덱스가 재조정 된다.

예를 들어, 0번 인덱스를 제거하면 기존 1번 인덱스가 0번으로 이동하므로, 반복문 다음 실행 시 기존 1번 인덱스에 있던 요소를 탐색하지 않게 된다.

따라서 리스트를 순회하며 인덱스 조건에 따라 삭제하고자 한다면 역순으로 삭제해야한다.

이 문제 또한, 홀수번(인덱스 기반 조건)째 요소를 반복하여 삭제하므로 인덱스가 꼬이는 것을 방지하기 위해 뒤에서 부터 지워야 한다. → 역순 삭제

static void solve() throws Exception {
	int n =scan.nextInt();
	List<Integer> num = new ArrayList<>();
	for (int i = 0; i < n; i++) {
		num.add(i+1);
	}
	while(num.size() > 1){
		int m =  num.size() - 1;
		for (int i = m; i >=0 ; i--) {
			if(i % 2 == 0){
				num.remove(i);
			}
		}
	}
	sb.append(num.get(0));
}