1. 문장의 유사도

세 문자열을 보자

직관적으로 봐도 "나는 너를 좋아해" 와 "너는 나 좋아하니?"와 유사하고 "오늘 집에 갈거야" 와는 유사하지 않다는 걸 알 수 있다.

우리는 인간이니까 직관적으로 두 문자열이 비슷한지 전혀 다른지 판단할 수 있지만 기계는 직관적으로 판단 할 수 없다. 

두 문자열의 유사도를 어떻게 판단할 수 있을까? Hamming Distance, Smith-Waterman, Sørensen–Dice coefficient 등 있지만 지금은 가장 간단한 Levenshtein Distance을 알아볼 것이다.(사실 문제 풀다가 나와서 정리하는 것)

2. 레벤슈타인 거리(Levenshtein Distance)

레벤슈타인 거리 알고리즘은 두 문자열이 같아지려면 몇번의 문자 조작(삽입, 삭제, 변경)이 필요한지 구하는 것이다.

점화식만 보면 어려우니까 예시로 표현해보자.

두 문자열을 비교하면 문자 조작 비용은 총 6이다.

3. 알고리즘

위에서 말한 것 처럼 직관적으로 비용이 6인것을 알 수 있는데, 이를 알고리즘으로 어떻게 구현하는지 알아보자. LCS와 매우 유사하다.

처음 비교 대상은 공집합과 공집합이다. 둘 다 같은 문자열이기 때문에 비용은 0이다. 그 다음은 공집합과 "나" 이다. 공집합이 "나"가 되려면 비용이 1이다. 그 다음은 공집합과 "나는"이다. 마찬가지로 비용이 2가든다. 계속 진행하면 위와 같이 표가 완성된다.

이제 "너" 와 공집합 - "나" - "나는" - "나는 "... - "나는 너를 좋아해!"를 비교해보자.

"너"와 공집합을 보자.  '너'가 {}이 되려면 문자를 삭제해야 한다. 그러므로 비용 1

"너"와 "나"를 보자. '너'와 '나'는 서로 다르기 때문에 교체해야 한다. 그러므로 비용 1

"너"와 "나는"을 보자. 길이가 다르기 때문에 추가해야 하고, 교체해야 한다. 그러므로 비용 2

"너"와 "나는 "을 보자. 역시 길이가 다르기 때문에 2개 추가해야 하고, 교체해야 한다. 그러므로 비용 3

"너"와 "나는 너"를 보자. 길이가 다르기 때문에 문자 3개를 추가해야 하지만, '너'는 서로 같기 때문에 그대로 둔다. 그러므로 비용 3

이런식으로 "나는 너를 좋아해!"까지 표를 완성하면 위와 같이 된다.

한번만 더 해보자. "너는"과 공집합 - "나" - "나는" - "나는 " - ... - "나는 너를 좋아해!"를 비교해보자

"너는"과 공집합을 비교해보자. "너는"이 {}이 되려면 문자 두개를 삭제해야 한다. 그러므로 비용 2

"너는"과 "나"를 비교해보자. 문자 한개 삭제와 교체가 필요하다. 그러므로 비용 2

"너는"과 "나는"을 비교해보자. '는'은 서로 같고, '너'와 '나'는 다르기 때문에 교체가 필요하다. 그러므로 비용 1

"너는"과 "나는 "을 비교해보자. 추가, 교체가 필요하다. 그러므로 비용 2

이런식으로 표를 완성하면 다음과 같이 된다.

쉽게 정리하면

1. 글자가 서로 동일하면 대각선 값을 가져온다
2. 변경이 필요하면 대각선 값에서 + 1을 한다.
3. 삽입이 필요하면 위의 값에서 +1을 한다.
4. 삭제가 필요하면 왼쪽 값에서 +1을 한다.
5. 1~4의 경우에서 최소값을 가져온다.

4. 코드

public class Levenshtein {

  public static int getDistance(String a, String b) {
    int[][] table = new int[a.length() + 1][b.length() + 1];

    for (int i = 1; i <= a.length(); i++) {
      table[i][0] = i;
    }
    for (int j = 1; j <= b.length(); j++) {
      table[0][j] = j;
    }

    for (int i = 1; i <= a.length(); i++) {
      for (int j = 1; j <= b.length(); j++) {
        int insert = table[i - 1][j] + 1;
        int delete = table[i][j - 1] + 1;
        int replace = (a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1) + table[i - 1][j - 1];
      }
    }

    return table[a.length()][b.length()];
  }
}

5. 예제

www.codewars.com/kata/5259510fc76e59579e0009d4/train/java

1. 문제

programmers.co.kr/learn/courses/30/lessons/17684

문제 설명

신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다.

어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.

LZW 압축은 다음 과정을 거친다.

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열w를 찾는다.
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서w를 제거한다.
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c),w+c에 해당하는 단어를 사전에 등록한다.
5. 단계 2로 돌아간다.

압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다. 사전의 색인 번호는 정수값으로 주어지며, 1부터 시작한다고 하자.

예를 들어 입력으로KAKAO가 들어온다고 하자.

1. 현재 사전에는KAKAO의 첫 글자K는 등록되어 있으나, 두 번째 글자까지인KA는 없으므로, 첫 글자K에 해당하는 색인 번호 11을 출력하고, 다음 글자인A를 포함한KA를 사전에 27 번째로 등록한다.
2. 두 번째 글자A는 사전에 있으나, 세 번째 글자까지인AK는 사전에 없으므로,A의 색인 번호 1을 출력하고,AK를 사전에 28 번째로 등록한다.
3. 세 번째 글자에서 시작하는KA가 사전에 있으므로,KA에 해당하는 색인 번호 27을 출력하고, 다음 글자O를 포함한KAO를 29 번째로 등록한다.
4. 마지막으로 처리되지 않은 글자O에 해당하는 색인 번호 15를 출력한다.

이 과정을 거쳐 다섯 글자의 문장KAKAO가 4개의 색인 번호 [11, 1, 27, 15]로 압축된다.

입력으로TOBEORNOTTOBEORTOBEORNOT가 들어오면 다음과 같이 압축이 진행된다.

제한 사항

입력 형식

입력으로 영문 대문자로만 이뤄진 문자열msg가 주어진다.msg의 길이는 1 글자 이상, 1000 글자 이하이다.

출력 형식

주어진 문자열을 압축한 후의 사전 색인 번호를 배열로 출력하라.

입출력 예

2. 어떻게 풀까?

1. Map을 생성해서 A~Z까지 index 1~26을 붙여 저장한다.
2. 문자열을 for문으로 돌며 Map에 존재하는지 체크하고 있다면 문자열 길이를 늘이고, 없다면 이전 문자열에 해당하는 index값을 출력하고, 늘린 문자열은 Map에 추가한다.

3. 코드

테스트 코드

package programmers.level2.압축_20210111;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

  @Test
  public void test1() {
    assertThat(new Solution().solution("KAKAO"), is(new int[]{11, 1, 27, 15}));
  }

  @Test
  public void test2() {
    assertThat(new Solution().solution("TOBEORNOTTOBEORTOBEORNOT"),
        is(new int[]{20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34}));
  }

  @Test
  public void test3() {
    assertThat(new Solution().solution("ABABABABABABABAB"),
        is(new int[]{1, 2, 27, 29, 28, 31, 30}));
  }
}

실제 코드

package programmers.level2.압축_20210111;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {

  public int[] solution(String msg) {
    Map<String, Integer> dictionary = buildBasicDictionary();
    List<Integer> indexList = new ArrayList<>();
    int letterIndex = 27;
    int startIndex = 0;

    while (startIndex < msg.length()) {
      int endIndex = getEndIndex(msg, dictionary, startIndex);
      String target = msg.substring(startIndex, endIndex);

      indexList.add(dictionary.get(target));
      if (endIndex < msg.length()) {
        dictionary.put(msg.substring(startIndex, endIndex + 1), letterIndex++);
      }

      startIndex = endIndex;
    }

    return indexList.stream().mapToInt(x -> x).toArray();
  }

  private int getEndIndex(String msg, Map<String, Integer> dictionary, int startIndex) {
    int index;
    for (index = startIndex + 1; index <= msg.length(); index++) {
      if (!dictionary.containsKey(msg.substring(startIndex, index))) {
        break;
      }
    }
    return index - 1;
  }

  private Map<String, Integer> buildBasicDictionary() {
    Map<String, Integer> map = new HashMap<>();
    int index = 1;
    for (char letter = 'A'; letter <= 'Z'; letter++, index++) {
      map.put(letter + "", index);
    }
    return map;
  }
}

