Codeup 3108번 문제를 Student의 정보를 저장하는 객체와 생성된 Student 객체를 저장하는 ArrayList에서 List를 순회하면서 삭제를 하는 과정에서 한 가지 이슈가 발생했다.
package com.example.likelion_week1.codeup;
import java.util.*;
class Student {
private String processCode;
private int studentId;
private String name;
public Student(String processCode, int studentId, String name) {
this.processCode = processCode;
this.studentId = studentId;
this.name = name;
}
public int getStudentId() {
return studentId;
}
public String getProcessCode() {
return processCode;
}
public String getName() {
return name;
}
@Override
public boolean equals(Object o) {
if (this == o) // 객체의 주소가 같은 경우
return true;
if (o == null || getClass() != o.getClass()) // 두 객체가 다른 클래스의 인스턴스인 경우
return false;
Student student = (Student) o; // 객체를 Student 형으로 캐스팅한다.
return studentId == student.studentId; // 학번이 같으면 같은 객체로 판단한다.
}
}
public class Codeup3108 {
private List<Student> students = new ArrayList<>();
public Student makeAStudent(String processCode, int studentId, String name) {
return new Student(processCode, studentId, name);
}
private boolean isExist(Student pStudent) {
for (Student student : students) {
if (pStudent.getStudentId() == student.getStudentId()) return true;
}
return false;
}
private void addAStudent(Student pStudent) {
if (!isExist(pStudent)) {
students.add(pStudent);
}
}
private void deleteStudent(Student pStudent) {
// if (isExist(pStudent)){
// List<Student> removeObject = new ArrayList<>();
// for (Student student : students) {
// if(student.getStudentId() == pStudent.getStudentId()) removeObject.add(student);
// }
// students.removeAll(removeObject);
// }
// if(isExist(pStudent)){
// for (int i = students.size() - 1; i > -1; i--) {
// if (students.get(i).getStudentId() == pStudent.getStudentId()) students.remove(i);
// }
// }
if(isExist(pStudent)) {
students.remove(pStudent);
}
}
public void process(String line) {
String[] splitted = line.split(" ");
Student student = makeAStudent(splitted[0], Integer.parseInt(splitted[1]), splitted[2]);
switch (student.getProcessCode()) {
case "I" -> addAStudent(student);
case "D" -> deleteStudent(student);
}
}
public void printStudents() {
for (Student student : students) {
System.out.printf("%s %s %s\n", student.getProcessCode(), student.getStudentId(), student.getName());
}
}
public void printSpecificStudents(int[] arr) {
Collections.sort(students, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o1.getStudentId() - o2.getStudentId();
}
});
for (int item : arr) {
Student student = students.get(item - 1);
System.out.printf("%s %s\n", student.getStudentId(), student.getName());
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Codeup3108 codeup3108 = new Codeup3108();
int size = sc.nextInt();
sc.nextLine();
for(int i = 0; i < size; i++) {
codeup3108.process(sc.nextLine());
}
String[] indexStr = sc.nextLine().split(" ");
int[] indexArr = new int[indexStr.length];
for(int i = 0; i < indexStr.length; i++) {
indexArr[i] = Integer.parseInt(indexStr[i]);
}
codeup3108.printStudents();
codeup3108.printSpecificStudents(indexArr);
}
}위는 전체 코드 내용이고 이슈가 발생한 부분은 deleteStudent 메서드 부분이다.
해당 메서드는 기존 List에 존재하는 Student 객체 중 삽입 할 객체와 같은 studentId를 갖는 객체가 있으면 삭제하는 기능이다.
최초로 발생한 이슈는 for-each 문을 통해 List를 순회하면서 삭제하는 방법을 사용하고 싶어서
if(isExist(pStudent)){
for(Student student : students) {
if(student.getStudentId() == pStudent.getStudentId()) students.remove(pStudent);
}
}위의 코드와 같이 로직을 구성했다.
하지만 "java.util.ConcurrentModificationException"이 발생했고
그 이유를 찾기 위해 자료를 찾아본 결과 객체 삭제를 통한 index의 문제가 발생 할 수 있어 List에서는 기본적으로 List를 순회하는 도중에 객체를 삭제 할 수 없다는 내용을 찾게되었다.
if (isExist(pStudent)){
List<Student> removeObject = new ArrayList<>();
for (Student student : students) {
if(student.getStudentId() == pStudent.getStudentId()) removeObject.add(student);
}
students.removeAll(removeObject);
}위와 같이 students List를 순회를 하면서 매개변수로 받은 Student 객체와 같은 studentId를 갖는 List 내의 요소를 removeObject 라는 List를 생성해 저장한 후 순회가 끝나고 removeObject 내의 객체들을 students List에서 삭제하는 방법으로 해결했다.
두 번째 이슈는 List 내에 같은 studentId를 갖는 객체가 있는지 여부를 판단하는 isExist 메서드를 delete에 활용해 보기 위해 시도를 하던 중 발생했다.
첫번째로 구성한 delete 로직에서 isExist는 매개변수와 같은 studentId를 갖는 객체가 List에 없다면 delete를 진행하지 않게 하는 정도로 사용되는데
if(isExist(pStudent)) {
students.remove(pStudent);
}위처럼 나는 delete 메서드의 매개변수로 받는 pStudent를 통해 직접 remove를 하고 싶었다.
하지만 List의 remove 메서드는 내부적으로 전체 List를 순회하며 equals 메서드를 통해 객체가 서로 주소가 같거나 내용이 동일한 경우에 remove를 하기 때문에 단순히 pStudent와 studentId는 같지만 전체 내용이 동일하지 않은 객체들은 remove가 되지 않았다.
이를 해결하기 위해 Student 객체에 equals 메서드를 override 해주었다.
@Override
public boolean equals(Object o) {
if (this == o) // 객체의 주소가 같은 경우
return true;
if (o == null || getClass() != o.getClass()) // 두 객체가 다른 클래스의 인스턴스인 경우
return false;
Student student = (Student) o; // 객체를 Student 형으로 캐스팅한다.
return studentId == student.studentId; // 학번이 같으면 같은 객체로 판단한다.
}위는 override 한 코드이고 주소나 내용이 같은 경우 외에도 매개변수로 받는 object와 같은 studentId를 같는 경우에도 true를 return 하도록 만들어 remove 시에 studentId만 같은 경우에도 삭제가 되게 해주었다.
마지막으로 발생한 이슈는 for 루프를 통해 List를 순회하면서 remove 하면서 발생했다.
사실 테스트 케이스에서는 이슈가 발생하지 않았는데 코드를 계속 보면서 문제가 발생할 수 있다는 생각을 했다.
for (int i = 0; i < students.size(); i++) {
if (students.get(i).getStudentId() == pStudent.getStudentId()) students.remove(i);
}처음에는 위와 같은 로직을 구상했는데 List 자료구조에서는 n번째 index의 요소를 삭제하면 그 이후의 index의 요소들이 한 칸씩 당겨진다는 사실을 망각했다.
앞쪽 index 부터 순회하며 n번 index와 n+1번 index를 순차적으로 삭제하면 n번 index의 요소는 제대로 삭제가 되지만 n+1번 요소는 n번 index 요소의 삭제로 인해 index가 한 칸 당겨져 n번 index를 갖게되면서 정상적인 삭제가 이루어지지 않을 수 있다.
for (int i = students.size() - 1; i > -1; i--) {
if (students.get(i).getStudentId() == pStudent.getStudentId()) students.remove(i);
}그렇기에 위의 코드와 같이 상위 index 부터 순회하며 삭제를 진행해 index의 변화에 영향을 받지 않도록 수정했다.
delete 로직을 여러가지 방법으로 구상하면서 마주친 다양한 문제들을 정리해 보았다.
사실 개인적인 생각으로는 for 루프를 통해 studentId가 같은 객체가 있는 index 찾고 이를 통해 remove하는 방법이 가장 효율적이라고 생각했다.
for-each 루프를 통한 삭제는
1. for-each 루프를 통한 students List 전체 탐색
2. 삭제 할 객체를 저장할 새로운 List 생성
3. 삭제 할 객체를 저장한 List에서 또 다시 remove 메서드를 통해 내부적으로 List를 전부 순회하며 equals 메서드를 통해 삭제 할 객체를 select 후 삭제
isExist 메서드를 활용한 삭제는
1. equals 메서드 overriding이 필요
2. remove 메서드를 통해 내부적으로 List를 전부 순회하며 equals 메서드를 통해 삭제 할 객체를 select 후 삭제
for 루프를 통한 삭제
1. for 루프를 통한 List 순회와 동시에 index를 통해 arrayList에 바로 접근해 삭제
isExist 메서드를 동작하는 비용은 3가지 방법 모두 들어가기에 고려하지 않고 그 외의 부분만 고려한다면 for 루프를 통한 삭제가 가장 효율적으로 보인다.
isExist를 활용한 삭제도 전체 List를 remove 메서드 내부적으로 순회하고 for 루프를 통한 삭제도 List 전체를 순회하기에 비슷한 효율성을 갖을 것 같지만
isExist를 활용한 방법은 equals 메서드를 재정의 해야하기도 하고 equals 메서드를 재정의 한 사실을 모르고 본다면 이게 되나...? 하는 생각이 생길 것 같다.
(단순히 로직만 본다면 매개변수로 받은 객체를 통해 삭제하는데 studentId만 같은 객체가 삭제가 되나?, pStudent는 완전 별개의 객체인데 remove가 제대로 되나? 하는 생각이 생길 것 같다)
ArrayList가 아닌 LinkedList로 구현한다면 for 루프를 통한 삭제 방법에서 for 루프를 진행하면서 studentId가 같은 객체의 index를 찾고 해당 index를 remove 메서드의 매개변수로 주면 remove 메서드 내부적으로 다시 LinkedList에서 해당하는 index까지 가기 위해 첫 노드부터 탐색 할 수도 있다고 생각했다. 이로 인해 LinkedList로 구현하면 조금 더 비용이 증가 할 수 있다고 생각했다.
사실 ArrayList 보다 LinkedList가 삽입과 삭제에서 더 효율적이고 반면 ArrayList는 LinkedList 보다 조회와 탐색에 더 효율적인 것까지 고려하면 delete 로직에 한에서 차이는 없을 것 같다.(위의 생각이 맞다면...)
ArrayList = O(n^2) -------> for문 List 순회 O(n), 요소 접근 O(1), remove O(n)
LinkedList = O(n^2) ------- > for문 List 순회 O(n), 요소 접근 O(n), remove O(1)
- ArrayList에서는 메모리 구조상 연속된 공간에 위치하기 때문에 첫 index의 메모리 주소를 알면 얼마나 떨어졌는지 계산해 바로 접근이 가능하다.
반면 LinkedList는 메모리 구조상 연속된 공간에 위치하지 않고 각 요소를 저장하는 노드에 다음 노드로 가는 주소 정보를 저장해 만약 2번 index의 노드에 접근하려면 0번 노드 -> 1번 노드 -> 2번 노드 이런식으로 첫 노드부터 탐색해야한다.
ArrayList 항목 접근 = O(1), LinkedList 항목 접근 = O(n)- ArrayList는 삽입과 삭제 과정에서 공간이 부족하다면 더 큰 새로운 List를 생성하고 기존의 내용을 전부 복제하는 과정이 필요하기도 하고, 맨 앞 혹은 중간에 삽입하거나 삭제하게되면 모든 요소의 index를 이동하는 과정이 필요하다. 반면 LinkedList는 삽입 시에는 삽입하고 싶은 index의 이전 노드가 삽입하는 노드를 가리키게 하고 삽입 되는 노드가 이전 노드가 가리키고 있던 노드를 가리키게 하면 되고, 삭제 시에는 삭제하는 노드의 이전 index의 노드가 삭제하는 노드가 가리키고 있던 노드를 가리키게 하면 되기에 삽입 삭제의 효율이 ArrayList 보다 좋다.
ArrayList 삽입/삭제 = O(n), LinkedList 삽입/삭제 = O(1)
마지막 ArrayList로 구현하지 않고 LinkedList를 사용해 구현했을 때 비용적 차이는 개인적인 생각이기 때문에 틀릴 수도 있다.
아래 두 메서드는 List의 remove(Object o)와 equals(Object o)이다.
remove 동작에 대한 이해를 할 때 참고하기 위해 첨부한다.
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof List)) {
return false;
}
final int expectedModCount = modCount;
// ArrayList can be subclassed and given arbitrary behavior, but we can
// still deal with the common case where o is ArrayList precisely
boolean equal = (o.getClass() == ArrayList.class)
? equalsArrayList((ArrayList<?>) o)
: equalsRange((List<?>) o, 0, size);
checkForComodification(expectedModCount);
return equal;
}아래는 참고한 글이다.
http://theeye.pe.kr/archives/1499
https://codechacha.com/ko/java-remove-from-list-while-iterating/
