문제

https://www.acmicpc.net/problem/2869


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class 달팽이는_올라가고_싶다 {
public static void main(String[] args) throws IOException {
String[] input = getInputData(System.in).split(" ");
int[] abv = convertStringArrayToIntegerArray(input);

System.out.println(solution(abv));
}

public static String getInputData(InputStream in) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(in))) {

return br.readLine();
}
}

private static int[] convertStringArrayToIntegerArray(String[] args) {
int[] array = new int[args.length];
int i = 0;

for (String str : args) {
array[i++] = Integer.parseInt(str);
}

return array;
}

public static int solution(int[] abv) {
return (abv[2] - abv[1] - 1) / (abv[0] - abv[1]) + 1;
}
}

흐름

  1. 달팽이는 하루에 A 만큼 올라가는데 자면서 B만큼 미끄러지므로 하루에 (A - B) 만큼 씩 올라가서 V미터 만큼 올라가면 된다.
  2. 하지만 꼭대기에 도달하면 미끄러지지 않는다고 하였으므로, 꼭대기(V) 에서 미끄러지는 만큼(B) 을 뺀 거리만큼만 올라가면 된다. (V - B)
  3. 그럼 수식은 (V - B) / (A / B)가 되고 int형은 소수점을 없애므로 나누어떨어지지 않으면 + 1을 하는데
  4. (V - B)에서 - 1을 먼저하고 무조건 1을 더한다.

(V - B - 1) / (A - B) + 1

  • V-B를 X, A-B를 y로 가정
  1. x/y가 나누어 떨어지는 경우
    1. x / y = d 일 때 (x-1)/y 는 반드시 d보다 작다.
    2. int형은 소수점 아래를 없애므로 x-1 /y = d - 1이 되고,
    3. +1을 하면 d가 된다.
  2. x/y가 나누어 떨어지지 않는 경우
    1. x / y = d + f 일 때 y를 양변에 곱하면
    2. x = y(d + f) 여기서 양변에 1을 빼면,
    3. x - 1 = y(d + f) - 1 여기서 y를 양변에 나누면
    4. (x - 1) / y = (d + f) -1 / y 이 된다.
    5. 이 때 1 / y 는 y >= 2 이고 int형은 소수점 아래를 없애버리므로 1 / y 는 없어진다.
      1. y >= 2 인 이유는 현재 x / y가 나누어 떨어지지 않는 경우임을 상정하고 있으므로 y가 1이면 나누어 떨어지기 때문에 y는 2보다 크게 된다.
    6. 그럼 (x - 1) / y = d + f 이 되고 +1을 하면,
    7. (x - 1) / y + 1 = d + f + 1 된다.

결과

결과


테스트 케이스

1
2
3
4
5
6
7
assertEquals(4, test.solution(new int[] {2,1,5}));
assertEquals(2, test.solution(new int[] {5,1,6}));
assertEquals(999999901, test.solution(new int[] {100,99,1000000000}));
assertEquals(1, test.solution(new int[] {5,0,5}));
assertEquals(4, test.solution(new int[] {3,2,6}));
assertEquals(2, test.solution(new int[] {100,1,101}));
assertEquals(3, test.solution(new int[] {3,1,6}));

참고 사이트

댓글 공유

문제

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


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
private static final int CAPITAL_A = 65;
private static final Character LAST_INIT_ALPHABET = 'Z';

public int[] solution(String msg) {
int[] answer = getDictionaryIndex(msg.toCharArray(), initIndexMap());

return answer;
}

private Map<String, Integer> initIndexMap() {
Map<String, Integer> indexMap = new HashMap<>();

Character start = CAPITAL_A;
int i = 1;

while (start <= LAST_INIT_ALPHABET) {

indexMap.put(String.valueOf(start), i);

++start;
++i;
}

return indexMap;
}

private int[] getDictionaryIndex(char[] charArray, Map<String, Integer> indexMap) {
int i = 0;
int arrayLength = charArray.length;
int lastIndex = indexMap.get(String.valueOf(LAST_INIT_ALPHABET));

List<Integer> answer = new ArrayList<>();

while (i < arrayLength) {
StringBuilder sb = new StringBuilder();

int value = 0;
int jump = 0;
for (int j = i; j < arrayLength; j++) {
sb.append(charArray[j]);

String key = sb.toString();
if (indexMap.containsKey(key)) {
value = indexMap.get(key);
jump++;

if (j +1 == arrayLength) {
answer.add(value);
i += jump;
}

continue;
}

answer.add(value);
i += jump;
break;
}

if (!indexMap.containsKey(sb.toString())) {
indexMap.put(sb.toString(), ++lastIndex);
}

sb.setLength(0);
}

return answer.stream().mapToInt(index -> index).toArray();
}