• buildBasicDictionary()에서 A~Z까지 Map에 추가한다.
• while문에서 Map에 존재하는 문자열의 value를 List에 저장하고, 존재하지 않는 문자열은 Map에 저장한다.
• getEndIndex()에서 endIndex를 구한다.

4. 느낀 점

• 처음에 getEndIndex()에서 index를 반환했다. 근데 그러면 입력 문자열의 startIndex ~ endIndex - 1까지의 subString은 Map에 존재하고, startIndex ~ endIndex까지의 subString은 존재하지 않는다. 이름이 너무 애매하고 오히려 더 헷갈려서 getEndIndex()에서 index - 1을 반환하는것으로 해결했다.
• 문제 자체는 카카오 문제치고는 어렵지 않은 편이다. level 2까지는 확실히 다 맞혀야 할듯

1. 문제

programmers.co.kr/learn/courses/30/lessons/17679

문제 설명

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은프렌즈4블록.
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

제한 사항

입력 형식

• 입력으로 판의 높이m, 폭n과 판의 배치 정보board가 들어온다.
• 2 ≦n,m≦ 30
• board는 길이n인 문자열m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

출력 형식

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

입출력 예

2. 어떻게 풀까?

1. 입력으로 주어진 String 배열 board를 이차원 배열로 만든다.
2. 이차원 배열의 현재 index의 block을 기준으로 block을 지울 수 있는지 확인한다.
3. 지운 이후 위쪽의 block들을 아래로 내린다.
4. 지울 수 있는 block이 없을 때까지 반복한다.
5. 해결 과정은 명확하게 이해할 수 있는데, 이것을 코드로 작성하는데 계속 막히고, 틀렸다. 특히, 지울 수 있는지 확인하는 과정에서 boolean 타입을 선언해서 확인하려했는데, 잘 안됐다. 그래서 답을 참고했다.

velog.io/@hyeon930/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%94%84%EB%A0%8C%EC%A6%884%EB%B8%94%EB%A1%9D-Java

3. 코드

테스트 코드

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

  @Test
  public void test1() {
    String[] board = {"CCBDE", "AAADE", "AAABF", "CCBBF"};
    assertThat(new Solution().solution(4, 5, board), is(14));
  }

  @Test
  public void test2() {
    String[] board = {"TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"};
    assertThat(new Solution().solution(6, 6, board), is(15));
  }

}

실제 코드

public class Solution {

  public int solution(int m, int n, String[] board) {
    String[][] table = buildTable(m, n, board);
    int count = 0;

    while (true) {
      int dropBlockCount = countFourBlock(m, n, table);
      if (dropBlockCount == 0) {
        break;
      }
      count += dropBlockCount;
      dropTable(m, n, table);
    }

    return count;
  }

  private String[][] buildTable(int m, int n, String[] board) {
    String[][] table = new String[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        table[i][j] = board[i].charAt(j) + "";
      }
    }
    return table;
  }

  private int countFourBlock(int m, int n, String[][] table) {

    boolean[][] check = new boolean[m][n];

    for (int row = 0; row < m - 1; row++) {
      for (int col = 0; col < n - 1; col++) {
        if (table[row][col].equals(".")) {
          continue;
        }
        checkFourBlock(table, check, row, col);
      }
    }

    int count = 0;
    for (int row = 0; row < m; row++) {
      for (int col = 0; col < n; col++) {
        if (check[row][col]) {
          count++;
          table[row][col] = ".";
        }
      }
    }

    return count;
  }

  private void checkFourBlock(String[][] table, boolean[][] check, int currentRow,
      int currentCol) {
    String currentBlock = table[currentRow][currentCol];

    for (int row = currentRow; row < currentRow + 2; row++) {
      for (int col = currentCol; col < currentCol + 2; col++) {
        if (!table[row][col].equals(currentBlock)) {
          return;
        }
      }
    }

    for (int row = currentRow; row < currentRow + 2; row++) {
      for (int col = currentCol; col < currentCol + 2; col++) {
        check[row][col] = true;
      }
    }
  }

  private void dropTable(int m, int n, String[][] table) {
    for (int col = 0; col < n; col++) {
      for (int row = m - 1; row >= 0; row--) {
        if (table[row][col].equals(".")) {
          for (int notDotRow = row - 1; notDotRow >= 0; notDotRow--) {
            if (!table[notDotRow][col].equals(".")) {
              table[row][col] = table[notDotRow][col];
              table[notDotRow][col] = ".";
              break;
            }
          }
        }
      }
    }
  }

}

• buildTable()에서 일차원 배열의 board를 이차원 배열로 만들었다.
• 반복문을 돌며 countFourBlock()을 통해 지울 수 있는 block의 수를 계산 후, 전체 count에 더해주고 dropTable()을 통해 지웠다.
• countFourBlock()에서 지울 수 있는 block인지 확인하는 boolean 이차원 배열을 선언 후, checkFourBlock()을 통해그림의 왼쪽 위부터 차례대로 확인했다. 마지막 행과 열은 확인 할 수 없기 때문에 반복문을 m-1, n-1까지만 돌며 확인했다. 지울 수 있는 block은 .으로 바꿔주었다.
• dropTable()에서 element가 .인 칸을 찾은 후에 그 위로 .가 아닌 칸을 찾아서 두 element를 바꿔주었다.

4. 느낀 점

이차원 배열을 왼쪽 위부터 오른쪽 아래까지 차례대로 확인 👉 지울 수 있는 블록이라면 따로 마킹 👉 이차원 배열에서 마킹해놓은 개수를 덧셈 👉 블록들 삭제 👉 지울 수 있는 블록이 없을 때까지 반복

이라는 흐름은 머리로 간단히 그려졌는데, 막상 코드로 구현하려고 할 때 어려움을 느꼈다.

마킹을 어떻게 해야할까? Key, Value로 구현해야하나? 그럼 Entry를 써야하나? 이런 고민들도 있었고,

지울 수 있는 블록들은 어떻게 삭제를 해야할까? 배열에서는 delete하기 어려우니 List를 써야하나? 하는 고민도 있었다.

다른 분이 푼 코드를 보니, 그냥 따로 boolean 타입의 이차원 배열을 선언하여 해결했고

배열은 delete 대신 .으로 바꿔주었다.

어렵다 ㅜㅜ

1. 문제

www.codewars.com/kata/55b3425df71c1201a800009c

문제 설명

You are the "computer expert" of a local Athletic Association (C.A.A.). Many teams of runners come to compete. Each time you get a string of all race results of every team who has run. For example here is a string showing the individual results of a team of 5 runners:

"01|15|59, 1|47|6, 01|17|20, 1|32|34, 2|3|17"

Each part of the string is of the form:h|m|swhere h, m, s (h for hour, m for minutes, s for seconds) are positive or null integer (represented as strings) with one or two digits. There are no traps in this format.

To compare the results of the teams you are asked for giving three statistics;range, average and median.

Range: difference between the lowest and highest values. In {4, 6, 9, 3, 7} the lowest value is 3, and the highest is 9, so the range is 9 − 3 = 6.

Mean or Average: To calculate mean, add together all of the numbers in a set and then divide the sum by the total count of numbers.

Median: In statistics, the median is the number separating the higher half of a data sample from the lower half. The median of a finite list of numbers can be found by arranging all the observations from lowest value to highest value and picking the middle one (e.g., the median of {3, 3, 5, 9, 11} is 5) when there is an odd number of observations. If there is an even number of observations, then there is no single middle value; the median is then defined to be the mean of the two middle values (the median of {3, 5, 6, 9} is (5 + 6) / 2 = 5.5).

the form:

"Range: hh|mm|ss Average: hh|mm|ss Median: hh|mm|ss"

where hh, mm, ss are integers (represented by strings) witheach 2 digits.

제한 사항

Remarks:

1. if a result in seconds is ab.xy... it will be giventruncatedas ab.

2. if the given string is "" you will return ""

입출력 예

input - "01|15|59, 1|47|6, 01|17|20, 1|32|34, 2|3|17"

result - "Range: hh|mm|ss Average: hh|mm|ss Median: hh|mm|ss"

2. 어떻게 풀까?

