1. 문제

https://programmers.co.kr/learn/courses/30/lessons/43163

문제 설명

제한 사항

입출력 예

2. 어떻게 풀까?

• 인자로 주어지는 begin에서 시작해서 words에 주어진 단어들과 비교하면서 알파벳 하나만 바꿔서 그 단어가 될 수 있는지 확인한다.
• words내에 방문한 단어들을 방문 표시하고, 모든 단어들을 방문하거나 target과 같은 단어를 방문하고 난 뒤에는 다시 방문 표시를 지워주어야 한다. 이게 무슨소리냐.. 말로 설명하니 어려우니까 그림으로 대체

• 아니 그럼 visit을 굳이 둘 필요 없지않냐? 라고 생각할 수도 있는데.... 그러면 무한루프에 hot → dot → hot → dot ... 이런식으로 무한루프에 빠지니까 visit또한 반드시 필요하다.

• hit에서 hot으로, hot에서 dog로 알파벳 하나를 바꿔서 만들 수 있는 단어라는 것을 우리는 직관적으로 알 수 있지만 이것을 코드로는 어떻게 구현할까?
• 단어와 단어 한 글자씩 비교하면서 다른 글자라면 count를 증가시키고, 그 count가 1이라면 알파벳 하나를 바꿔 만들 수 있는 단어가 된다고 판단하면 되겠다.

3. 코드 (Java)

package programmers.level3.단어변환_20220125;

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

public class Solution {

  public int result = Integer.MAX_VALUE;
  public Map<String, Boolean> visit;

  public int solution(String begin, String target, String[] words) {
    visit = new HashMap<>();
    for (String word : words) {
      visit.put(word, false);
    }
    dfs(begin, target, words, 0);
    return result == Integer.MAX_VALUE ? 0 : result;
  }

  private void dfs(String currentWord, String targetWord, String[] words, int distance) {

    if (currentWord.equals(targetWord)) {
      result = Math.min(result, distance);
      return;
    }

    for (String word : words) {
      if (!visit.get(word) && getCharDifferenceCount(currentWord, word) == 1) {
        visit.replace(word, true);
        dfs(word, targetWord, words, distance + 1);
        visit.replace(word, false);
      }
    }
  }

  private int getCharDifferenceCount(String a, String b) {
    if (a.length() != b.length()) {
      return -1;
    }

    int result = 0;
    for (int i = 0; i < a.length(); i++) {
      if (a.charAt(i) != b.charAt(i)) {
        result++;
      }
    }
    return result;
  }
}

사실 틀렸었다.

이유를 생각해봤는데.... 알파벳을 한 번 바꿔서 일치하는지 체크하는 부분에서 실수를 저질렀다.

    for (String word : words) {
      String erase = currentWord.replaceAll("[" + word + "]", "");
      if (!visit.get(word) && erase.length() == 1) {
        visit.replace(word, true);
        dfs(word, targetWord, words, distance + 1);
        visit.replace(word, false);
      }
    }

내 생각은 이랬다. "hot"에서 정규표현식을 이용하여 "[hit]"에 매치되는 부분을 지우면 "o"만 남게되고 그러면 알파벳 차이가 1개이니까 조건에 부합하겠구나! 나 천잰듯?

천재가 아니라 멍청이었다.

만약 단어가 "hto"였다면 어떨까? "hto" → "hit"가 되려면 알파벳을 2개 바꿔야한다. (t → i, o → t) 근데 저 코드대로라면 erase는 역시 "o"만 남게되고 조건에 맞으니까 if문을 통과하게 된다.

아니.. 개 허술한 코드였는데.. 다 틀려야지 하나만 틀리니까 더 찾기 힘들잖아.....................

그래서 정공법으로 코드 수정한 결과가 getCharDifferenceCount() 메소드를 이용한 것이었다.

그나마 다행인 것은 구글링해서 뭐가 틀렸는지 확인한 것이 아니라 스스로 틀린 부분을 생각해낸 부분이라는점..?

1. 문제

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

