- 알고리즘 1문제 : 순위 검색
- JAVA Immutable 객체에 대하여
개발 언어, 분야, 경력, 소울푸드, 그리고 점수에 따라 몇 명의 사람이 지원했는지 반환하는 문제였다.
일단 못풀었다! 정확도는 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
풀이의 흐름은 직관적이다.
info
리스트에 있는 지원자들의 정보를 split
해서 people
리스트에 담는다.query
리스트의 쿼리들을 하나씩 iterate한다. 최초의 기준은 테스트의 점수이다. 이분 탐색을 이용해서 cut_index
를 구해 기준 점수 이상을 가진 지원자들을 추려낸다.pass_num
변수에 1을 더해 쿼리 조건을 만족하는 지원자의 수를 늘린다.지원자의 수, 즉 info
리스트의 최대 길이는 5,000이고 쿼리의 수, 즉 query
리스트의 최대 길이는 100,000이다. 이중 반복문을 쓰면 시간 초과가 나는데, 당장에 생각나는 것이 이것 밖에 없었다..!!
CS에서 말하는 Immutable은 "바뀌지 않음"이다. Immutable 객체란, 생성된 인스턴스의 내부 값이 변하지 않는 클래스를 말한다.
특별한 이유가 없는 한, 프로그래밍에서 객체는 최대한 불변으로 만드는 것이 좋다. 몇 가지 장점이 있기 때문이다.
객체에 저장된 상태값이 바뀔 가능성이 있는 프로그램에선 객체를 믿지 못한다. 객체를 생성할 때 설정했던 필드값이 바뀔 수도 있다면, 혹시 모를 사고를 피하기 위해 필드 값이 유효한지 검사하는 과정이 필요하다. 혹은 객체 데이터의 무결성을 확인하기 위해 불안에 떨며 프로젝트의 코드를 여기저기 뜯어봐야 할지도 모른다.
이는 생산성의 저하를 불러온다. '한 번 생성된 객체의 값은 변하지 않는다'를 원칙으로 세워놓으면 객체를 신뢰할 수 있다. 그로써 비즈니스 로직에 조금 더 집중할 수 있다.
자바의 멀티스레드 환경에서 가장 큰 문제는 공유 변수에 대한 data hazard이다. 한 스레드가 값을 쓰기도 전에 다른 스레드가 값을 읽는다든가, 여러 스레드가 같은 변수에 데이터를 써서 race condition이 발생한다든가 하는 것이 그 예시이다.
이는 힙에 공유되는 객체 데이터가 mutable하기 때문에 일어나는 문제이다. 사전에 "이 객체는 절대 변하지 않는 객체에요" 설정을 한다면 당연히 thread safe할 것이며, 동기화를 고려하지 않아도 돼 성능에도 긍정적 영향을 미칠 것이다.
객체의 필드값이 바뀌면, 해당 객체의 로직을 구현하기 위해 override한 hashCode() 등의 동작도 바뀔 수 있다. 따라서 같은 객체라도 다른 해시값을 반환하여 이를 이용하는 hash set 등의 자료구조로 쓰기 어렵다. 그러나 객체가 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;
}
일단, 당연히 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 ..
}
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..
}
여기서 끝이 아니다. 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());
}
}
이렇게 클래스의 상속을 허락하면, 하위 인스턴스를 만드는 꼼수를 통해 객체를 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 ..
}
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());
}
}
이 때 쓸 수 있는 것이 방어적 복사이다. 객체가 가지고있는 참조변수 자체를 넘기지 않고 기존 객체와 똑같은 값을 가지는 새로운 객체를 생성해 반환하는 것을 방어적 복사라고 한다.
getFavoriteFood() 메소드를 다음과 같이 수정하자.
public Food getFavoriteFood() {
return new Food(this.favoriteFood.getName());
}
이렇게 되면 Reference 타입 필드의 객체 원본이 아닌, 새로 생성된 Food 객체를 넘겨주게 된다. 이제 getFavoriteFood()를 통해 받은 Food 객체에 뭔 짓을 해도 Person이 가진 멤버변수에는 영향이 없을 것이다.
List와 같은 collection이 클래스의 멤버 변수이면 어떻게 해야할까?
이번엔 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 객체를 반환한다.