1. input으로 들어온 time 문자열을 쪼갠다.
2. 각 time 문자열을 시간, 분, 초를 계산해서, 혹은 LocalTime을 이용해서 List에 저장 후 정렬한다.
   • 전에 Time 패키지 공부 한 것을 써먹기 위해 LocalTime을 사용해서 해결
3. List를 통해 Range, Average, Median을 구하고 String으로 표현한다.

3. 코드

테스트 코드

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import org.junit.Test;

public class StatTest {

  @Test
  public void testWhenInputIsEmptyString() {
    String expected = "";
    String input = "";
    assertThat(Stat.stat(input), is(expected));
  }

  @Test
  public void testWhenInputSizeIs1() {
    String expected = "Range: 00|00|00 Average: 00|15|00 Median: 00|15|00";
    String input = "0|15|0";
    assertThat(Stat.stat(input), is(expected));
  }

  @Test
  public void testWhenInputSizeIsOdd() {
    String expected = "Range: 01|01|18 Average: 01|38|05 Median: 01|32|34";
    String input = "01|15|59, 1|47|16, 01|17|20, 1|32|34, 2|17|17";
    assertThat(Stat.stat(input), is(expected));
  }

  @Test
  public void testWhenInputSizeIsEven() {
    String expected = "Range: 00|31|17 Average: 02|25|24 Median: 02|19|40";
    String input = "02|15|59, 2|47|16, 02|17|20, 2|32|34, 2|17|17, 2|22|00";
    assertThat(Stat.stat(input), is(expected));
  }

}

실제 코드

import java.time.LocalTime;
import java.time.format.DateTimeFormatter;
import java.time.temporal.ChronoUnit;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Stat {

  public static String stat(String strg) {
    if (strg.isEmpty()) {
      return "";
    }
    List<LocalTime> list = getSortedTimeList(strg);

    LocalTime range = getRange(list);
    LocalTime average = getAverage(list);
    LocalTime median = getMedian(list);

    return getResultString(range, average, median);
  }

  private static List<LocalTime> getSortedTimeList(String strg) {
    List<LocalTime> list = new ArrayList<>();
    String[] split = strg.split(", ");
    for (int i = 0; i < split.length; i++) {
      LocalTime temp = LocalTime.parse(split[i], DateTimeFormatter.ofPattern("H|mm|s"));
      list.add(temp);
    }
    list.sort(Comparator.naturalOrder());
    return list;
  }

  private static LocalTime getRange(List<LocalTime> list) {
    LocalTime min = list.get(0);
    LocalTime max = list.get(list.size() - 1);
    long seconds = min.until(max, ChronoUnit.SECONDS);

    return LocalTime.ofSecondOfDay(seconds);
  }

  private static LocalTime getAverage(List<LocalTime> list) {
    long seconds = 0;
    for (int i = 0; i < list.size(); i++) {
      seconds += list.get(i).toSecondOfDay();
    }
    return LocalTime.ofSecondOfDay(seconds / list.size());
  }

  private static LocalTime getMedian(List<LocalTime> list) {
    long seconds = 0;
    if (list.size() % 2 == 1) {
      seconds = list.get(list.size() / 2).toSecondOfDay();
    } else {
      seconds += list.get(list.size() / 2).toSecondOfDay();
      seconds += list.get(list.size() / 2 - 1).toSecondOfDay();
      seconds /= 2;
    }
    return LocalTime.ofSecondOfDay(seconds);
  }

  private static String getResultString(LocalTime range, LocalTime average, LocalTime median) {
    return String.format("Range: %s Average: %s Median: %s",
        range.format(DateTimeFormatter.ofPattern("HH|mm|ss")),
        average.format(DateTimeFormatter.ofPattern("HH|mm|ss")),
        median.format(DateTimeFormatter.ofPattern("HH|mm|ss")));
  }
}

• getSortedTimeList() 에서 input 문자열을 ", "로 쪼갠 뒤 List에 저장 후 정렬했다.
• getRange(), getAverage(), getMedian()에서 List에 저장한 LocalTime들을 계산했다.

4. 느낀 점

• 문제를 처음 보고 '|'의 index를 통해 시, 분, 초를 구하고 그것들을 초로 바꾸어 List에 저장해서 정렬 후, range/average/medain을 계산하려 했는데, 전에 공부했던 Time 패키지의 LocalTime을 이용하면 쉽게 해결 할 수 있겠다고 생각해서 사용해 보았다.
• List<LocalTime>을 정렬하면 정렬이 안될줄 알았는데 아주 잘 되서 신기했다.
• LocalTime을 이용할 때, 전에 포스팅한 Time 패키지를 참고했다. 정리 해놓길 잘했다는 생각이 든다.
  • Time 패키지

1. 문제

programmers.co.kr/learn/courses/30/lessons/17677

문제 설명

여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 사용자들이 편리하게 다양한 뉴스를 찾아볼 수 있도록 문제점을 개선하는 업무를 맡게 되었다.

개발의 방향을 잡기 위해 튜브는 우선 최근 화제가 되고 있는 카카오 신입 개발자 공채 관련 기사를 검색해보았다.

• 카카오 첫 공채..'블라인드' 방식 채용
• 카카오, 합병 후 첫 공채.. 블라인드 전형으로 개발자 채용
• 카카오, 블라인드 전형으로 신입 개발자 공채
• 카카오 공채, 신입 개발자 코딩 능력만 본다
• 카카오, 신입 공채.. 코딩 실력만 본다
• 카카오 코딩 능력만으로 2018 신입 개발자 뽑는다

기사의 제목을 기준으로 블라인드 전형에 주목하는 기사와 코딩 테스트에 주목하는 기사로 나뉘는 걸 발견했다. 튜브는 이들을 각각 묶어서 보여주면 카카오 공채 관련 기사를 찾아보는 사용자에게 유용할 듯싶었다.

유사한 기사를 묶는 기준을 정하기 위해서 논문과 자료를 조사하던 튜브는 자카드 유사도라는 방법을 찾아냈다.

자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.

예를 들어 집합 A = {1, 2, 3}, 집합 B = {2, 3, 4}라고 할 때, 교집합 A ∩ B = {2, 3}, 합집합 A ∪ B = {1, 2, 3, 4}이 되므로, 집합 A, B 사이의 자카드 유사도 J(A, B) = 2/4 = 0.5가 된다. 집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.

자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 A는 원소 1을 3개 가지고 있고, 다중집합 B는 원소 1을 5개 가지고 있다고 하자. 이 다중집합의 교집합 A ∩ B는 원소 1을 min(3, 5)인 3개, 합집합 A ∪ B는 원소 1을 max(3, 5)인 5개 가지게 된다. 다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로, 자카드 유사도 J(A, B) = 3/7, 약 0.42가 된다.

이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다. 문자열 FRANCE와 FRENCH가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다.

제한 사항

입력 형식

• 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
• 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 ab+가 입력으로 들어오면, ab만 다중집합의 원소로 삼고, b+는 버린다.
• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. AB와 Ab, ab는 같은 원소로 취급한다.

출력 형식

입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

입출력 예

2. 어떻게 풀까?

1. 두 문자열을 소문자 or 대문자로 바꿔주고, 2개의 문자열로 분할해서 배열 같은 곳에 따로 저장한다.
2. 두 배열을 비교해서 같은 문자열이 있으면 교집합과 합집합 count를 추가해주고, 같은 문자열이 없으면 합집합 count만 추가해준다.
3. 근데 한 배열에 중복된 문자열이 있을 수도 있으니까 배열보다 Map을 이용하는게 더 나아 보인다.
4. 두 Map을 비교해서 같은 문자열이 있다.
   1. 교집합 - 문자열 중복 개수 중 작은 값
   2. 합집합 - 문자열 중복 개수 중 큰 값

3. 코드

테스트 코드

package programmers.level2.뉴스클러스터링_20201210;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

  @Test
  public void test1() {
    assertThat(new Solution().solution("FRANCE", "french"), is(16384));
  }

  @Test
  public void test2() {
    assertThat(new Solution().solution("handshake", "shake hands"), is(65536));
  }

  @Test
  public void test3() {
    assertThat(new Solution().solution("aa1+aa2", "AAAA12"), is(43690));
  }

  @Test
  public void test4() {
    assertThat(new Solution().solution("E=M*C^2", "e=m*c^2"), is(65536));
  }
}

실제 코드