문제 설명

제한 사항

입출력 예

2. 어떻게 풀까?

• 문제에서 그림은 실제로 보면 직삼각형이다.

• 7부터 아래로 내려가면서 값을 더한다, 겹치는 칸은 더 큰 값을 할당한다.

• 배열의 처음과 끝은, 대소 비교를 할 필요 없이 현재 값과 이전 행의 같은 열 값을 더한 값이다
• 그 외에는 이전 행의 같은 열과 이전 행중에서 큰 값과 더한 값이다.

3. 코드

테스트 코드

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

import org.junit.Test;

public class SolutionTest {

  @Test
  public void test1() {
    int[][] triangle = {
        {7},
        {3, 8},
        {8, 1, 0},
        {2, 7, 4, 4},
        {4, 5, 2, 6, 5}
    };
    assertThat(new Solution().solution(triangle), is(30));
  }
}

실제 코드

import java.util.Arrays;

public class Solution {

  public int solution(int[][] triangle) {
    int[][] maxSums = init(triangle);
    for (int row = 1; row < triangle.length; row++) {
      fillFirstAndLast(maxSums, triangle, row);
      for (int j = 1; j < maxSums[row].length - 1; j++) {
        maxSums[row][j] = Math.max(maxSums[row - 1][j - 1], maxSums[row - 1][j])
            + triangle[row][j];
      }
    }
    return Arrays.stream(maxSums[maxSums.length - 1]).max().getAsInt();
  }

  private void fillFirstAndLast(int[][] maxSums, int[][] triangle, int row) {
    int first = 0;
    int last = maxSums[row].length - 1;

    maxSums[row][first] = maxSums[row - 1][first] + triangle[row][first];
    maxSums[row][last] = maxSums[row - 1][last - 1] + triangle[row][last];
  }

  private int[][] init(int[][] triangle) {
    int[][] result = new int[triangle.length][];
    for (int i = 0; i < triangle.length; i++) {
      result[i] = new int[triangle[i].length];
    }
    result[0][0] = triangle[0][0];

    return result;
  }
}

• init() 에서 배열을 생성하고 (0,0)에 triangle[0][0]을 할당한다.
• fillFirstAndLast()에서 현재 행의 처음 열과 마지막 열의 값을 할당한다.
• 그리고 그 외의 값은 이전 행의 같은 열과, 이전 열중 더 큰 값과 현재 값을 더한 값을 할당한다.

Best 코드 (내가 보기에 Best)

import java.util.Arrays;

public class BestAnswer {

  public static int solution(int[][] triangle) {
    for (int row = 1; row < triangle.length; row++) {
      triangle[row][0] += triangle[row - 1][0];
      triangle[row][row] += triangle[row - 1][row - 1];
      for (int col = 1; col < row; col++) {
        triangle[row][col] += Math.max(triangle[row - 1][col], triangle[row - 1][col - 1]);
      }
    }
    return Arrays.stream(triangle[triangle.length - 1]).max().getAsInt();
  }
}

• 굳이 새 배열을 생성하지 않고, 현재 값에 최대값을 더한 값을 할당해준다.
• triangle[row][triangle[row].length-1] 보다 triangle[row][row]가 훨씬 깔끔해 보인다.

4. 느낀 점

• 예전에 비슷한 문제를 풀어본 기억이 나서 쉽게 풀었다.

1. 문제

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

문제 설명

제한 사항

입출력 예

2. 어떻게 풀까?

• lock을 가만히 두고 key를 끝에서 1 x 1에서 n x n까지 이동시키면서 홈에 맞는지 확인한다.
• 맞지 않는다면 key를 90도 회전한다.
• key를 4번 회전시켜도 그대로라면 false를 리턴한다.

• 위와 같이 생각했는데, 코드로 어떻게 구현해야 할지 감이 안 와서 고민하다가 결국 다른 사람이 푼 코드를 참고했다.
• 코드를 보니, 반대로 생각했다. key는 가만히 두고, lock을 움직이면서 key와 맞는지 체크한다.
• 코드로 구현하기 위해서 key에 padding을 했다.

