[F-Lab 모각코 챌린지 2일차] Immutable

부추·2023년 6월 2일
f-lab챌린지
0

F-Lab 모각코 챌린지

목록 보기
2/66

TIL

  1. 알고리즘 1문제 : 순위 검색
  2. JAVA Immutable 객체에 대하여

1. 순위 검색

개발 언어, 분야, 경력, 소울푸드, 그리고 점수에 따라 몇 명의 사람이 지원했는지 반환하는 문제였다.

일단 못풀었다! 정확도는 100점이었지만 효율성 면에서 시간초과가 났다.

from bisect import bisect_left
def solution(info, query):
    ans,people = [],[]
    for p in info:
        lang,field,career,food,s = p.split()
        s = int(s)
        people.append([s,lang,field,career,food])
    people.sort()
    score = [p[0] for p in people]
    
    for q in query:
        q_lang,_,q_field,_,q_career,_,q_food,q_score = q.split()
        q_score = int(q_score)
        
        # cut_index부터 살펴봄
        cut_index,pass_num = bisect_left(score,q_score),0
        for i in range(cut_index,len(score)):
            _,cur_lang,cur_field,cur_career,cur_food = people[i]
            if (q_lang!="-" and q_lang!=cur_lang):
                continue
            if (q_field!="-" and q_field!=cur_field):
                continue
            if (q_career!="-" and q_career!=cur_career):
                continue
            if (q_food!="-" and q_food!=cur_food):
                continue
                
            # 모든 조건 만족
            pass_num += 1
            
        ans.append(pass_num)
    return ans

풀이의 흐름은 직관적이다.

  1. info 리스트에 있는 지원자들의 정보를 split해서 people 리스트에 담는다.
  2. 지원자의 점수를 기준으로 정렬한다.
  3. query 리스트의 쿼리들을 하나씩 iterate한다. 최초의 기준은 테스트의 점수이다. 이분 탐색을 이용해서 cut_index를 구해 기준 점수 이상을 가진 지원자들을 추려낸다.
  4. 3번에서 얻은 지원자들을 하나씩 iterate해서 나머지 조건이 모두 맞으면 pass_num 변수에 1을 더해 쿼리 조건을 만족하는 지원자의 수를 늘린다.

지원자의 수, 즉 info 리스트의 최대 길이는 5,000이고 쿼리의 수, 즉 query 리스트의 최대 길이는 100,000이다. 이중 반복문을 쓰면 시간 초과가 나는데, 당장에 생각나는 것이 이것 밖에 없었다..!!


중첩 딕셔너리를 구현하려고 4시간을 넘게 붙잡고 있었는데, 오늘 하루 이 문제에 다 쏟아붓기엔 시간이 아까워서 일단 멈춘다. 머리 좀 식히고 내일 추가로 풀어볼 계획이다.



2. Immutable

1. Immutable 해야하는 이유

CS에서 말하는 Immutable은 "바뀌지 않음"이다. Immutable 객체란, 생성된 인스턴스의 내부 값이 변하지 않는 클래스를 말한다.

특별한 이유가 없는 한, 프로그래밍에서 객체는 최대한 불변으로 만드는 것이 좋다. 몇 가지 장점이 있기 때문이다.

1) 객체에 대한 신뢰성이 높아짐

객체에 저장된 상태값이 바뀔 가능성이 있는 프로그램에선 객체를 믿지 못한다. 객체를 생성할 때 설정했던 필드값이 바뀔 수도 있다면, 혹시 모를 사고를 피하기 위해 필드 값이 유효한지 검사하는 과정이 필요하다. 혹은 객체 데이터의 무결성을 확인하기 위해 불안에 떨며 프로젝트의 코드를 여기저기 뜯어봐야 할지도 모른다.

이는 생산성의 저하를 불러온다. '한 번 생성된 객체의 값은 변하지 않는다'를 원칙으로 세워놓으면 객체를 신뢰할 수 있다. 그로써 비즈니스 로직에 조금 더 집중할 수 있다.

2) thread-safe

자바의 멀티스레드 환경에서 가장 큰 문제는 공유 변수에 대한 data hazard이다. 한 스레드가 값을 쓰기도 전에 다른 스레드가 값을 읽는다든가, 여러 스레드가 같은 변수에 데이터를 써서 race condition이 발생한다든가 하는 것이 그 예시이다.