package programmers.level2.뉴스클러스터링_20201210;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class Solution {

  int union = 0;
  int intersection = 0;

  public int solution(String str1, String str2) {
    Map<String, Integer> map1 = getStringSet(str1);
    Map<String, Integer> map2 = getStringSet(str2);

    return getSimilarity(map1, map2);
  }

  private int getSimilarity(Map<String, Integer> map1, Map<String, Integer> map2) {
    for (Entry<String, Integer> entry : map1.entrySet()) {
      String key = entry.getKey();
      int value = entry.getValue();
      if (map2.containsKey(key)) {
        intersection += Math.min(value, map2.get(key));
        union += Math.max(value, map2.get(key));
        map2.remove(key);
      } else {
        union += value;
      }
    }
    for (Entry<String, Integer> entry : map2.entrySet()) {
      union += entry.getValue();
    }

    return union == 0 ? 65536 : (int) Math.floor(65536 * ((double) intersection / union));
  }

  private Map<String, Integer> getStringSet(String string) {
    string = string.toLowerCase();
    Map<String, Integer> map = new HashMap<>();

    for (int i = 0; i < string.length() - 1; i++) {
      String sub = string.substring(i, i + 2);
      if (sub.matches("[a-z][a-z]")) {
        map.put(sub, map.getOrDefault(sub, 0) + 1);
      }
    }
    return map;
  }
}

• getStringSet() 메서드를 이용해서 문자열을 분할하여 저장한다. 이때, 문자열에 알파벳을 제외한 문자가 있으면 저장하지 않는다.
• getSimiliarty() 메서드에서 문자열 count를 저장한 두 Map을 비교하여 교집합 count와 합집합 count를 추가한다.
  • union이 0이면 0으로 나눌 수 없기 때문에 1로 가정한다.

4. 느낀 점

어렵지 않은 문제, 쉽게 풀었다.

1. 문제

programmers.co.kr/learn/courses/30/lessons/67256

문제 설명

이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.

1. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
2. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
3. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
4. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
   4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

제한 사항

• numbers 배열의 크기는 1 이상 1,000 이하입니다.
• numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.
• hand는 left 또는 right 입니다.
  • left는 왼손잡이, right는 오른손잡이를 의미합니다.
• 왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.

입출력 예

2. 어떻게 풀까?

• 키패드와 현재 왼손, 오른손을 좌표로 생각하여 풀면 될 것 같다.
• 1,4,7은 항상 왼손이고 3,6,9는 항상 오른손이다.
• 2,5,8,0의 경우 해당 number의 좌표와 현재 왼손과 오른손 좌표의 거리를 계산하여 더 가까운 손으로 누르면 되겠다.
  • 거리가 같은 경우는 입력으로 주어진 hand를 이용한다.

3. 코드

for문과 if / else if문으로 계속 쓰다보니 바로 됐다. 그 후에 리팩토링을 어떻게 깔끔하게 할 수 있을까 많이 고민했다.

테스트코드

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

  @Test
  public void test1() {
    int[] numbers = {1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5};
    assertThat(new Solution().solution(numbers,"right"), is("LRLLLRLLRRL"));
  }

  @Test
  public void test2() {
    int[] numbers = {7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2};
    assertThat(new Solution().solution(numbers,"left"), is("LRLLRRLLLRR"));
  }

  @Test
  public void test3() {
    int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
    assertThat(new Solution().solution(numbers,"right"), is("LLRLLRLLRL"));
  }
}

실제코드

public class Solution2 {

  int[] leftPoint;
  int[] rightPoint;

  public String solution(int[] numbers, String hand) {
    StringBuilder result = new StringBuilder();
    leftPoint = new int[]{3, 0};
    rightPoint = new int[]{3, 2};
    hand = hand.equals("right") ? "R" : "L";

    for (int number : numbers) {
      touch(result, number, hand);
    }
    return result.toString();
  }

  private void touch(StringBuilder result, int number, String hand) {

    if (number == 1 || number == 4 || number == 7) {
      result.append("L");
      leftPoint = getPoint(number);
    } else if (number == 3 || number == 6 || number == 9) {
      result.append("R");
      rightPoint = getPoint(number);
    } else if (number == 2 || number == 5 || number == 8 || number == 0) {
      String finger = getCloseFinger(number, leftPoint, rightPoint, hand);
      result.append(finger);
      if (finger.equals("R")) {
        rightPoint = getPoint(number);
      } else {
        leftPoint = getPoint(number);
      }
    }
  }

  private String getCloseFinger(int number, int[] leftPoint, int[] rightPoint, String hand) {
    int[] padPoint = getPoint(number);

    int toLeftFingerDistance =
        Math.abs(leftPoint[0] - padPoint[0]) + Math.abs(leftPoint[1] - padPoint[1]);
    int toRightFingerDistance =
        Math.abs(rightPoint[0] - padPoint[0]) + Math.abs(rightPoint[1] - padPoint[1]);

    return toLeftFingerDistance == toRightFingerDistance ? hand
        : toLeftFingerDistance < toRightFingerDistance ? "R" : "L";
  }

  private int[] getPoint(int number) {
    if (number == 1) {
      return new int[]{0, 0};
    } else if (number == 2) {
      return new int[]{0, 1};
    } else if (number == 3) {
      return new int[]{0, 2};
    } else if (number == 4) {
      return new int[]{1, 0};
    } else if (number == 5) {
      return new int[]{1, 1};
    } else if (number == 6) {
      return new int[]{1, 2};
    } else if (number == 7) {
      return new int[]{2, 0};
    } else if (number == 8) {
      return new int[]{2, 1};
    } else if (number == 9) {
      return new int[]{2, 2};
    }
    return new int[]{3, 1};
  }
}

반복문을 돌면서 touch() 메서드로 result를 계속 붙여나갔다.

touch() 메서드에서는

• number가 1, 4, 7일 경우 result에 "L"을 붙이고 현재 왼손 좌표인 leftPoint를 number에 해당하는 좌표로 수정.
• 마찬가지로 3, 6, 9일 경우 result에 "R"을 붙이고 rightPoint를 number에 해당하는 좌표로 수정한다.
• number가 2, 5, 8, 0일 경우 getCloseFinger() 메서드를 통해 "L" 또는 "R"을 result에 붙여주고 리턴 값에 따라 leftPoint or rightPoint를 number에 해당하는 좌표로 수정한다.
• 좌표를 수정은 getPoint()메서드에서 한다.

getCloseFinger() 메서드에서는 number에 해당하는 좌표와 현재 왼손위치(leftPoint), 오른손위치(rightPoint)중 더 가까운 손을 반환 한다.("R" 또는 "L") 만약 거리가 같다면 입력으로 받은 hand에 따라 결정한다.

4. 느낀점

• 문제 자체는 쉬웠다. 그냥 반복문과 조건문으로 간단하게 풀 수 있었다.
• 그런데, 조건문을 사용하면서 중복되는 코드가 매우 많아져서 코드를 읽기도 어렵고 상당히 복잡했다.
• 그래서 문제를 푸는것 보다 리팩토링하는데 더 고민을 한 문제였다.
• 이 문제 2020 카카오 인턴십때 나온 문제인데 그 당시에는 못풀었다. 이유가 문제만 보고 아 어렵겠다 하고 넘겨서 못풀었는데, 지금 보니까 너무 쉬운문제이다. ㅜㅜ 아쉽

1. 개요

Map 자료구조를 사용하는 경우가 많은데, 항상 정렬하는 부분에서 까먹고 구글링을 하게 된다. 답답해서 내 블로그에 정리한다.

또 저번에 문제 풀다가 key 하나에 value여러개를 저장해야하는 경우가 있었는데, Value를 List로 두어 구현하니 1 key, multi value가 가능했다. 이것도 까먹을 수 있으니 정리해두자.

2. Map 정렬

Map 자료구조를 정렬할 때 크게 두 가지 경우를 생각해 볼 수 있다.

• Key를 기준으로 정렬
• Value 기준으로 정렬

2-1. Key를 기준으로 정렬

Key를 기준으로 정렬할 때 TreeMap을 사용하면 된다. TreeMap은 저장할 때 Key 순서로 저장하도록 구현되어있다. 오름차순 정렬, 내림차순 정렬, 또는 다른 기준으로 정렬할 수 있는데 이 때 Comparator를 사용한다.

예시를 보자