3. 코드

테스트 코드

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

import org.junit.Test;

public class SolutionTest {

  @Test
  public void test1() {
    int[][] key = {
        {0, 0, 0},
        {1, 0, 0},
        {0, 1, 1}
    };
    int[][] lock = {
        {1, 1, 1},
        {1, 1, 0},
        {1, 0, 1}
    };
    assertThat(new Solution().solution(key, lock), is(true));
  }
}

실제 코드

public class Solution {

  public boolean solution(int[][] key, int[][] lock) {
    int padSize = lock.length - 1;

    for (int i = 0; i < 4; i++) {
      key = rotate(key);
      int[][] paddedKey = pad(key, padSize);
      for (int j = 0; j < paddedKey.length - padSize; j++) {
        for (int k = 0; k < paddedKey.length - padSize; k++) {
          if (isValid(lock, paddedKey, j, k)) {
            return true;
          }
        }
      }
    }

    return false;
  }

  private boolean isValid(int[][] lock, int[][] paddedKey, int j, int k) {
    for (int l = 0; l < lock.length; l++) {
      for (int m = 0; m < lock.length; m++) {
        if (lock[l][m] + paddedKey[j + l][k + m] != 1) {
          return false;
        }
      }
    }
    return true;
  }

  private int[][] pad(int[][] key, int padSize) {
    int[][] result = new int[key.length + padSize * 2][key.length + padSize * 2];

    for (int i = 0; i < key.length; i++) {
      for (int j = 0; j < key.length; j++) {
        result[padSize + i][padSize + j] = key[i][j];
      }
    }
    return result;
  }

  private int[][] rotate(int[][] key) {
    int[][] result = new int[key.length][key.length];
    for (int i = 0; i < key.length; i++) {
      for (int j = 0; j < key.length; j++) {
        result[i][j] = key[key.length - 1 - j][i];
      }
    }
    return result;
  }

  private int[][] copy(int[][] key) {
    int[][] result = new int[key.length][key.length];
    for (int i = 0; i < key.length; i++) {
      for (int j = 0; j < key.length; j++) {
        result[i][j] = key[i][j];
      }
    }
    return result;
  }
}

• rotate() 에서 key를 오른쪽 90도로 회전한다.
• pad()에서 lock의 length - 1 만큼 상하좌우로 추가하여 padding 해준다.
• pad된 key의 0부터 끝까지 가는 게 아니라 key까지만 이동한다. 더 이동하면 lock이 pad범위를 벗어나기 때문

4. 느낀 점

• 문제를 처음 보고, 어렵지만 할 수 있겠다고 생각했다. 실제로 문제 해결 방법은 맞다고 생각한다.
• 근데 이것을 코드로 구현하는 과정이 너무 어렵다.. 이걸 잘해야 level 3 문제들을 풀 수 있을 듯.

1. 문제

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

문제 설명

제한 사항

입출력 예

11의 경우 22 / 2 = 11이므로 2를 3개 사용해서 만들 수 있다.

2. 어떻게 풀까?