흐름

  1. A부터 Z를 Key로 하는 Map을 만든다.
  2. 압축 할 문자열의 길이만큼 반복한다.
  3. 돌면서 현재 문자가 Map에 key에 포함되는지 확인한다.
  4. 이미 포함되어 있으면(처음엔 A~Z) 해당 문자의 index를 뽑아내기 위해 value를 꺼내서 저장한다.
  5. 이번 문자는 포함되어 있으므로 그 다음 문자열의 index까지 점프하기 위해 jump 변수를 증가시킨다.
  6. 현재 문자가 문자열의 마지막 문자라면 더 이상 사전에서 검색 할 수 없으므로,
  7. 문자열의 index 즉, value를 List에 저장하고 i를 jump 만큼 더해서 문자열의 index를 증가시킨다.
  8. 이미 사전에 있는 문자이므로 continue해서 끝내지 않고 반복문을 올라가서 문자를 더한다.
    1. A가 포함되어 있으면 A 뒤문자인 B를 더해서 AB가 존재하는지 찾기 위해
  9. 사전에 포함되어 있지 않는다면(Map에 key로 존재하지 않는다면)
  10. 이전에 검색했던 문자의 index를 저장하고 i를 jump 시킨 후 반복문을 벗어난다.
  11. 그 후 사전에 존재 하지 않았던 문자를 사전에 등록, Map에 key, lastIndex에서 + 1해서 Map에 추가하고, 문자를 저장했던 StringBuilder를 초기화 시킨다.
  12. 문자열 모두 검색 할 때까지 반복한다.
  13. 사전에서 검색한 index를 저장한 List를 array로 변경한 후 return 한다.
  14. 끝.

결과

번호 속도
테스트 1 통과 (6.64ms, 53MB)
테스트 2 통과 (6.30ms, 52.9MB)
테스트 3 통과 (5.29ms, 50.3MB)
테스트 4 통과 (9.62ms, 53MB)
테스트 5 통과 (5.94ms, 51.1MB)
테스트 6 통과 (10.26ms, 52.8MB)
테스트 7 통과 (7.65ms, 51MB)
테스트 8 통과 (8.38ms, 52.8MB)
테스트 9 통과 (6.01ms, 52.5MB)
테스트 10 통과 (11.33ms, 53MB)
테스트 11 통과 (8.25ms, 51.6MB)
테스트 12 통과 (8.79ms, 51.3MB)
테스트 13 통과 (9.26ms, 53.6MB)
테스트 14 통과 (9.22ms, 51.5MB)
테스트 15 통과 (10.26ms, 53MB)
테스트 16 통과 (8.91ms, 53.5MB)
테스트 17 통과 (10.89ms, 53.2MB)
테스트 18 통과 (7.93ms, 53.2MB)
테스트 19 통과 (8.32ms, 53.1MB)
테스트 20 통과 (8.10ms, 50.8MB)

테스트 케이스

1
2
3
4
assertArrayEquals(new int[] {11, 1, 27, 15}, test.solution("KAKAO"));
assertArrayEquals(new int[] {20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34}, test.solution("TOBEORNOTTOBEORTOBEORNOT"));
assertArrayEquals(new int[] {1, 2, 27, 29, 28, 31, 30}, test.solution("ABABABABABABABAB"));
assertArrayEquals(new int[] {20, 8, 1, 20, 27, 29, 9, 19, 33, 31, 30, 28, 20, 33, 14, 15, 39, 19, 41, 43, 36, 9, 39, 46, 38, 47, 34, 19, 36, 52, 45, 40, 42, 35, 38, 48, 62, 54, 51, 61, 53, 55, 66, 57, 44, 59, 64, 32, 49, 60, 29, 52, 76, 37, 32, 71, 43, 70, 47, 75, 73, 80, 43, 79, 56, 72, 84, 61, 86, 68, 81, 90, 69, 92, 72, 85, 63, 96, 89, 87, 91, 83, 101, 94, 103, 65, 97, 106, 99, 108, 50, 74, 111, 77, 66, 98, 81, 70, 93, 118, 117, 88, 33, 122, 116, 58, 127, 62, 127, 78, 114, 123, 100, 133, 95, 112, 105, 104, 132, 145, 87, 134, 130, 129, 137, 131, 82, 79, 148, 151, 150, 144, 153, 159, 102, 135, 121, 156, 159, 125, 75, 162, 113, 158, 124, 109, 126, 149, 67, 142, 146, 166, 155, 158, 174, 171, 140, 119, 128, 175, 120, 138, 152, 161, 174, 181, 139, 154, 141, 187, 143, 176, 165, 172, 167, 191, 164, 182, 194, 184, 136, 170, 193, 147, 86}, test.solution("THATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITIS"));