이는 힙에 공유되는 객체 데이터가 mutable하기 때문에 일어나는 문제이다. 사전에 "이 객체는 절대 변하지 않는 객체에요" 설정을 한다면 당연히 thread safe할 것이며, 동기화를 고려하지 않아도 돼 성능에도 긍정적 영향을 미칠 것이다.

3) set, map 등의 요소로 쓰기 적절

객체의 필드값이 바뀌면, 해당 객체의 로직을 구현하기 위해 override한 hashCode() 등의 동작도 바뀔 수 있다. 따라서 같은 객체라도 다른 해시값을 반환하여 이를 이용하는 hash set 등의 자료구조로 쓰기 어렵다. 그러나 객체가 immutable이라면 이같은 부수 효과를 고려하지 않고 마음 편히 이용할 수 있다.


2. Immutable 객체 만들기

불변 객체를 만들기 위해 Person 클래스로 예시를 하나 들었다. 나이, 이름, 가장 좋아하는 음식의 필드 값을 가진 클래스이다. getter와 setter 메소드를 하위에 따로 구현했다.

public class Person {
    String name;
    Food favoriteFood;

    public Person(String name, Food favoriteFood) {
        this.name = name;
        this.favoriteFood = favoriteFood;
    }
    
    // getter and setter..
}

추가로 Food 클래스는 이름 필드만을 가진 간단한 클래스이다.

public class Food {
    String name;
}

1) 생성자를 제외한 setter을 제거하자

일단, 당연히 Person은 Immutable이 아니다. @Setter을 통해 public setAge, public setName, public setFood 메소드를 만들었으므로 해당 메소드를 통해 너무나도 쉽게 객체의 필드값을 변화시키는 것이 가능하다.

그러므로 가장 첫번째로 생성자를 제외한 setter를 제거해, 객체 필드값을 변화시킬 수 있는 메소드를 없애야한다.

public class Person {
    String name;
    Food favoriteFood;

    public Person(String name, Food favoriteFood) {
        this.name = name;
        this.favoriteFood = favoriteFood;
    }
    
    // getters ..
}

2) 필드 값을 private final로 바꾸자

setter를 없애도, "인스턴스.변수명" 형식을 통해 객체 필드값에 직접 접근하여 값을 수정하면 말짱 도루묵이다. 외부에서 필드에 접근할 수 없도록 private 키워드를 추가하자.

또한 필드 값이 변하는 것을 사전에 막기 위해 아예 필드 자체를 final로 선언하자.

public class Person {
    private final String name;
    private final Food favoriteFood;

    public Person(String name, Food favoriteFood) {
        this.name = name;
        this.favoriteFood = favoriteFood;
    }
    
    // getters..
}

3) final class : 상속을 통한 꼼수 차단

여기서 끝이 아니다. Person을 상속받아서 해당 클래스를 mutable처럼 이용할 여지가 남아있다. Person 클래스를 상속받는 Woman 클래스를 보자.

public class Woman extends Person {
    private String newName;
    public Woman(String name, Food favoriteFood) {
        super(name,favoriteFood);
        newName = name;
    }
    public void setName(String name) {
        newName = name;
    }
    @Override
    public String getName() {
        return this.newName;
    }
}

newName 필드가 추가되었고, 해당 필드에 대한 getter와 setter를 추가했다. 기존 Person 클래스에도 getName() 메소드가 있으므로 getName()을 Override했는데, 이때 새로 추가한 newName 필드를 반환한다.

이렇게 하위 클래스에서 재정의가 일어나면, 캐스팅을 통해 객체의 의도하지 않은 동작이 일어날 수 있다.

public class FinalClass {
    public static void main(String[] args) {
        // up casting
        Person person = new Woman("부추", new Food("떡볶이"));
        
        // down casting
        Woman woman = (Woman) person;
        woman.setName("여자부추");
        
        // 여자부추?!
        System.out.println(person.getName());
    }
}
  • Person 클래스는 불변이기 때문에, 인스턴스를 하위 클래스로 생성했더라도 한 번 지정된 person의 name필드 "부추"는 바뀌지 않을 것이라 예상했다.
  • 그러나 Person을 상속받은 Woman 클래스로 다운캐스팅 후, 필드값을 수정한 뒤 Override한 메소드를 호출했더니 mutable로 동작했다.

