카카오 신입 공채 1차 코딩 테스트에 있는 알고리즘 문제를 풀어봅니다.
다트 게임(난이도: 하) 알고리즘 문제
상편
“점수|보너스|[옵션]”으로 이루어진 문자열 3세트. 이므로,
"1S","1D","1T"와 같은 "점수|보너스"는 반드시 존재합니다.
점수객체, 보너스객체, 점수객체+보너스객체(Object Compoistion[조합 객체])를 만들어 역할을 담당하게 합니다.
1. 다트 포인트 객체 생성 ("2S","2D","2T") - 앞쪽 숫자
알고리즘 규칙 2. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
먼저 테스트 코드를 만들어봅니다. (10점이지만 20점 까지로 해보았습니다.)
package kakao.dart;
import org.junit.Test;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.core.Is.is;
public class BasicPointTest {
@Test
public void 포인트_제한_0에서_20() {
for (int i = 0; i < 20; i++) {
new PointNumber(String.valueOf(i));
}
}
@Test (expected = IllegalArgumentException.class)
public void 포인트_최대값_초과_21() {
new PointNumber("21");
}
}해당 조건에 부합하는 객체를 만듭니다.
package kakao.dart;
public class PointNumber {
private static final Long MIN_NUMBER = 0l;
private static final Long MAX_NUMBER = 20l;
private Long number;
public PointNumber(String numeric) {
if (numeric == null) throw new IllegalArgumentException();
Long number = Long.valueOf(numeric);
if (outOfNumber(number)) throw new IllegalArgumentException();
this.number = number;
}
private boolean outOfNumber(Long number) {
return number < MIN_NUMBER || MAX_NUMBER < number;
}
public long toLong() {
return number;
}
}기본 점수 객체를 만들어 놓으면, 이후에 객체 사용시 validation check(null, invalid value)에 대한 부담을 줄일 수 있습니다.
다트 게임은 0~20까지의 점수를 기준으로 했습니다. (bull (Single bull, Double bull)은 제외했습니다.)
outOfNumber() : 생성시 핵심 로직으로 작동합니다.
2. 다트 보너스 객체 생성 ("2S","2D","2T") - 뒷쪽 문자
알고리즘 규칙 3. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수^1 , 점수^2 , 점수^3 )으로 계산된다.
@Test
public void 보너스_계산() {
assertThat(2l, is(Bonus.SINGLE.calculate(2)));
assertThat(4l, is(Bonus.DOUBLE.calculate(2)));
assertThat(8l, is(Bonus.TRIPLE.calculate(2)));
}
계산을 했을경우 왼쪽의 값과 같도록 테스트코드를 만들었습니다.
package kakao.dart;
import java.util.Arrays;
import java.util.function.Function;
public enum Bonus {
SINGLE("S", value -> value),
DOUBLE("D", value -> (long) Math.pow(value, 2)),
TRIPLE("T", value -> (long) Math.pow(value, 3));
private String shortName;
private Function<Long, Long> expression;
Bonus(String shortName, Function<Long, Long> expression) {
this.shortName = shortName;
this.expression = expression;
}
public long calculate(long value) {return expression.apply(value);}
public static Bonus getByShortName(String shortName) {
return Arrays.asList(Bonus.values()).stream()
.filter(bonus -> bonus.shortName.equals(shortName))
.findFirst()
.orElseThrow(IllegalArgumentException::new);
}
}java8에서 개발했기 때문에 Function<Long, Long>이 가능케 되는데요.
자세한 내용은 우아한 형제의 이동욱님께서 작성한 Java Enum 활용기를 참고하세요~
java 7에서 하는 방법도 나와있답니다 :)
calculate() : 핵심로직으로 제곱 연산을 담당합니다.
3. 조합 객체 만들기
“점수|보너스|[옵션]”으로 이루어진 문자열
3세트.알고리즘 규칙 8. Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
다트 포인트와 보너스는 항상 붙어 다니므로, 1개의 객체로 취급합니다.
@Test (expected = IllegalArgumentException.class)
public void 포인트_보너스_부재() {
new BasicPoint("1");
}
@Test
public void 포인트_계산() {
assertThat(2L, is(new BasicPoint("2S").calculate()));
assertThat(4L, is(new BasicPoint("2D").calculate()));
assertThat(8L, is(new BasicPoint("2T").calculate()));
}package kakao.dart;
import java.util.Optional;
public class BasicPoint {
private static final String POINT_MATCH = "[^\\d]{1,2}";
private PointNumber pointNumber;
private Bonus bonus;
public BasicPoint(String text) {
if (text == null || text.isEmpty()) throw new IllegalStateException();
pointNumber = matchPoint(text);
bonus = matchArea(text);
}
private PointNumber matchPoint(String text) {
return new PointNumber(Optional.of(text.split(POINT_MATCH)).orElseThrow(IllegalArgumentException::new)[0]);
}
private Bonus matchArea(String text) {
return Bonus.getByShortName(text.substring(text.length()-1));
}
public Long calculate() {
return bonus.calculate(pointNumber.toLong());
}
}optional.of()는 단순히 if문을 줄이기 위해 사용하였습니다.
matchPoint, matchArea 매쏘드 에서 의도한 값이 들어오지 않으면 IllegalStateException을 던지도록 하였습니다.
이렇게 해서 다트 게임의 필수 값을 구현했습니다.
객체를 객체답게 사용하기위해
규칙 1: 한 메서드에 오직 한 단계의 들여쓰기만 한다.
규칙 2: else 예약어를 쓰지 않는다.
규칙 3: 모든 원시값과 문자열을 포장한다.
규칙 6: 모든 엔티티를 작게 유지한다.
규칙 7: 2개 이상의 인스턴스 변수를 가진 클래스를 쓰지 않는다.
규칙 8: 일급 콜렉션을 쓴다.
규칙 9: 게터/세터/프로퍼티를 쓰지 않는다.
출처 : 효과적으로 TDD, 리팩토링, OOP를 연습하는 방법
하편
4. 옵션 객체 생성
스타상과 아차상이 존재하죠!?
알고리즘 규칙 4. 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
@Test
public void 옵션_계산() {
assertThat(4l, is(Option.STAR.calculate(2)));
assertThat(-2l, is(Option.ACHA.calculate(2)));
assertThat(4l, is(new Options(Option.STAR).calculate(2)));
assertThat(-4l, is(new Options(Option.STAR).add(Option.ACHA).calculate(2)));
assertThat(-4l, is(new Options(Option.ACHA).add(Option.STAR).calculate(2)));
}package kakao.dart;
import java.util.Arrays;
import java.util.function.Function;
public enum Option {
STAR("*", value -> value * 2),
ACHA("#", value -> -value);
private String shortName;
private Function<Long, Long> expression;
Option(String shortName, Function<Long, Long> expression) {
this.shortName = shortName;
this.expression = expression;
}
public long calculate(long value) {
return expression.apply(value);
}
public static boolean hasOption(String text) {
return Arrays.asList(Option.values()).stream()
.map(option -> option.shortName)
.anyMatch(shortName -> text.indexOf(shortName) > -1);
}
public static Option getByShortName(String shortName) {
return Arrays.asList(Option.values()).stream()
.filter(option -> option.shortName.equals(shortName))
.findFirst()
.orElseThrow(IllegalArgumentException::new);
}
}Bouns와 같은 방식으로 구현하였습니다.
calculate() : 가 핵심로직으로 되죠.
그런데... 옵션 객체는 좀 특수한 룰을 갖고 있네요.
5. 옵션 일급 콜렉션 생성
알고리즘 규칙 6. 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
2개가 중복해서 존재할 수 있는거죠.
package kakao.dart;
import java.util.ArrayList;
import java.util.List;
public class Options {
private List<Option> options;
public Options(List<Option> options) {
if (options == null) throw new IllegalArgumentException();
this.options = options;
}
public Options(Option option) {
options = new ArrayList<>();
options.add(option);
}
public Options add(Option option) {
options.add(option);
return new Options(options);
}
public Option unique() {
if (options.size() != 1) throw new IllegalStateException();
return options.get(0);
}
public long calculate(long value) {
for (int i = 0; i < options.size(); i++) {
value = options.get(i).calculate(value);
}
return value;
}
}다른 멤버 변수가 없는 일급 콜렉션으로 객체를 생성하였습니다.
일급 콜렉션을 사용함으로, 불필요한 ArrayList의 상속이나, 상태값 변경에 대한 리스크를 줄일기 편합니다.
add() : 해당 로직에서 자기 자신을 반환하는 것에 주의해주세요.
getter, setter 를 사용하지 않고 객체다운 운용이 가능해 집니다.
unique() : 2개가 존재하는 값은 이전 에 기록된 적이 있다는 것을 의미합니다.
의도적으로 잘못된 사용을 막기위한 매쏘드 입니다. [코드가 불안하네요 ㅠㅠ]
이제 어느정도 모양을 잡아가고 있네요!!
6. 다트 포인트 객체 생성 (조합)
알고리즘 규책 9. 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.
이전에 만든 2개의 객체를 1개의 객체로 만듭니다.
@Test
public void 던지기() {
assertThat(2L ,is(new Point("2S").calculate()));
assertThat(-2L ,is(new Point("2S#").calculate()));
assertThat(8L ,is(new Point("2D*").calculate()));
assertThat(4L,is(new Point(new BasicPoint("2S"), new Options(Option.STAR)).calculate()));
assertThat(-2L,is(new Point(new BasicPoint("2S"), new Options(Option.ACHA)).calculate()));
assertThat(-4L,is(new Point(new BasicPoint("2S"), new Options(Option.STAR).add(Option.ACHA)).calculate()));
}package kakao.dart;
import java.util.ArrayList;
public class Point {
private BasicPoint basicPoint;
private Options options;
public Point(String text) {
if (Option.hasOption(text)) {
String option = text.substring(text.length()-1);
options = new Options(Option.getByShortName(option));
text = text.substring(0, text.indexOf(option));
}
basicPoint = new BasicPoint(text);
}
public Point(BasicPoint basicPoint, Options options) {
this.basicPoint = basicPoint;
this.options = options;
}
public Point addOption(Point point) {
if (options == null) {
options = new Options(new ArrayList<>());
}
return new Point(basicPoint, options.add(point.options.unique()));
}
public boolean has(Option option) {
return options != null && option == options.unique();
}
public long calculate() {
if (options == null) return basicPoint.calculate();
return options.calculate(basicPoint.calculate());
}
}addOption() : 스타상(*)을 위해서 존재하는 매쏘드 입니다.
이전의 값에도 옵션을 주기 위한 매쏘드입니다.
has() : getter를 사용해 값을 비교하는 것이 아닌, 객체에게 물어보는 행위를 하게 됩니다.
7. 점수에 옵션 적용하기.
알고리즘 규칙 4. 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
점수를 여러개 가지고 있어야 하기 때문에 컬렉션의 형태가 관리하기 편하며, 갯수도 임의로 변경 가능하다.
@Test
public void 점수() {
assertThat( 37l, is(new Score("1S2D*3T").calculate()));
assertThat( 9l, is(new Score("1D2S#10S").calculate()));
assertThat( 3l, is(new Score("1D2S0T").calculate()));
assertThat( 23l, is(new Score("1S*2T*3S").calculate()));
assertThat( 5l, is(new Score("1D#2S*3S").calculate()));
assertThat( -4l, is(new Score("1T2D3D#").calculate()));
assertThat( 59l, is(new Score("1D2S3T*").calculate()));
}package kakao.dart;
import java.util.ArrayList;
import java.util.List;
public class Score {
List<Point> score;
public Score(String text) {
if (text == null || text.isEmpty()) throw new IllegalArgumentException();
score = new ArrayList<>();
fillScore(text);
}
private void fillScore(String text) {
String[] tokens = text.split("[^\\d]{1,2}");
int index = 1;
while(index < tokens.length) {
String point = text.substring(0, text.indexOf(tokens[index++]));
add(new Point(point));
text = text.substring(point.length());
}
add(new Point(text));
}
private void add(Point point) {
if (point.has(Option.STAR) && score.size() != 0) {
int prevIndex = score.size() - 1;
Point previous = score.get(prevIndex);
score.set(prevIndex, previous.addOption(point));
}
score.add(point);
}
public long calculate() {
return score.stream().mapToLong(Point::calculate).sum();
}
}fillScore() : 드디어 핵심 로직인 토큰이 나오게 되네요. BasicPoint와 같은 match를 사용하죠.
해당 토큰별로 구분하여, 각각의 점수로 스코어를 만들게 됩니다.
fill로 하지 않음으로, 기존의 같은 값을 넣는 매쏘드가 아님을 밝힙니다.
while()문을 매쏘드로 빼려고 했지만, 문맥상 읽기 힘들어져서 그냥 두었습니다.
add() : 첫번째를 제외한 스타상(*)은 바로 전 값에 영향을 주기위해,
score.size가 0인 상태에선 진행할 수 없습니다.
생성자에서 새로운 값을 set하기 때문에, 안전하게 사용할 수 있습니다.
최대한 객체를 객체답게 사용하기위해
규칙 1: 한 메서드에 오직 한 단계의 들여쓰기만 한다.
규칙 2: else 예약어를 쓰지 않는다.
규칙 3: 모든 원시값과 문자열을 포장한다.
규칙 6: 모든 엔티티를 작게 유지한다.
규칙 7: 2개 이상의 인스턴스 변수를 가진 클래스를 쓰지 않는다.
규칙 8: 일급 콜렉션을 쓴다.
규칙 9: 게터/세터/프로퍼티를 쓰지 않는다.