Dev 일기장

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가 확실히 어려운데, 연습을 계속하면 할 만한 것 같기도 하다.