package algorithm.map;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;
import org.junit.jupiter.api.Test;

public class MapSortTest {

  Map<Integer, String> numberCountryMap;

  MapSortTest() {
    numberCountryMap = new HashMap<>();
    numberCountryMap.put(82, "대한민국");
    numberCountryMap.put(1, "미국");
    numberCountryMap.put(33, "프랑스");
    numberCountryMap.put(7, "러시아");
    numberCountryMap.put(61, "호주");
    numberCountryMap.put(84, "베트남");
    numberCountryMap.put(81, "일본");
    numberCountryMap.put(886, "대만");
    numberCountryMap.put(44, "영국");
  }

  @Test
  public void mapEntireSortByAscendingKeyTest() {
    Map<Integer, String> keyAscendingMap = new TreeMap<>(Comparator.naturalOrder());
    //Map<Integer, String> keyAscendingMap = new TreeMap<>((o1, o2) -> o1.compareTo(o2));도 가능
    keyAscendingMap.putAll(numberCountryMap);
    System.out.println("---key ascending map ---");
    printMap(keyAscendingMap);
  }

}

생성자에서 구현한 numberCountryMap을 출력하면 저장한 순서대로 출력된다. 그러나 TreeMap으로 구현한 keyAscendingMap은 key 오름차순 순서로 출력된다. 생성자에 원하는 정렬 기준 Comparator를 입력으로 하면 된다.

이번엔 내림차순으로 정렬한 것을 보자

package algorithm.map;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;
import org.junit.jupiter.api.Test;

public class MapSortTest {

  //numberCountryMap은 오름차순 때와 같음

  @Test
  public void mapEntireSortByDescendingKeyTest() {
    Map<Integer, String> keyDescendingMap = new TreeMap<>(Comparator.reverseOrder());
    // Map<Integer, String> keyDescendingMap = new TreeMap<>((o1, o2) -> o2.compareTo(o1));도 가능
    keyDescendingMap.putAll(numberCountryMap);
    System.out.println("---key descending map---");
    printMap(keyDescendingMap);
  }
}

정렬 기준을 익명클래스로 Comparator를 생성하거나, 람다식을 이용해서 구현할 수도 있다.

2-2. Value를 기준으로 정렬

Key를 기준으로 한 Map의 정렬은 TreeMap을 이용해서 쉽게 구현할 수 있다. 그렇다면 Value를 기준으로 한 정렬은 어떻게 구현할까?

Map.Entry를 List로 저장하여 value를 기준으로 정렬 한 후 LinkedHashMap에 저장한다.

예시로 쉽게 알아보자.

package algorithm.map;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;
import org.junit.jupiter.api.Test;

public class MapSortTest {

  // numberCountryMap은 위 예시들과 같음

  @Test
  public void mapEntireSortByAscendingValueTest() {
    List<Entry<Integer, String>> entryList = new ArrayList<>(numberCountryMap.entrySet());
    entryList.sort((o1, o2) -> o1.getValue().compareTo(o2.getValue()));
    // entryList.sort(Comparator.comparing(Entry::getValue));도 가능
    // entryList.sort(Entry.comparingByValue());도 가능

    Map<Integer, String> valueAscendingMap = new LinkedHashMap<>();
    for (Entry<Integer, String> entry : entryList) {
      valueAscendingMap.put(entry.getKey(), entry.getValue());
    }

    System.out.println("--- value ascending map ---");
    printMap(valueAscendingMap);
  }

  @Test
  public void mapEntireSortByDescendingValueTest() {
    List<Entry<Integer, String>> entryList = new ArrayList<>(numberCountryMap.entrySet());
    entryList.sort((o1, o2) -> o2.getValue().compareTo(o1.getValue()));

    Map<Integer, String> valueDescendingMap = new LinkedHashMap<>();
    for (Entry<Integer, String> entry : entryList) {
      valueDescendingMap.put(entry.getKey(), entry.getValue());
    }
    System.out.println("--- value descending map ---");
    printMap(valueDescendingMap);
  }

}

예시에서는 List를 정렬 후 LinkedHashMap에 저장했지만, 정렬 된Map을 구현하는 것이 아닌, 단순 출력 목적이라면 List까지만 구현해도 된다.

2-3. 번외 - Key만 필요하거나, Value만 필요할 경우

그냥 Entry로 List를 구현하여 정렬하는것이 더 낫다고 생각하지만, 참고용으로 keySet()과 values()로 구현한것도 정리해둔다.

package algorithm.map;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;
import org.junit.jupiter.api.Test;

public class MapSortTest {

  // numberCountryMap은 위 예시들과 같음

  @Test
  public void keyListTest() {
    List<Integer> keys = new ArrayList<>(numberCountryMap.keySet());
    for (Integer key : keys) {
      System.out.println("Key : " + key);
    }
    System.out.println();
  }

  @Test
  public void valueListTest() {
    List<String> values = new ArrayList<>(numberCountryMap.values());
    for (String value : values) {
      System.out.println("Value : " + value);
    }
    System.out.println();
  }

}

3. one Key Multi Value

Spring에 MultiValueMap이 있기는 하지만 사용하기 위해선 라이브러리를 추가해주어야 한다.

https://docs.spring.io/spring-framework/docs/current/javadoc-api/org/springframework/util/MultiValueMap.html

Spring 라이브러리 추가 없이 사용하기 위해 Map<Key, Value>에서 Value를 List로 사용한다.

package algorithm.map;

import static org.junit.Assert.fail;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;
import org.junit.jupiter.api.Test;

public class MultiValueMapTest {

  Map<Character, List<String>> dictionaryMap = new TreeMap<>();

  @Test
  public void multiValueMapTest() {
    addWord("apple");
    addWord("dig");
    addWord("drug");
    addWord("banana");
    addWord("abc-Mart");
    addWord("africa");
    addWord("ace");
    addWord("big");
    addWord("boy");
    addWord("drum");
    addWord("cap");

    printSortedDictionaryMap(dictionaryMap);
  }

  private void printSortedDictionaryMap(Map<Character, List<String>> dictionaryMap) {
    for (Entry<Character, List<String>> entry : dictionaryMap.entrySet()) {
      System.out.println("--- " + entry.getKey() + " ---");

      List<String> words = entry.getValue();
      words.sort(Comparator.naturalOrder());

      for (int i = 0; i < words.size(); i++) {
        System.out.println(i + 1 + ". " + words.get(i));
      }
    }
  }

  private void addWord(String word) {
    List<String> words = dictionaryMap.containsKey(word.charAt(0))
        ? dictionaryMap.get(word.charAt(0))
        : new ArrayList<>();

    words.add(word);
    dictionaryMap.put(word.charAt(0), words);
  }
}

addWord()에서 Map에 key가 없다면 새 List를 생성하고, key가 있다면 key에 해당하는 List를 가져온다. 그리고 List에 word를 저장하고 List를 Map에 저장한다.

printSortedDictionaryMap()에서 반복문으로 Entry를 가져와서 Key와 Value를 가져온다. Value는 List이므로 정렬 후 List를 돌며 word를 출력한다.

위의 정렬 예시와 마찬가지로 정렬된 Map으로 저장하고 싶다면 LinkedHashMap<Character, List<String>>으로 새 Map을 생성하여 정렬된 List를 순서대로 저장한다.

1. 문제

www.codewars.com/kata/56a32dd6e4f4748cc3000006

문제 설명

data and data1 are two strings with rainfall records of a few cities for months from January to December. The records of towns are separated by\n. The name of each town is followed by:

data and towns can be seen in "Your Test Cases:".

Task:

• function:mean(town, strng)should return the average of rainfall for the citytown and the strng data ordata1(In R and Julia this function is calledavg).
• function:variance(town, strng) should return the variance of rainfall for the city town and the strng data or data1.

제한 사항

• if functions mean or variance have as parameter town a city which has no records return -1 or -1.0 (depending on the language)

• Don't truncate or round: the tests will pass if abs(your\_result - test\_result) <= 1e-2 or abs((your\_result - test\_result) / test\_result) <= 1e-6 depending on the language.

• Shell tests only variance

• A ref:http://www.mathsisfun.com/data/standard-deviation.html

• data and data1(can be name d0 and d1 depending on the language; see "Sample Tests:") are adapted from:http://www.worldclimate.com

입출력 예

mean("London", data), 51.19(9999999999996)

variance("London", data), 57.42(833333333374)

2. 어떻게 풀까?