이렇게 클래스의 상속을 허락하면, 하위 인스턴스를 만드는 꼼수를 통해 객체를 mutable처럼 동작하게 할 수 있다. 따라서 class 자체도 final로 만들어야한다!

public final class Person {
    private final String name;
    private final Food favoriteFood;

    public Person(String name, Food favoriteFood) {
        this.name = name;
        this.favoriteFood = favoriteFood;
    }

    // getters ..
}

4) 방어적 복사

Reference 타입에 final 키워드가 붙었다고 해서 해당 객체를 수정할 수 없다는 뜻은 아니다. Person 클래스의 멤버 변수인 Food 앞에 final이 붙어도, 다음과 같은 동작이 가능하다. favoriteFood 멤버변수 값을 맘대로 바꾸는 예시이다.

public class NoDefensive {
    public static void main(String[] args) {
        Person person = new Person("부추",new Food("떡볶이"));
        person.getFavoriteFood().setName("짜장면");
        
        // 짜장면
        System.out.println(person.getFavoriteFood().getName());
    }
}

Reference 타입은 Primitive 타입처럼 값 자체를 담고 있는 것이 아니라, 힙에서 참조할 인스턴스의 주소를 담고 있다. Reference 타입이 final이라는 것은 변수가 가리키는 객체 주소가 변하지 않는다는 뜻이지, 객체 내부의 값이 고정이라는 뜻은 아니다. getFavoriteFood()를 통해 받게되는 Food 객체는 어쨌든 항상 같은 주소의 객체이다.

이 때 쓸 수 있는 것이 방어적 복사이다. 객체가 가지고있는 참조변수 자체를 넘기지 않고 기존 객체와 똑같은 값을 가지는 새로운 객체를 생성해 반환하는 것을 방어적 복사라고 한다.

getFavoriteFood() 메소드를 다음과 같이 수정하자.

public Food getFavoriteFood() {
    return new Food(this.favoriteFood.getName());
}

이렇게 되면 Reference 타입 필드의 객체 원본이 아닌, 새로 생성된 Food 객체를 넘겨주게 된다. 이제 getFavoriteFood()를 통해 받은 Food 객체에 뭔 짓을 해도 Person이 가진 멤버변수에는 영향이 없을 것이다.


Immutable한 객체를 만들고 싶다면, mutable Reference 멤버 변수의 원본 객체를 직접 넘겨주는 일은 없도록 하자.
사실 Food 자체가 immutable이라면 이런 방어적 복사를 하지 않아도 된다. 객체 원본을 넘겨주더라도 원본 객체가 변할 일이 없기 때문이다. 여기서 객체를 immutable로 사용해야할 이유가 하나 더 늘었다!

List가 멤버 변수일 때

List와 같은 collection이 클래스의 멤버 변수이면 어떻게 해야할까?

  1. List 자체도 방어적 복사가 일어나야한다.
  2. List 각각의 요소들 역시 방어적 복사가 일어나야한다.

이번엔 Person 객체에 favoriteFoods라는 List 멤버변수를 만들고 이를 immutable 객체로 구현해보자.

public final class Person {
    private final String name;
    private final List<Food> favoriteFoods;

    public Person(String name, List<Food> favoriteFoods) {
        this.name = name;
        this.favoriteFoods = copy(favoriteFoods);
    }

    public String getName() {
        return this.name;
    }
    public List<Food> getFavoriteFoods() {
        return copy(favoriteFoods);
    }
    public List<Food> copy(List<Food> foods) {
        List<Food> copied = new ArrayList<>();
        foods.forEach(food -> copied.add(new Food(food.getName())));
        return copied;
    }
}

copy() 메소드가 중요하다. 인자로 들어온 collection 객체 자체와 각각의 요소에 대해 완전 방어적 복사를 하여 새로운 collection 객체를 반환한다.




REFERENCE

https://www.youtube.com/watch?v=EOGOJdBy2Rg

https://mangkyu.tistory.com/131

profile
부추
부추튀김인지 부추전일지 모를 정도로 빠싹한 부추전을 먹을래
이전 포스트

[F-Lab 모각코 챌린지 1일차] volatile?

다음 포스트

[F-Lab 모각코 챌린지 3일차] Annotation?

0개의 댓글