횡단보도에 파란불이 들어오면 반대편 지역으로 이동할 수 있으며 이동하는 데 1분이 걸린다. 1 + i ( 0 <= i < M) 번째 신호는 i, M+i, 2M+i, 3M+i, ... 분 주기에 시작해서 1분 동안 Ai 번 지역과 Bi 번 지역을 잇는 횡단보도에 파란불이 들어오고, 다른 모든 횡단보도에는 빨간불이 들어온다. 한 주기 동안 같은 횡단보도에 파란불이 여러 번 들어올 수 있다.
횡단보도와 신호의 정보가 주어질 때, 시간 0 분에서 시작해서 1 번 지역에서 N 번 지역까지 가는 최소 시간을 구하시오.
2.문제예제
3.문제풀이(수동)
예제 풀이 2번을 수동 풀이한다.
구간
시간
3 - 4
1분, 13분, 25분, 37분...
5 - 6
2분, 14분, 26분, 38분...
7 - 8
3분, 15분, 27분, 39분...
2 - 3
4분, 16분, 28분, 40분...
1 - 5
5분, 17분, 29분, 41분...
...
... (생략) ...
각 횡단보도가 켜지는 시간대는 위 표와 같다. 내가 만약 7 - 8 번 구간을 처음에 선택하였다면 그 다음 구간을 선택할 때 걸리는 시간이 시계방향처럼 연산된다. 그 다음 1 - 5 번 구간을 선택하면 +2 가 되고, 3 - 4 번 구간을 선택하면 한 바퀴 돌아서 +10 이 된다. 그 다음 구간의 시간 대가 현재 시간 대보다 적다면 한 바퀴 돌아서 연산된다.
위 글에서는 자바 제네릭의 한계 때문에 런타임 시 타입을 확인하기 위해 타입 토큰을 사용하여 타입 안전 이종 컨테이너(THC Pattern(Typesafe Heterogenous Container Pattern)) 를 활용한다고 하지만, 책에서는 제네릭 확장 개념으로 설명하고 있다. Set<E>, Map<K, E> 처럼 제네릭은 매개변수를 한 개나 두 개 정도 밖에 사용을 못 하는데 더 확장하여 사용하고 싶지 않냐는 식이었다. 사실 취지가 마음에 와닿지는 않았다.
그래도 개념은 동일하다. 타입 안전 이종 컨테이너(THC Pattern(Typesafe Heterogenous Container Pattern))는 컨테이너 대신 키를 매개변수화한 다음, 컨테이너에 값을 꺼내거나 뺄 때 매개변수화한 키를 활용한다는 것이다.
// 선언부publicclassSimpleTypeSafeMap{
private Map<Class<?>, Object> map = new HashMap<>();
public <T> voidput(Class<T> k, T v){
map.put(Objects.requireNonNull(k), v);
}
public <T> T get(Class<T> clazz){
return clazz.cast(map.get(clazz));
}
}
// 사용부
simpleTypeSafeMap.put(String.class, "테스트");
simpleTypeSafeMap.put(Integer.class, 1);
String string1 = simpleTypeSafeMap.get(String.class);
Integer integer1 = simpleTypeSafeMap.get(Integer.class);
위 글 예제와 같다. HashMap Key 에 타입 토큰을 지정하여 값을 로드하고 저장하면 된다.
여기서 중요한 점은 키가 Class<?> 이라서 비한정적 와일드 카드이기 때문에 Map 안에 아무것도 못 넣을 수 있다고 생각할 수 있지만(타입을 체크하지 못하므로), 컨테이너 입장에서는 중첩되어 있기 때문에 Key 만 와일드카드 타입이기 때문에 모든 키가 가능하다. 또 맵의 값 타입이 Object 이기 때문에 이 맵은 키와 값 사이의 타입 관계를 보증하지 않는다. 하지만 메서드들에서 타입을 가져와 동적 캐스팅해 로드하고 타입을 키로 지정해 저장하기 때문에 상관없다. Map 자체로는 안전하지 않지만, 메서드들에서 이를 보장한다.
안전해보이지만, 아직 두 가지 제약이 존재한다.
첫 번째 제약은 클라이언트가 아래와 같이 Generic 타입이 아닌 Raw 타입을 전달하면 타입 안전성이 깨지게 된다. HashSet 이나 HashMap 같은 일반 컬렉션에 Raw 타입을 사용하는 것처럼 말이다.
map.put((Class)Integer.class, "hello");
int testInteger = map.get(Integer.class);
// 닮은 꼴 예제
HashSet<Integer> set = new HashSet<>();
((HashSet)set).add("hello");
단순히 cast 메서드는 Class 객체가 알려주는 타입의 인스턴스인지를 검사한 다음, 맞다면 그대로 반환하고 아니면 ClassCastException 예외를 던지기 때문이다. get 메서드에서는 cast 메서드로 맞는 타입인지 점검하는 반면에 put 메서드에서는 점검하지 않으므로 생기는 문제이다. 컴파일 타임 때 모두 점검하기 위해서 아래와 같이 코드를 수정하자.
public <T> voidput(Class<T> k, T v){
map.put(Objects.requireNonNull(k), type.cast(v));
}
type.cast 로 명시한 타입과 같은지 체크한다. 그냥 동적 형변환을 사용하면 된다. java.util.Collections 의 checkedSet, checkedList, checkedMap 과 같은 메서드들이 위와 같은 구조를 사용한다고 한다.
두 번째 제약은 제네릭(실체화 불가 타입)은 사용할 수 없다. 위 글에서 소개한 것처럼 제네릭에 대한 타입 토큰이나 클래스 리터럴이 준비되어 있지 않기 때문이다. 예를 들어 List<String>와 List<Integer> 는 List.class 클래스 객체를 공유하므로 타입 안전성이 깨지게 된다. 위 글에서 소개한 것처럼 슈퍼 타입 토큰 방식으로 처리해야 한다.
현재는 어떤 Class 객체든 받아들이는데 간혹 메서드들이 허용하는 타입을 제한하고 싶을 때가 있다. 그 때 한정적 타입 매개변수나 한정적 와일드카드를 사용하면 된다. 특히 애너테이션 API 가 한정적 타입 토큰을 적극적으로 사용한다.
public <T extends Annotation> T getAnnotation(Class<T> annotationType);
이 getAnnotation 메서드는 대상 요소에 달려있는 애너테이션을 런타임 때 읽어오는 기능을 한다. 토큰으로 명시한 타입의 애너테이션이 대상 요소에 달려 있다면 그 애너테이션을 반환하고 없다면 null 을 반환한다. THC 컨테이너다. (annotationType 인수가 한정적 타입 토큰으로 선언되어 있는 것을 볼 수 있다.)
만약 Class<?> 타입의 객체가 있고, 이를 getAnnotation 처럼 한정적 타입 토큰을 받는 메서드에 넘기려면 어떻게 해야 할까? Class<? extends Annotation> 은 비검사 형변환이므로 컴파일 경고가 떠서 안 되고, asSubclass 메서드로 동적 형변환 해야한다. 인자로 받은 클래스 객체로 형변환해준다. 컴파일 시점에는 알 수 없으나 런타임 때 읽어낼 수 있는 메서드이다.
"일반적인 제네릭은 한 컨테이너가 다룰 수 있는 타입 매개변수의 수가 고정되어 있다.
하지만 컨테이너 자체가 아닌 키를 타입 매개변수로 바꾸면 이런 제약이 없는 THC 컨테이너를 만들 수 있다."
자바 제네릭은 클래스에서 사용할 타입을 외부(사용부)에서 사용하게 해주는 일반적인 기법을 의미한다.
이러한 제네릭을 사용하면, 타입만 다르고 공통된 기능을 가지고 있는 클래스나 메서드들에 파라미터로 타입을 외부에서 전달받아 조금 더 범용적인 코드를 만들 수 있다. 이러한 제네릭이 없었다면, 자바 객체의 최고 조상인 Object 로 전달받아 객체 타입에 따라 캐스팅해 로직을 별도로 만들어야 되는데 이러면 오히려 런타임 시 예기치 못한 오류가 더 많이 발생하고 별도의 타입으로 만들어둔 클래스 및 함수들과 다를 바 없다.
publicclassGeneric{
public List<String> list = new ArrayList<>();
publicvoidaddString(String str){
list.add(str);
}
public String getString(int index){
return list.get(index);
}
}
// 제네릭이 아니라면, 이렇게 Object 로 전달publicclassNonGeneric{
public List list = new ArrayList();
publicvoidaddString(Object obj){
list.add(obj);
}
// 원하는 타입으로 캐스팅 해 반환public String getString(int index){
return (String) list.get(index);
}
}
그런데 자바 제네릭은 다른 언어의 제네릭과 달리 다른 점이 존재한다.
제네릭 도입 이후, 컴파일 타임 때까지는 타입 안전성을 얻을 수 있었지만, Type Erasure 기능으로 인해 컴파일 이후에는 타입이 소거가 되기 때문이다. 반쪽 제네릭이라고 불리우는 이유이다.
Class Test<T> {
private T value;
publicTest(T t){
this.value = t;
}
public T get(){
return value;
}
}
// -> 컴파일 이후
Class Test {
private Object value;
publicTest(Object t){
this.value = t;
}
public Object get(){
return value;
}
}
컴파일 타임 이후에 Object 로 변환이 된 것을 볼 수 있다. 컴파일 때까지만 타입 안전성을 제공하고, 그 이후에는 Object 로 변환이 되기 때문에 런타임 시에는 오류가 발생할 수도 있다.
자바 진영에서는 동세대 언어인 C# 과 다르게 보급률이 좋아서 현업 프로젝트들이 월등히 많았고 이러한 프로젝트들을 지키고자 하위 호완성을 위해 Type Erasure 를 도입했다고 한다. 컴파일 타임 때 Type Erasure 를 수행하면서 제네릭이 없던 하위 버전들과 동일한 형태로 class 파일을 생성할 수 있었다.
2. 타입 토큰의 등장
자바언어 개발자였던 Neal Gafter는 JAVA JDK5에 generics를 추가할 때 java.lang.Class 가 generic type이 되도록 변경했다고 한다. 예를 들어, String.class 의 Type 이 Class<String> 되도록 만들어 주었다. 그리고 이를 타입 토큰이라고 불렀다.
클래스 리터럴과 타입 토큰의 차이
클래스 리터럴은 어떤 클래스인지 파라미터로 전달되는 정보로 타입 토큰의 클래스 정보이다. 타입 토큰과 동일한 개념으로 타입 토큰은 클래스의 타입을 명시하고, 클래스 리터럴은 그 타입 토큰과 매칭되는 매개변수로 보면 된다.
제네릭만 사용했을 때, Operation 이나 타입들의 메서드들이 동일해야 사용할 수 있다는 한계가 있긴 하지만 그래도 동일한 기능을 한 코드로 만들 수 있어 좋다. 그런데 원하는 타입으로 반환은 안 된다. 아까 위에서 언급한 것처럼 타입이 모두 Object 로 변환되기 때문에 타입 캐스팅이 되지 않는다. 이 때 타입 토큰이 유용하게 사용된다.
위 예제처럼, valueType 으로 클래스 타입을 매개변수로 전달해주면 json 을 읽어 그 타입으로 반환해줄 수 있다.
조금 더 나아가 THC (Typesafe Heterogenous Container) Pattern 으로 사용될 수 있다.
// 선언부publicclassSimpleTypeSafeMap{
private Map<Class<?>, Object> map = new HashMap<>();
public <T> voidput(Class<T> k, T v){
map.put(k, v);
}
public <T> T get(Class<T> clazz){
return clazz.cast(map.get(clazz));
}
}
// 사용부
simpleTypeSafeMap.put(String.class, "테스트");
simpleTypeSafeMap.put(Integer.class, 1);
String string1 = simpleTypeSafeMap.get(String.class);
Integer integer1 = simpleTypeSafeMap.get(Integer.class);
타입 토큰을 키로 사용해 타입끼리 저장하고 다시 그 타입 토큰으로 캐스팅해서 가져올 수 있다. 타입 안전 이종 컨테이너라고 불리우며 영어로는 THC (Typesafe Heterogenous Container) 라고 한다. 컨테이너가 타입을 체크해서 컴파일 여부를 결정하는 것이 아니라 타입 토큰을 가지고 프로그래머가 직접 핸들링하는 개념이다.
3. 슈퍼 타입 토큰의 등장
타입 토큰의 한계
이 타입 토큰에도 한계는 있다. 제네릭 타입의 클래스 리터럴과 타입 토큰은 존재하지 않는다. Type Erasure 때문에 <> 내부에 있는 타입들이 제거되기 때문이다. 조금 더 쉽게 생각해보면 이중 삼중... 다중 타입에 대한 정보들을 가지고 있지 않아서 그렇다. 이러한 타입 토큰의 한계를 극복한 개념이 슈퍼 타입 토큰이다.
슈퍼 타입 토큰
다중 타입에 대한 정보들을 리터럴로 표현할 수 있으면 타입 토큰처럼 안전성을 확보할 수 있을 것이다.
Class.getGenericSuperclass() 와 ParameterizedType.getActualTypeArguments() 를 사용해서 전체 타입에 대한 정보와 실제 타입을 가져올 수 있다.
classSuper<T> {}
classMyClassextendsSuper<List<String>> {}
MyClass myClass = new MyClass();
Type typeOfGenericSuperclass = myClass.getClass().getGenericSuperclass();
// ~~~$1Super<java.util.List<java.lang.String>> 출력됨
System.out.println(typeOfGenericSuperclass);
해당 객체의 상위 클래스 타입을 반환하는 메서드. 만약 상위 클래스가 매개변수화된 타입이라면 소스코드에서 사용된 실제 타입들을 반영해 반환해야 한다. 매개변수화된 타입에 대한 내용은 별도의 문서를 확인하라고 적혀 있다.(ParameterizedType은 제네릭 타입을 가지고 있는 타입을 말한다.)
제네릭 타입이라면, getActualTypeArguments 메서드를 통해 이 제네릭의 실제 타입을 가져올 수 있다.
classSuper<T> {}
classMyClassextendsSuper<List<String>> {}
MyClass myClass = new MyClass();
Type typeOfGenericSuperclass = myClass.getClass().getGenericSuperclass();
// ~~~$1Super<java.util.List<java.lang.String>> 출력됨
System.out.println(typeOfGenericSuperclass);
// 수퍼 클래스가 ParameterizedType 이므로 ParameterizedType으로 캐스팅 가능// ParameterizedType의 getActualTypeArguments()으로 실제 타입 파라미터의 정보를 구함
Type actualType = ((ParameterizedType) typeOfGenericSuperclass).getActualTypeArguments()[0];
// java.util.List<java.lang.String>가 출력됨
System.out.println(actualType);
슈퍼 타입 토큰 예제
// 선언부publicabstractclassTypeReference<T> {
privatefinal Type type;
protectedTypeReference(){
Type superClassType = getClass().getGenericSuperclass();
if (superClassType instanceof ParameterizedType) {
this.type = ((ParameterizedType)superClassType).getActualTypeArguments()[0];
} else {
thrownew IllegalArgumentException("TypeReference는 항상 실제 타입 파라미터 정보가 있어야 합니다.");
}
}
public Type getType(){
return type;
}
}
// 사용부publicclassTypeSafeMap{
privatefinal Map<Type, Object> map = new HashMap<>();
public <T> voidput(TypeReference<T> k, T v){
map.put(k.getType(), v);
}
public <T> T get(TypeReference<T> k){
final Type type = k.getType();
final Class<T> clazz;
if (type instanceof ParameterizedType) {
clazz = (Class<T>) ((ParameterizedType) type).getRawType();
} else {
clazz = (Class<T>) type;
}
return clazz.cast(map.get(type));
}
}
Class.getGenericSuperclass() 와 ParameterizedType.getActualTypeArguments() 를 활용해서 실제 RawType 를 가져온다.
4. 프레임워크의 슈퍼 타입 토큰
이렇게 매번 직접 만들기에는 수고스럽다. 프레임워크에서도 이런 슈퍼 타입 토큰을 지원한다.
Spring 의 ParameterizedTypeReference
Spring 프레임워크에서도 동일하게 런타임 시 발생하는 타입 안정성 문제를 해결하기 위해 ParameterizedTypeReference라는 클래스를 만들었다. 매개변수화된 타입에 대한 정보를 가져올 때 사용하면 된다. 클래스 리터럴을 전달하는 대신 아래와 같이 사용하면 된다. new ParameterizedTypeReference<List<User>>()
publicclassMain{
publicstaticvoidmain(String[] args){
Lamp lamp = new Lamp();
Command lampOnCommand = new LampOnCommand(lamp);
Alarm alarm = new Alarm();
Command alarmStartCommand = new AlarmStartCommand(alarm);
Button button1 = new Button(lampOnCommand);
button1.pressed();
Button button2 = new Button(alarmStartCommand);
button2.pressed();
button2.setCommand(lampOnCommand);
button2.pressed();
}
}
Button 에 한 단계 추상화 한 Command 를 부착할 수 있게 만들어 두고, 그 Command 의 메서드로 각각의 구현체가 동작하는 방식이다.
리팩토링 관점에서 보면...
사실 처음부터 설계하는 것보다는 기존의 코드를 수정할 일이 더 많다.
"명령" 과 "수행" 이라는 관점에서 커맨드 패턴을 떠올려 리팩토링할 수도 있지만, 조금 더 범용적인 관점에서 문제코드의 문제점을 해결할 수 있어야 커맨드 패턴을 처음 만든 프로그래머들의 취지를 이해할 수 있다고 생각한다.
커맨드 패턴을 알지 못 한 시점에서 해당 코드를 보고 무슨 문제점이 있는지 다시 살펴보자.
조건문(if 문이나 switch 문)에 각각 객체들이 포진되어 있고, 요구사항이 늘어날 때마다 결합되는 객체의 갯수와 조건문이 점점 커진다. 이 말은 고차원에서 저차원으로 가는데 저차원의 모듈 갯수가 현저히 많아 생긴 문제이다. 앞서 소개한 커맨드 패턴으로 예를 들면, 명령을 할 때 버튼을 눌러서 명령할 수도 있고, 손가락을 지시하여 명령할 수도 있다. 명령을 받는 주체는 그 명령을 받아 명령을 수행한다.
명령한다 => 버튼을 눌러서 명령한다 or 손가락을 지시하여 명령한다. => 램프를 킨다. or 알람을 설정한다. or 자동차 시동을 건다 등등
명령을 내리는 주체보다 명령을 받는 주체가 점점 많아지므로 DIP 원칙에서도 설명하였듯이 항상 저차원의 갯수가 많다. 따라서 고차원과 저차원의 모듈이 강하게 결합이 되는 것을 막으려면 한 단계를 추상화해 변수를 만들고 그 변수를 중간 매개체로 삼아 연결해야 한다. 그 매개체가 인터페이스이다. 이 인터페이스를 합성으로 고차원에 연결하면 앞서 소개한 커맨드 패턴이 되는 것이다.
결국 커맨드 패턴은 DIP 와 합성을 "명령" + "실행" 관점으로 바라본 디자인 패턴이다.
조건문이 계속 커지고 그 조건문 내에 객체의 갯수가 많아지면 인터페이스로 분리하여 합성하자.
일렬로 나열된 n 개의 풍선이 있다. 풍선들을 아래 규칙에 따라 단 1개만 남을 때까지 하나씩 터트린다고 할 때 최후까지 남기는 것이 가능한 풍선들의 갯수를 구하시오.
임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트린다.
터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킨다.
번호가 더 작은 풍선을 터트리는 행위는 한 번만 수행할 수 있다.
2.문제예제
[9,-1,-5] 풍선이 주어질 때 다음과 같다.
첫 번째 풍선(9가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
[9, -1, -5]에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
[9, -5]에서 9, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
두 번째 풍선(-1이 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
[9, -1, -5]에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
[-1, -5]에서 -1, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
세 번째 풍선(-5가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
[9, -1, -5]에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
[-1, -5]에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
3개의 풍선이 최후까지 남을 수 있으므로, 3을 return 해야 합니다.
3.팩트추출
Fact 1: 숫자가 낮은 풍선을 터트리는 행위는 한 번만 할 수 있으므로 모든 조합을 탐색할 필요는 없다. 탐색 방향에 맞춰 조합을 쪼개 규칙성을 찾는다. 일부 조합의 결과를 찾는 알고리즘과 전체 조합의 결과를 찾는 알고리즘이 같다면 DP 이다.
일단, 풍선의 갯수를 n 이라고 가정하고 n 이 점차 증가했을 때 규칙성을 찾아본다.
1) n 이 1 일 때,
무조건 풍선이 남아 있으므로 1 반환
2) n 이 2 일 때,
1번 풍선이 작고 2 번 풍선이 큰 경우와 1번 풍선이 크고 2번 풍선이 작은 경우로 나눌 수 있다.
낮은 풍선을 터트리는 찬스 없이도 큰 걸 제거할 수 있으므로 2 반환
3) n 이 3 일 때, 가운데 풍선을 기준으로 4 가지 경우의 수로 나눌 수 있다.
3-1) 왼쪽이 작고 오른쪽이 큰 경우
1
2
3
1번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 2 생존
2번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 3 생존
2번을 제거하고 3번을 제거하면(큰 것 => 큰 것 순) 1 생존
3-2) 왼쪽이 크고 오른쪽이 작은 경우
3
2
1
1번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 2 생존
2번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 3 생존
2번을 제거하고 3번을 제거하면(큰 것 => 큰 것 순) 1 생존
= 3-1 경우의 수와 같다.
3-3) 왼쪽도 작고 오른쪽도 작은 경우
1
3
2
1번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 2 생존
3번을 제거하고 2번을 제거하면 (큰 것 => 큰 것 순) 1 생존
3번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 2 생존
2번을 제거하고 3번을 제거하면(작은 것 => 큰 것 순) 1 생존
= 모든 경우의 수를 살펴봐도 중간값은 생존이 되지 않는다.
3-4) 왼쪽도 크고 오른쪽도 큰 경우
2
1
3
2번을 제거하고 3번을 제거하면 (큰 것 => 큰 것 순) 1 생존
2번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 3 생존
3번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 2 생존
현재 값보다 양 옆에 있는 숫자가 모두 작은 경우에만 생존하지 못 한다.
Fact 2 : 이전 결과 값이 그 다음에 영향을 미치지 않고 작은 문제들의 정답이 전체 문제의 정답이 되는 규칙성은 발견되지 않았다. (거의 모든 경우의 숫자가 살아 남으므로) 따라서 DP 나 분할 정복 문제는 아니다. 그러나 생존하지 못 하는 경우의 수로 보면 두 구역 모두 현재 숫자보다 작을 때 한 가지 경우의 수 밖에 없다. 따라서 경우의 수가 적은 여집합을 구한다.
Fact 3: n 이 4일 때, 5일 때도 같은 규칙성이 존재하는지 확인한다. 작은 풍선을 제거하는 규칙을 사용하지 않고 큰 값만 골라 왼쪽, 오른쪽에서 제거한다면 항상 작은 값들만 배치하게 된다. 그렇게 n 이 3일 때로 만들고 위 규칙을 적용하면 결과값이 동일하다. 구역을 확장해도 해당 규칙에는 문제가 없다.
4.문제전략
부분 문제로 보이지 않고 규칙성이 보이지 않으므로 완전 조합 문제로 풀어야 한다. 하지만 생존을 못 하는 여집합 경우의 수는 한 가지이므로 이 점을 고려하여 두 구역의 최솟 값보다 큰 경우의 숫자만 찾아 제외시켜 문제를 풀면 된다.
5. 소스코드
classSolution{
publicintsolution(int[] a){
int count = 0;
if (a.length == 1) return1;
if (a.length == 2) return2;
int leftMin = a[0];
int rightMin[] = newint[a.length];
rightMin[a.length-1] = a[a.length-1];
for (int i = a.length - 2; i > 0; i--)
rightMin[i] = Math.min(rightMin[i + 1], a[i]);
for (int i = 0; i < a.length; i++) {
if (!(leftMin < a[i] && rightMin[i] < a[i]))
count++;
leftMin = Math.min(leftMin, a[i]);
}
return count;
}
}
이 회사는 다단계 판매 업무를 하고 있다. 초대 받은 사람의 이익 10 퍼센트를 초대한 사람이 가지는 시스템인데 중앙에 있는 Center 까지 거슬러 올라가 모두 이익금을 나누어 가져야 한다.
판매원의 이름을 담은 배열 enroll, 각 판매원을 다단계 조직에 참여시킨 다른 판매원의 이름을 담은 배열 referral, 판매량 집계 데이터의 판매원 이름을 나열한 배열 seller, 판매량 집계 데이터의 판매 수량을 나열한 배열 amount가 매개변수로 주어질 때, 각 판매원이 득한 이익금을 나열한 배열을 구하시오.
2.문제예제
emily 가 450 원을 벌었다면, mary 는 10 퍼센트인 45 원을 가지게 되고, center 는 45원의 10 퍼센트인 40원을 가지게 된다.
3.팩트추출
Fact 1: 어렴풋이 보면 트리 자료구조 문제로 보일 수 있으나 enroll 입장에서 보면 부모가 하나이기 때문에 항상 일차원적인 구조이다. 따라서 부모노드까지 계속 재귀호출하면서 이익금을 계산해주면 된다. enroll 의 갯수만큼 반복문을 수행하고 이익금을 나누어 가지면 된다.
4.문제전략
트리 문제라고 속지만 않으면 된다. enroll 을 순회하면서 이익금을 계산하면 된다.
5. 소스코드
import java.util.*;
classSolution{
staticclassPerson{
String name;
Person parent;
int sellAmount;
publicPerson(String name, Person parent, int sellAmount){
this.name = name;
this.parent = parent;
this.sellAmount = sellAmount;
}
publicvoidcalculateMultiLevel(int amount){
int parentAmount = amount / 10;
this.sellAmount += amount - parentAmount;
if (this.parent != null && parentAmount >= 1) {
this.parent.calculateMultiLevel(parentAmount);
}
}
}
privatestatic HashMap<String, Person> childParent;
publicint[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
childParent = new HashMap<>();
for (String enrollP: enroll) {
childParent.put(enrollP, new Person(enrollP, null, 0));
}
for (int i = 0; i < enroll.length; i++) {
if (!referral[i].equals("-")) {
childParent.get(enroll[i]).parent = childParent.get(referral[i]);
}
}
for (int i = 0; i < seller.length ; i++) {
childParent.get(seller[i]).calculateMultiLevel(amount[i] * 100);
}
int[] result = newint[enroll.length];
for (int i = 0; i < result.length; i++) {
result[i] = childParent.get(enroll[i]).sellAmount;
}
return result;
}
}