• 우선 data가 \n으로 도시들이 구분되어 있고, 도시와 월별 rainfall은 :로 구분되어있다고 하니 data를 통해 각 도시와 rainfall을 split 하는 게 중요해 보인다.
• 그 이후에는 각 rainfall들을 더해서 12로 나누어 평균값(mean)을 구하고, mean을 이용해서 variance도 구하면 되겠다.
• mean은 평균값인게 이해가 갔는데 variance는 뭔지 몰랐다. 근데 참고 링크를 보니까 딱 알겠더라.
• 제한 사항을 보니 입력의 town이 data or data1에 존재하지 않으면 -1을 리턴하라고 한다.
  • 처음에는 입력으로 주어진 town에 대한 결과값만 리턴하면 되겠다. 생각했는데, 이 제한사항 때문에 Map을 이용해야겠다고 생각했다.

3. 코드

테스트 코드

package codeWars.kyu6.rainFall_20201117;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import org.junit.Test;

public class RainfallTest {

  public static String data =
      "Rome:Jan 81.2,Feb 63.2,Mar 70.3,Apr 55.7,May 53.0,Jun 36.4,Jul 17.5,Aug 27.5,Sep 60.9,Oct 117.7,Nov 111.0,Dec 97.9"
          +
          "\n" +
          "London:Jan 48.0,Feb 38.9,Mar 39.9,Apr 42.2,May 47.3,Jun 52.1,Jul 59.5,Aug 57.2,Sep 55.4,Oct 62.0,Nov 59.0,Dec 52.9"
          +
          "\n" +
          "Paris:Jan 182.3,Feb 120.6,Mar 158.1,Apr 204.9,May 323.1,Jun 300.5,Jul 236.8,Aug 192.9,Sep 66.3,Oct 63.3,Nov 83.2,Dec 154.7"
          +
          "\n" +
          "NY:Jan 108.7,Feb 101.8,Mar 131.9,Apr 93.5,May 98.8,Jun 93.6,Jul 102.2,Aug 131.8,Sep 92.0,Oct 82.3,Nov 107.8,Dec 94.2"
          +
          "\n" +
          "Vancouver:Jan 145.7,Feb 121.4,Mar 102.3,Apr 69.2,May 55.8,Jun 47.1,Jul 31.3,Aug 37.0,Sep 59.6,Oct 116.3,Nov 154.6,Dec 171.5"
          +
          "\n" +
          "Sydney:Jan 103.4,Feb 111.0,Mar 131.3,Apr 129.7,May 123.0,Jun 129.2,Jul 102.8,Aug 80.3,Sep 69.3,Oct 82.6,Nov 81.4,Dec 78.2"
          +
          "\n" +
          "Bangkok:Jan 10.6,Feb 28.2,Mar 30.7,Apr 71.8,May 189.4,Jun 151.7,Jul 158.2,Aug 187.0,Sep 319.9,Oct 230.8,Nov 57.3,Dec 9.4"
          +
          "\n" +
          "Tokyo:Jan 49.9,Feb 71.5,Mar 106.4,Apr 129.2,May 144.0,Jun 176.0,Jul 135.6,Aug 148.5,Sep 216.4,Oct 194.1,Nov 95.6,Dec 54.4"
          +
          "\n" +
          "Beijing:Jan 3.9,Feb 4.7,Mar 8.2,Apr 18.4,May 33.0,Jun 78.1,Jul 224.3,Aug 170.0,Sep 58.4,Oct 18.0,Nov 9.3,Dec 2.7"
          +
          "\n" +
          "Lima:Jan 1.2,Feb 0.9,Mar 0.7,Apr 0.4,May 0.6,Jun 1.8,Jul 4.4,Aug 3.1,Sep 3.3,Oct 1.7,Nov 0.5,Dec 0.7";

  public static String data1 =
      "Rome:Jan 90.2,Feb 73.2,Mar 80.3,Apr 55.7,May 53.0,Jun 36.4,Jul 17.5,Aug 27.5,Sep 60.9,Oct 147.7,Nov 121.0,Dec 97.9"
          +
          "\n" +
          "London:Jan 58.0,Feb 38.9,Mar 49.9,Apr 42.2,May 67.3,Jun 52.1,Jul 59.5,Aug 77.2,Sep 55.4,Oct 62.0,Nov 69.0,Dec 52.9"
          +
          "\n" +
          "Paris:Jan 182.3,Feb 120.6,Mar 188.1,Apr 204.9,May 323.1,Jun 350.5,Jul 336.8,Aug 192.9,Sep 66.3,Oct 63.3,Nov 83.2,Dec 154.7"
          +
          "\n" +
          "NY:Jan 128.7,Feb 121.8,Mar 151.9,Apr 93.5,May 98.8,Jun 93.6,Jul 142.2,Aug 131.8,Sep 92.0,Oct 82.3,Nov 107.8,Dec 94.2"
          +
          "\n" +
          "Vancouver:Jan 155.7,Feb 121.4,Mar 132.3,Apr 69.2,May 85.8,Jun 47.1,Jul 31.3,Aug 37.0,Sep 69.6,Oct 116.3,Nov 154.6,Dec 171.5"
          +
          "\n" +
          "Sydney:Jan 123.4,Feb 111.0,Mar 151.3,Apr 129.7,May 123.0,Jun 159.2,Jul 102.8,Aug 90.3,Sep 69.3,Oct 82.6,Nov 81.4,Dec 78.2"
          +
          "\n" +
          "Bangkok:Jan 20.6,Feb 28.2,Mar 40.7,Apr 81.8,May 189.4,Jun 151.7,Jul 198.2,Aug 197.0,Sep 319.9,Oct 230.8,Nov 57.3,Dec 9.4"
          +
          "\n" +
          "Tokyo:Jan 59.9,Feb 81.5,Mar 106.4,Apr 139.2,May 144.0,Jun 186.0,Jul 155.6,Aug 148.5,Sep 216.4,Oct 194.1,Nov 95.6,Dec 54.4"
          +
          "\n" +
          "Beijing:Jan 13.9,Feb 14.7,Mar 18.2,Apr 18.4,May 43.0,Jun 88.1,Jul 224.3,Aug 170.0,Sep 58.4,Oct 38.0,Nov 19.3,Dec 2.7"
          +
          "\n" +
          "Lima:Jan 11.2,Feb 10.9,Mar 10.7,Apr 10.4,May 10.6,Jun 11.8,Jul 14.4,Aug 13.1,Sep 23.3,Oct 1.7,Nov 0.5,Dec 10.7";

  @Test
  public void meanTest() {
    assertThat(Rainfall.mean("London", data), is(51.199999999999996));
    assertThat(Rainfall.mean("Beijing", data), is(52.416666666666664));
  }

  @Test
  public void varianceTest() {
    assertThat(Rainfall.variance("London", data), is(57.42833333333374));
    assertThat(Rainfall.variance("Beijing", data), is(4808.37138888889));
  }

  @Test
  public void whenDataHasNotTownTest() {
    assertThat(Rainfall.mean("Lon", data), is(-1.0));
    assertThat(Rainfall.variance("Lon", data), is(-1.0));
  }
}

실제 코드

package codeWars.kyu6.rainFall_20201117;

import java.util.HashMap;
import java.util.Map;

public class Rainfall {

  public static double mean(String town, String strng) {
    Map<String, Double> townRainfallMeanMap = buildTownRainfallMeanMap(strng);

    return townRainfallMeanMap.getOrDefault(town, -1.0);
  }

  private static Map<String, Double> buildTownRainfallMeanMap(String strng) {
    Map<String, Double> townRainfallMeanMap = new HashMap<>();
    String[] townAndMonthRainfalls = strng.split("\n");

    for (String townAndMonthRainfall : townAndMonthRainfalls) {
      String targetTown = townAndMonthRainfall.split(":")[0];
      String[] monthRainfalls = townAndMonthRainfall.split(":")[1].split(",");
      double sumOfRecords = 0;

      for (String monthRainfall : monthRainfalls) {
        sumOfRecords += Double.parseDouble(monthRainfall.split(" ")[1]);
      }
      townRainfallMeanMap.put(targetTown, sumOfRecords / 12);
    }

    return townRainfallMeanMap;
  }

  public static double variance(String town, String strng) {
    Map<String, Double> townRainfallVarianceMap = buildTownRainfallVarianceMap(town, strng);

    return townRainfallVarianceMap.getOrDefault(town, -1.0);
  }