• N으로 9개 이상 표현하면 표현할 수 없다는 것으로 보고 -1을 리턴한다.
• 그러므로 1개로 표현했을 때 만들 수 있는 값 ~ 8개로 표현했을 때 만들 수 있는 값에서 number와 같은 값이 있으면 리턴하도록 한다.
  1. N 1개를 사용했을 때 표현 가능한 숫자 - N
  2. N 2개를 사용했을 때 표현 가능한 숫자 - NN, (N 1개를 사용했을 때 표현 가능한 값) 사칙연산 (N 1개를 사용했을 때 표현 가능한 값)
  3. N 3개를 사용했을 때 표현 가능한 숫자 - NNN, (N 1개를 사용했을 때 표현 가능한 값) 사칙연산 (N 2개를 사용했을 때 표현 가능한 값) U (N 2개를 사용했을 때 표현 가능한 값) 사칙연산 (N 1개를 사용했을 때 표현 가능한 값)
     • NNN
     • N + NN, N - NN, N * NN, N / NN
     • N + (N+N), N - (N+N), N * (N+N), N / (N+N)
     • N + (N-N), N - (N-N), N * (N-N), N / (N-N)
     • N + (N*N), N -(N*N), N *(N*N), N /(N*N)
     • N + (N/N), N -(N/N), N *(N/N), N /(N/N)
     • NN + N, NN - N, NN * N, NN / N
     • (N+N) + N, (N+N) - N, (N+N) * N, (N+N) / N
     • (N-N) + N, (N-N) - N, (N-N) * N, (N-N) / N
     • (N*N) + N, (N*N) - N, (N*N) * N, (N*N) / N
     • (N/N) + N, (N/N) - N, (N/N) * N, (N/N) / N
  4. 덧셈과 곱셈은 교환 법칙이 성립하기 때문에, (1개 표현 수) 사칙연산 (2개 표현 수)와 (2개 표현 수) 사칙연산 (1개 표현 수)가 같지만, 뺄셈과 나눗셈은 성립하지 않기 때문에 다르다
     • 2 + 22 = 22 + 2 = 24, 2 * 22 = 22 * 2 = 44
     • 2 - 22 = -20, 22 - 2 = 20, 2 / 22 = 0, 22 / 2 = 11
  5. 그러므로 N x개를 사용했을 때 표현 가능한 숫자는 - N을 x번 붙힌 값, (N 1개 표현 수) (덧셈, 뺄셈, 역뺄셈, 곱셈, 나눗셈, 역나눗셈) (N x-1개 표현수) U (N 2개 표현 수) (덧셈, 뺄셈, 역뺄셈, 곱셈, 나눗셈, 역나눗셈) (N x-2개 표현수) U ... U (N x/2개 표현 수) (덧셈, 뺄셈, 역뺄셈, 곱셈, 나눗셈, 역나눗셈) (N x/2개 표현수) 이다.

3. 코드

테스트 코드

package doNotSolve.programmers.level3.N으로표현;

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(5, 12), is(4));
    assertThat(new Solution().solution(2, 11), is(3));
    assertThat(new Solution().solution(5, 5), is(1));
    assertThat(new Solution().solution(5, 10), is(2));
    assertThat(new Solution().solution(5, 31168), is(-1));
    assertThat(new Solution().solution(1, 1121), is(7));
  }

  @Test
  public void test2() {
    assertThat(new Solution().solution(5, 1010), is(7));
    assertThat(new Solution().solution(3, 4), is(3));
    assertThat(new Solution().solution(5, 5555), is(4));
    assertThat(new Solution().solution(5, 5550), is(5));
  }

  @Test
  public void test3() {
    assertThat(new Solution().solution(5, 20), is(3));
    assertThat(new Solution().solution(3, 30), is(3));
    assertThat(new Solution().solution(6, 65), is(4));
    assertThat(new Solution().solution(5, 2), is(3));
    assertThat(new Solution().solution(5, 4), is(3));
    assertThat(new Solution().solution(1, 1), is(1));
    assertThat(new Solution().solution(1, 11), is(2));
    assertThat(new Solution().solution(1, 111), is(3));
    assertThat(new Solution().solution(1, 1111), is(4));
    assertThat(new Solution().solution(1, 11111), is(5));
    assertThat(new Solution().solution(7, 7776), is(6));
    assertThat(new Solution().solution(7, 7784), is(5));
  }
}

실제 코드

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Map;

public class Solution {

  Map<Integer, HashSet<Integer>> calculationResultMap;

  public int solution(int N, int number) {
    calculationResultMap = new HashMap<>();

    for (int i = 1; i < 9; i++) {
      HashSet<Integer> calculationResults = getCalculationValues(i, N);
      if (calculationResults.contains(number)) {
        return i;
      }
      calculationResultMap.put(i, calculationResults);
    }

    return -1;
  }