여담

  • 코드의 퀄리티가 썩 마음에 들지 않는다.
  • 시간 날 때 리팩토링을 꼭 해야 할 듯 싶다.

댓글 공유

문제

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


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
private static final String[] ABCDEF = new String[] {"A","B","C","D","E","F"};
public String solution(int n, int t, int m, int p) {

int limit = t * m;
String speakString = make(n, limit);

char[] toChar = speakString.toCharArray();

StringBuilder answer = new StringBuilder();

int index = p - 1;
for (int i = 0; i < t; i++) {
answer.append(toChar[index]);
index += m;
}

return answer.toString();
}

public String make(int n, int limit) {
StringBuilder sb = new StringBuilder().append(0);

for (int i = 1; i < limit; i++) {
sb.append(changeDecimal(i, n));
}

return sb.toString();
}

public char[] changeDecimal(int currentNumber, int n) {
StringBuilder sb = new StringBuilder();
while(currentNumber > 0) {
int remain = currentNumber % n;
sb.append(remain >= 10 ? ABCDEF[remain-10] : remain);
currentNumber /= n;
}

return sb.reverse().toString().toCharArray();
}

흐름

  • 진법 n, 미리 구할 숫자의 갯수 t, 게임에 참가하는 인원 m, 튜브의 순서 p
  1. 미리 구할 숫자의 갯수와 참가 인원 수를 곱해서 구해야 할 수의 갯수를 구한다.
  2. 1부터 구해야 될 수까지 반복한다.
  3. 반복하면서 숫자를 진법으로 나눈 나머지를 구한다.
  4. 나머지가 10 이상이면 A, B, C … 으로 치환한다.
  5. 현재 수를 n 진법의 값만큼 나눈다.
  6. 작은 수부터 역순으로 저장되어야 하므로 reverse() 메서드로 역순으로 돌린다.
  7. 0부터 미리 구할 숫자 갯수만큼 반복하면서
  8. n진법으로 치환한 문자열에서 참가인원 숫자만큼 더하면서 숫자를 뽑아 저장한다.

결과

번호 속도
테스트 1 통과 (0.87ms, 50.6MB)
테스트 2 통과 (1.15ms, 50.5MB)
테스트 3 통과 (1.02ms, 52MB)
테스트 4 통과 (1.07ms, 52.1MB)
테스트 5 통과 (4.60ms, 52.6MB)
테스트 6 통과 (4.40ms, 52.2MB)
테스트 7 통과 (4.55ms, 53MB)
테스트 8 통과 (2.62ms, 52.3MB)
테스트 9 통과 (2.45ms, 52.6MB)
테스트 10 통과 (2.57ms, 52.3MB)
테스트 11 통과 (2.49ms, 52MB)
테스트 12 통과 (2.45ms, 52.7MB)
테스트 13 통과 (5.32ms, 50.3MB)
테스트 14 통과 (69.61ms, 77.9MB)
테스트 15 통과 (75.19ms, 75.8MB)
테스트 16 통과 (70.55ms, 78.1MB)
테스트 17 통과 (17.09ms, 53.3MB)
테스트 18 통과 (15.42ms, 52.7MB)
테스트 19 통과 (6.46ms, 52.6MB)
테스트 20 통과 (13.17ms, 53MB)
테스트 21 통과 (29.51ms, 58.7MB)
테스트 22 통과 (21.20ms, 56.5MB)
테스트 23 통과 (41.04ms, 64.1MB)
테스트 24 통과 (59.00ms, 77.4MB)
테스트 25 통과 (74.66ms, 80MB)
테스트 26 통과 (24.89ms, 54.3MB)

테스트 케이스

1
2
3
assertEquals("0111", test.solution(2,4,2,1));
assertEquals("02468ACE11111111", test.solution(16,16,2,1));
assertEquals("13579BDF01234567", test.solution(16,16,2,2));

참고사이트

댓글 공유

  • page 1 of 1

Junggu Ji

author.bio


author.job