  private static Map<String, Double> buildTownRainfallVarianceMap(String town, String strng) {
    Map<String, Double> townRainfallVarianceMap = new HashMap<>();
    double mean = mean(town, strng);
    String[] townAndMonthRainfalls = strng.split("\n");

    for (String townAndMonthRainfall : townAndMonthRainfalls) {
      String targetTown = townAndMonthRainfall.split(":")[0];
      String[] monthRainfalls = townAndMonthRainfall.split(":")[1].split(",");
      double sumOfRecords = 0;

      for (String monthRainfall : monthRainfalls) {
        double rainfall = Double.parseDouble(monthRainfall.split(" ")[1]);
        sumOfRecords += Math.pow((rainfall - mean), 2);
      }
      townRainfallVarianceMap.put(targetTown, sumOfRecords / 12);
    }

    return townRainfallVarianceMap;
  }
}

mean()과 variance() 둘 다 비슷하게 구현했다. data로 주어진 strng을 \n으로 쪼개 town별로 분리하고, 분리한 town String 배열에서 :으로 쪼개 도시와 월별 rainfall로 분리했다. 그리고 rainfall끼리 전부 더해서 12로 나누어준 값을 map에 저장했다. varinace()에서는 mean()을 이용하여 variance를 구했다.

4. 느낀점

• 어렵지 않은 문제였다. String을 어떻게 잘 쪼개냐가 관건인 것 같다.

1. 문제

programmers.co.kr/learn/courses/30/lessons/17682

문제 설명

카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다.
갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다.

1. 다트 게임은 총 3번의 기회로 구성된다.
2. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
3. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱으로 계산된다.
4. 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
5. 스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고)
6. 스타상(*)의 효과는 다른 스타상(*)의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상(*) 점수는 4배가 된다. (예제 4번 참고)
7. 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
8. Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
9. 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.

0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.

제한 사항

입력 형식

점수|보너스|[옵션]으로 이루어진 문자열 3세트.
예)1S2D*3T

• 점수는 0에서 10 사이의 정수이다.
• 보너스는 S, D, T 중 하나이다.
• 옵선은 *이나 # 중 하나이며, 없을 수도 있다.

출력 형식

3번의 기회에서 얻은 점수 합계에 해당하는 정수값을 출력한다.
예) 37

입출력 예

2. 어떻게 풀까?

• 문제에서 다트는 총 3번 던지니까 String의 split()메서드를 이용해서 점수와 보너스,옵션을 분리할 수 있을 것이다.
  • 근데 분리할 때, empty string ("")이 생길 수 있으니 유의해야할듯.
• 그래서 보너스 문자에 따라 점수에 2제곱, 3제곱, *2, *-1 등을 해주어 배열에 저장하고 다 더해주면 되겠다.
• 문자열을 반복문 돌며 계산해줘도 될거라 생각했는데 10점이 변수가되기 때문에 그냥 분리하는게 낫겠다.

3. 코드

TDD 연습을 위해 1번 테스트 👉 실제 코드 작성 👉 리팩토링 👉 다음 테스트 👉 실제 코드 작성 👉 리팩토링 ... 순서로 계속 살을 붙여나갔다.

테스트 코드

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

  @Test
  public void test1() {
    assertThat(new Solution().solution("1S2D*3T"), is(37));
  }

  @Test
  public void test2() {
    assertThat(new Solution().solution("102S#10S"), is(9));
  }

  @Test
  public void test3() {
    assertThat(new Solution().solution("1D2S0T"), is(3));
  }

  @Test
  public void test4() {
    assertThat(new Solution().solution("1S*2T*3S"), is(23));
  }

  @Test
  public void test5() {
    assertThat(new Solution().solution("1D#2S*3S"), is(5));
  }

  @Test
  public void test6() {
    assertThat(new Solution().solution("1T2D3D#"), is(-4));
  }

  @Test
  public void test7() {
    assertThat(new Solution().solution("1D2S3T*"), is(59));
  }
}

실제 코드

import java.util.Arrays;

public class Solution {

  public int solution(String dartResult) {
    int[] scores = getScores(dartResult);
    String[] bonus = getBonus(dartResult);

    return getSumOfScore(scores, bonus);
  }

  private int getSumOfScore(int[] scores, String[] bonus) {
    int[] result = new int[3];

    for (int i = 0; i < bonus.length; i++) {
      int score = scores[i];
      if (bonus[i].contains("T")) {
        score = (int) Math.pow(score, 3);
      } else if (bonus[i].contains("D")) {
        score = (int) Math.pow(score, 2);
      }
      if (bonus[i].contains("*")) {
        score *= 2;
        if (i != 0) {
          result[i - 1] *= 2;
        }
      } else if (bonus[i].contains("#")) {
        score *= -1;
      }
      result[i] = score;
    }
    return Arrays.stream(result).sum();
  }

  private String[] getBonus(String dartResult) {
    String[] bonus = new String[3];
    String[] bonusSplit = dartResult.split("\\d");
    int index = 0;
    for (int i = 0; i < bonusSplit.length; i++) {
      if (!bonusSplit[i].equals("")) {
        bonus[index++] = bonusSplit[i];
      }
    }
    return bonus;
  }

  private int[] getScores(String dartResult) {
    int[] scores = new int[3];
    String[] scoresSplit = dartResult.split("[SDT*#]");
    int index = 0;
    for (String score : scoresSplit) {
      if (!score.equals("")) {
        scores[index++] = Integer.parseInt(score);
      }
    }
    return scores;
  }
}

• getBonus()와 getScores()에서 emptyString("")을 제외하고 점수, 보너스를 각 배열에 담았다.
• 그 배열들을 이용해서 getSumOfScore()메서드를 통해 총 점수를 계산하고 리턴했다.

4. 느낀점

• 카카오 코테 문제가 비교적 어렵다고해도 level1 수준의 문제는 간단하게 풀 수 있다. 시간도 약 20~30분정도? 더 줄이면 좋겠지만, level1을 다 풀 수 있는걸로 만족은 한다.
• level2 이상은 좀 많이 어렵긴한데 적어도 level1 수준의 문제는 확실히 다 풀 수 있도록 해야겠다.

1. 개요 - LCS가 뭘까?

LCS(Longest Common Subsequence) 알고리즘은 공통부분 문자열 중 가장 길이가 긴 문자열을 찾는 알고리즘을 뜻한다.

여기서 Subsequnce와 Substring의 차이가 있는데 Substring은 연속된 부분 문자열이고, Subsequence는 연속되지 않는 부분 문자열이다.

같은 길이의 다른 해가 있을 수 있다.

막상 직접 만드려니 어렵네요;; 틀렸다면 댓글 부탁드립니다 ㅜ

2. LCS의 길이 구하기

LCS 알고리즘은 DP(Dynamic Programming)이므로 특정 범위까지의 LCS을 구하고 다음 범위의 LCS를 구할 때 이전에 구해 둔 값을 이용하여 문제를 해결한다.

점화식

점화식만 보면 이해가 잘 안 된다. 예시를 들어 설명하는 게 더 이해하기 쉬우니 예시를 들어보자.

문자열 "ABCBDAB"와 "ADCABA"를 표를 이용해서 비교해보자. 

1) 0부터

0을 추가하는 이유는 공통 부분이 없다면 LCS가 길이가 0이기 때문이다.

2) B와 비교 

표를 보는 방법은 열의 {A}와 행의 {A}, {AB}, {ABC}, {ABCB}.. 의 마지막 element를 비교하는 것이다.

점화식을 따라해보자.

• 우선 {A}와 {A}를 비교해보면 마지막 element는 "A"로 같다. 그러므로 두 문자열에서 "A"를 뺀 {}(empty)와, {}(empty)의 LCS길이인 0에 +1을 하여 표기한다. (점화식 2번 case)
• 그다음, {A}와 {AB}를 비교해 보자. 마지막 element는 "A"와 "B"로 다르다. 그러므로 {}(empty)와 {AB}의 LCS길이인 0과 {A}와 {A}의 LCS길이인 1중 더 큰 값인 1을 표기한다. (점화식 3번 case)
• 이번엔 {A}와 {ABC}를 비교해보자. 마지막 element는 "A"와 "C"로 다르다. 그러므로 {}(empty)와 {ABC}의 LCS길이인 0과 {A}와 {AB}의 LCS길이인 1중 더 큰 값인 1을 표기한다. (역시 점화식 3번 case)
• 계속 반복하면서 표기하다가 다시 {A}와 {ABCBDA}를 비교해보자. 마지막 element는 "A"로 같다. 그러면 두 문자열 마지막 element "A"가 없는 {}(empty)와 {ABCBD}의 LCS길이인 0에 +1을 하여 표기한다. (점화식 2번 case)