  private HashSet<Integer> getCalculationValues(int count, int N) {
    HashSet<Integer> set = new LinkedHashSet<>();
    int attach = getAttachValue(count, N);
    set.add(attach);

    for (int j = 1; j <= count / 2; j++) {
      for (int a : calculationResultMap.get(j)) {
        for (int b : calculationResultMap.get(count - j)) {
          for (Operator op : Operator.values()) {
            set.add(op.calcuate(a, b));
          }
        }
      }
    }

    return set;
  }

  private int getAttachValue(int count, int N) {
    return Integer.parseInt(Integer.toBinaryString((int) Math.pow(2, count) - 1)) * N;
  }

}

enum Operator {
  PLUS {
    @Override
    public int calcuate(int a, int b) {
      return a + b;
    }
  },
  MINUS {
    @Override
    public int calcuate(int a, int b) {
      return a - b;
    }
  },
  BACKMINUS {
    @Override
    public int calcuate(int a, int b) {
      return b - a;
    }
  },
  MULTIPLY {
    @Override
    public int calcuate(int a, int b) {
      return a * b;
    }
  },
  DIVIDE {
    @Override
    public int calcuate(int a, int b) {
      return b == 0 ? 0 : a / b;
    }
  },
  BACKDIVIDE {
    @Override
    public int calcuate(int a, int b) {
      return a == 0 ? 0 : b / a;
    }
  };

  abstract int calcuate(int a, int b);
}

4. 느낀 점

• 처음 문제를 풀 때, N이 9개 이상이면 -1을 리턴하라고 해서 N 1개로 표현 가능한 식, 2개로 표현 가능한 식, ..., 8개로 표현 가능한 식을 Set에 담아서 그 식을 계산한 값이 number와 같으면 리턴하도록 코드를 작성하면 되겠구나 생각했다.
• 근데 처음 생각한 코드는, (N-N/N*NN+N) 같은 식은 괄호 위치에 따라 다르게 계산될 수 있는데 그걸 생각 못하고 앞에서부터 계산한 값만 생각했다. 그래서 계속 1번, 8번 테스트가 실패로 나왔다.
• 왜 틀렸는지 계속 생각해봐도 이해가 안 돼서 다른 사람들이 작성한 코드를 봤는데, 괄호 때문에 계산 순서가 달라질 수 있는 것을 고려하지 않은 점, 뺼셈과 나눗셈은 교환 법칙이 성립하지 않는 점을 생각하지 못해서 틀린 것 같다.
• 그 외에도 Enum을 사용해서 덧셈, 뺄셈, 역뺄셈, 곱셈, 나눗셈, 역나눗셈을 해결한 코드가 전혀 생각하지 못한 방법이라 똑같이 따라 해 보았다.
• 완전 탐색(DFS)을 이용하여 해결한 답도 많았는데, 해당 문제 카테고리가 DP(Dynamic Programming)이기도 했고, DFS를 이용하면 N*N-N/N 같은 식도 고려하지 않고 통과가 된다고 한다. 그래서 DFS는 따로 참고하지 않았다.

1. 문제

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

문제 설명

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리 초) 간 처리하는 요청의 최대 개수를 의미한다.

제한 사항

입력 형식

• solution함수에 전달되는 lines배열은 N(1 ≦N≦ 2,000) 개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답 완료 시간 S와 처리시간 T가 공백으로 구분되어 있다.

• 응답 완료 시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.

• 처리시간 T는 0.1s,0.312s, 2s와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는s로 끝난다.

• 예를 들어, 로그 문자열2016-09-15 03:10:33.020 0.011s은2016년 9월 15일 오전 3시 10분 **33.010초**부터2016년 9월 15일 오전 3시 10분 **33.020초**까지**0.011초**동안 처리된 요청을 의미한다.(처리시간은 시작시간과 끝시간을 포함)

• 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은0.001 ≦ T ≦ 3.000이다.

• lines 배열은 응답완료시간S를 기준으로 오름차순 정렬되어 있다.

출력형식

• solution함수에서는 로그 데이터lines배열에 대해초당 최대 처리량을 리턴한다.

입출력 예

예제 1

• 입력: [
  2016-09-15 01:00:04.001 2.0s,
  2016-09-15 01:00:07.000 2s
  ]

• 출력: 1

예제 2

• 입력: [
  2016-09-15 01:00:04.002 2.0s,
  2016-09-15 01:00:07.000 2s
  ]

• 출력: 2

• 설명: 처리시간은 시작시간과 끝시간을포함하므로
  첫 번째 로그는01:00:02.003 ~ 01:00:04.002에서 2초 동안 처리되었으며,
  두 번째 로그는01:00:05.001 ~ 01:00:07.000에서 2초 동안 처리된다.
  따라서, 첫 번째 로그가 끝나는 시점과 두 번째 로그가 시작하는 시점의 구간인01:00:04.002 ~ 01:00:05.0011초 동안 최대 2개가 된다.

예제 3

• 입력: [
  2016-09-15 20:59:57.421 0.351s,
  2016-09-15 20:59:58.233 1.181s,
  2016-09-15 20:59:58.299 0.8s,
  2016-09-15 20:59:58.688 1.041s,
  2016-09-15 20:59:59.591 1.412s,
  2016-09-15 21:00:00.464 1.466s,
  2016-09-15 21:00:00.741 1.581s,
  2016-09-15 21:00:00.748 2.31s,
  2016-09-15 21:00:00.966 0.381s,
  2016-09-15 21:00:02.066 2.62s
  ]

• 출력: 7

• 설명: 아래 타임라인 그림에서 빨간색으로 표시된 1초 각 구간의 처리량을 구해보면(1)은 4개,(2)는 7개,(3)는 2개임을 알 수 있다. 따라서초당 최대 처리량은 7이 되며, 동일한 최대 처리량을 갖는 1초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.

  

2. 어떻게 풀까?

• 입력으로 주어진 응답 완료 시간과 처리 시간을 이용하여 응답 시작 시간을 구한다.

• 시작 시간, 완료 시간을 구간 시작으로 저장하여 1초동안 처리하는 데이터를 찾는다.

  • 구간에서 처리하고 있는 데이터는

    1. 응답 시작 시간이 구간에 걸쳐있는 경우

    2. 응답 완료 시간이 구간에 걸쳐있는 경우

    3. 응답 시작 시간 ~ 응답 완료 시간 사이에 구간이 포함되는 경우

• 가장 많은 데이터 처리량을 구한다.

3. 코드

테스트 코드

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

import org.junit.Test;

public class SolutionTest {

  @Test
  public void test1() {
    String[] lines = {
        "2016-09-15 01:00:04.001 2.0s",
        "2016-09-15 01:00:07.000 2s"
    };
    assertThat(new Solution().solution(lines), is(1));
  }

  @Test
  public void test2() {
    String[] lines = {
        "2016-09-15 01:00:04.002 2.0s",
        "2016-09-15 01:00:07.000 2s"
    };
    assertThat(new Solution().solution(lines), is(2));
  }

  @Test
  public void test3() {
    String[] lines = {
        "2016-09-15 20:59:57.421 0.351s",
        "2016-09-15 20:59:58.233 1.181s",
        "2016-09-15 20:59:58.299 0.8s",
        "2016-09-15 20:59:58.688 1.041s",
        "2016-09-15 20:59:59.591 1.412s",
        "2016-09-15 21:00:00.464 1.466s",
        "2016-09-15 21:00:00.741 1.581s",
        "2016-09-15 21:00:00.748 2.31s",
        "2016-09-15 21:00:00.966 0.381s",
        "2016-09-15 21:00:02.066 2.62s"
    };
    assertThat(new Solution().solution(lines), is(7));
  }
}

실제 코드

import java.util.ArrayList;
import java.util.List;

public class Solution {

  private List<Integer> starts;
  private List<Integer> startTimes;
  private List<Integer> endTimes;