위에서 한 표기들을 DP측면에서 살펴보면

• {A}와 {A}의 LCS길이를 구하기 위해서 이전에 구해놓은 {}(empty)와 {}(empty)의 LCS길이인 0을 이용했다. 즉, 이전의 LCS길이값을 이용해서 현재 LCS길이값을 구할 수 있었다.
• {A}와 {AB}의 LCS길이는 공통부분이 "A"이기 때문에 1이다. 이것은 이전에 구해놓은 {}(empty)와 {AB}의 LCS길이, 그리고 {A}와 {A}의 LCS길이를 이용해서 구할 수 있었다. 

3) 몇 번 더 반복해보자

역시 점화식을 따라 해보자

• {ADCA}와 {ABCBDA}를 비교해보면, 마지막 element는 "A"로 같다. 그러므로 "A"가 없는 {ADC}와 {ABCBD}의 LCS길이인 2에 +1을 하여 표기한다 (점화식 2번 case)
• {ABCBDAB}와 {ADCABA}를 비교해보자. 마지막 element는 "B"와 "A"로 서로 다르다. 그러므로 {ABCBDAB}와 {ADCAB}의 LCS길이 4와 {ABCBDA}와 {ADCABA}의 LCS길이 4 중 더 큰 값을 표기한다. (점화식 3번 case)

이것도 DP관점에서 보면

• {ADCA}와 {ABCBDA}의 LCS길이를 구하기 위해 이전에 구해놓은 {ADC}와 {ABCBD}의 LCS길이를 이용한다.
• {ABCBDAB}와 {ADCABA}의 LCS길이를 구하기 위해 이전에 구해놓은 {ABCBDAB} 와 {ADCAB}, {ABCBDA}와 {ADCABA} LCS길이를 이용한다.

따라서 점화식을 해석하면

• 문자열 X나 문자열 Y의 index가 0일 경우 0
• 문자열의 마지막 element를 비교하여 같을 경우 왼쪽 위 대각선의 값 +1을 표기
• 문자열의 마지막 element를 비교하여 다를 경우 왼쪽 값과 위쪽 값 중 더 큰 값을 표기

코드로는 어떻게 구현할까?

package algorithm.lcs;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

import org.junit.jupiter.api.Test;

public class LongestCommonSubsequence {

  @Test
  public void testLcsLength() {
    assertThat(lcsLength("ADCABA", "ABCBDAB"), is(4));
  }

  public int lcsLength(String x, String y) {
    int maxLength = 0;

    x = "0" + x;
    y = "0" + y;
    int[][] lcsTable = new int[x.length()][y.length()];

    for (int i = 1; i < x.length(); i++) {
      for (int j = 1; j < y.length(); j++) {
        if (x.charAt(i) == y.charAt(j)) {
          lcsTable[i][j] = lcsTable[i - 1][j - 1] + 1;
          maxLength = lcsTable[i][j];
        } else {
          lcsTable[i][j] = Math.max(lcsTable[i][j - 1], lcsTable[i - 1][j]);
        }
      }
    }
    return maxLength;
  }
}

자바의 경우 int 배열을 선언하면 0으로 초기화되기 때문에 "0"에 해당하는 0 값을 따로 넣어주지 않았다.

3. LCS 구하기

LCS 길이를 표기해 나갔던 표를 역추적하여 LCS를 구할 수 있다.

LCS 길이 점화식을 다시 생각해보면

문자열 마지막 element가 같을 경우 왼쪽 위 대각선 값 + 1

문자열 마지막 element가 다를 경우 왼쪽이나 위쪽 값 중 더 큰 값

이를 이용해서 표를 역추적하면 실제 LCS를 구할 수 있다.

역시 이해가 잘 안 되니까 표를 보자.

우선 표의 끝(오른쪽 아래)에서 시작하자. ({6,8}("A", "B"))

시작 위치에서 위쪽, 대각선(왼쪽 위), 왼쪽 값을 비교하면 대각선 값 보다 크고 왼쪽, 위쪽 값과 같다. 이때 왼쪽 or 위쪽으로 이동할 수 있는데 위쪽을 선택

• 단, 왼쪽이나 위쪽을 선택했을 때, 선택한 방향으로만 이동해야 한다.

이동한 위치 ({5,8} ("B", "B"))에서 element 값이 같다. 그리고 왼쪽, 위쪽, 대각선 값보다 크다. 그러므로 대각선으로 이동한다. 이때 현재 위치 값 "B"를 기록해둔다.

• Output : B

이동한 위치 ({4,7}, ("A", "A"))에서 element 값이 "A"로 같다. 역시 왼쪽, 위쪽, 대각선 값보다 크기 때문에 "A"를 기록하고 대각선으로 이동한다.

• Output : AB

이동한 위치 ({3,6}, ("C", "D")}에서 element 값이 다르다. 그리고 대각선 값보다는 크고, 왼쪽 위쪽 값과는 같다. 처음에 이럴 경우 위쪽으로 이동하는 것을 선택했기 때문에 위쪽으로 이동한다.

이동한 위치 ({2,6}, ("D", "D")}에서 element 값이 "D"로 같다. 역시 왼쪽, 위쪽, 대각선 값보다 크기 때문에 "D"를 기록하고 대각선으로 이동한다.

• Output : DAB

이동한 위치 ({1,5}, ("A", "B")}에서 element 값이 다르다. 대각선과 위쪽 값보다는 크고, 왼쪽 값과는 같다. 그러므로 왼쪽으로 이동한다.

왼쪽으로 계속 이동하다가 ({1,1}, ("A", "A"))에서 element 값이 "A"로 같다. "A"를 기록하고 대각선으로 이동한다.

• Output : ADAB

이동한 위치가 {0,0}이므로 종료, 그러므로 LCS는 "ADAB"이다.

왼쪽과 위쪽 모두 같을 때 왼쪽을 선택한 경우도 있다.

이럴 경우 LCS는 "ACBA"이다.

즉, 같은 LCS 길이에 다른 LCS값이 나올 수 있다.

소스 코드

package algorithm.lcs;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

import org.junit.jupiter.api.Test;

public class LongestCommonSubsequence {

  @Test
  public void testLcsLength() {
    assertThat(lcs("ADCABA", "ABCBDAB"), is("ADAB"));
  }

  public String lcs(String x, String y) {
    x = "0" + x;
    y = "0" + y;
    int[][] lcsTable = getLcsTable(x, y);

    StringBuilder lcs = new StringBuilder();
    backTracking(lcs, x.length() - 1, y.length() - 1, lcsTable, x);

    return lcs.toString();
  }

  private void backTracking(StringBuilder lcs, int m, int n, int[][] lcsTable, String x) {
    if (m == 0 || n == 0) {
      return;
    }
    //위쪽, 왼쪽, 대각선(왼쪽 위) 값보다 클 때 👉 문자 기록하고 대각선으로 이동
    if (lcsTable[m][n] > lcsTable[m - 1][n - 1]
        && lcsTable[m][n] > lcsTable[m][n - 1]
        && lcsTable[m][n] > lcsTable[m - 1][n]) {
      lcs.insert(0, x.charAt(m));
      backTracking(lcs, m - 1, n - 1, lcsTable, x);
    }
    //왼쪽 값과 같고, 위쪽 값보다 클 때 👉 왼쪽으로 이동
    else if (lcsTable[m][n] > lcsTable[m - 1][n]
        && lcsTable[m][n] == lcsTable[m][n - 1]) {
      backTracking(lcs, m, n - 1, lcsTable, x);
    } 
    //왼쪽, 위쪽 값과 같을 때 👉 위쪽으로 이동
    else {
      backTracking(lcs, m - 1, n, lcsTable, x);
    }
  }
}

마지막 두 조건문 순서를 바꾸면 LCS는 "ACBA"이다.

4. 예제

• Longest Common Subsequence - www.codewars.com/kata/52756e5ad454534f220001ef
• 문제 풀 때마다 추가 예정