  public Solution() {
    starts = new ArrayList<>();
    startTimes = new ArrayList<>();
    endTimes = new ArrayList<>();
  }

  public int solution(String[] lines) {
    timeToMilliseconds(lines, starts, startTimes, endTimes);
    int max = 0;

    for (int startSection : starts) {
      int endSection = startSection + 1000;
      max = Math.max(max, getProcessCount(startSection, endSection));
    }

    return max;
  }

  private int getProcessCount(int startSection, int endSection) {
    int count = 0;
    for (int i = 0; i < startTimes.size(); i++) {
      if (isPartOfSection(startSection, endSection, startTimes.get(i), endTimes.get(i))) {
        count++;
      }
    }
    return count;
  }

  private boolean isPartOfSection(int startSection, int endSection, int startTime, int endTime) {
    return (startTime >= startSection && startTime < endSection)
        || (endTime >= startSection && endTime < endSection)
        || (startTime <= startSection && endTime >= endSection);
  }

  private void timeToMilliseconds(String[] lines, List<Integer> starts, List<Integer> startTimes,
      List<Integer> endTimes) {
    for (String line : lines) {
      String[] log = line.split(" ");
      int endTime = getSeconds(log[1]);
      int processTime = (int) (Double.parseDouble(log[2].replace("s", "")) * 1000);
      int startTime = endTime - processTime + 1;
      startTimes.add(startTime);
      endTimes.add(endTime);
    }
    starts.addAll(startTimes);
    starts.addAll(endTimes);
  }

  private int getSeconds(String time) {
    String[] split = time.split(":");
    return (Integer.parseInt(split[0]) * 60 * 60 * 1000)
        + (Integer.parseInt(split[1]) * 60 * 1000)
        + (int) (Double.parseDouble(split[2]) * 1000);
  }
}

• timeToMilliseconds()에서 입력으로 주어진 lines를 통해 응답 시작 시간과 완료 시작을 구하고, 각 startTimes, endTimes에 저장한다. 그리고 구간 시작점 starts를 따로 만들어 저장한다.

  • lines에서 완료 시간과 처리시간을 추출하고, HH:mm:ss.sss로 주어진 완료 시간을 getSeconds()에서 밀리 초로 환산해서 List에 저장한다.

• starts에 저장된 구간 시작 지점을 반복문을 통해 구간을 만들고 getProcessCount()에서 구간 내에 처리량을 구한다.

4. 느낀 점

• "각 응답의 시작점과 끝점을 구간으로 잡아야겠다"라는 생각을 하기까지 시간이 좀 걸렸다. 위에 그림처럼 직접 그림을 그려서 정리를 하니까 그 생각이 들었다.

• "응답의 시작점과 끝점을 세트로 묶어야겠네?"라는 생각으로 처음에는 Entry가 필요하겠구나 생각했는데 Entry에 추가하는 메서드가 없어서 Map으로 구현하여 Key, Value -> 시작점, 끝점을 저장했다.

  • 근데 계속 틀려서 왜 틀리는지 생각을 해봤는데, Map의 Key값, 즉 시작점이 같아지는 경우가 있을 수 있는 걸 생각하지 못했다. 그러면 Map에 data를 추가하는 것이 아닌, 교체하는 것이 되기 때문에 적절한 자료구조를 사용하지 못한 것이라고 볼 수 있다.

  • 그래서 List로 다시 구현했다.

• 처음 시간을 계산할 때 LocalTime 클래스를 사용하려 했다. 근데 코드를 작성할수록 더 복잡해지는 것 같아서 시간을 밀리 초로 환산하는 메서드를 만들어서 해결했다.

• 처음에 최대 처리량을 max를 Integer.MIN\_VALUE로 초기화했는데, 계속 틀렸다. 당연하지만 첫 최대 처리량을 0으로 초기화했어야 했다.

• level2보다 level 3가 확실히 어려운데, 연습을 계속하면 할 만한 것 같기도 하다.

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. 문제

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. 문제

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 수준의 문제는 확실히 다 풀 수 있도록 해야겠다.