프로그래머스: 땅따먹기

문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
int solution(int[][] land) {
    for (int i = land.length - 2; i >= 0; i--) {
        int rowIndex = i + 1;
        land[i][0] += max(land[rowIndex][1], max(land[rowIndex][2], land[rowIndex][3]));
        land[i][1] += max(land[rowIndex][0], max(land[rowIndex][2], land[rowIndex][3]));
        land[i][2] += max(land[rowIndex][0], max(land[rowIndex][1], land[rowIndex][3]));
        land[i][3] += max(land[rowIndex][0], max(land[rowIndex][1], land[rowIndex][2]));
    }

    int answer = max(land[0][0], max(land[0][1], max(land[0][2], land[0][3])));
    return answer;
}

흐름

  1. 마지막 행 전행 부터 반복문을 시작해서 i가 0이 될 때까지 반복한다.
  2. i행의 각 인덱스에는 자기 자신의 열을 제외한 이전 행의 값 중 가장 큰 값과 자기 자신의 값을 더한 값을 저장한다.
  3. 위 과정을 반복하면 0번째 행들의 index에 계산된 값들이 할당되어 있을 테니
  4. 0 번째 행 중에서 가장 큰 값을 return한다.
  5. 끝

결과

정확성

번호 속도
테스트 1 통과 (1.05ms, 51.1MB)
테스트 2 통과 (1.16ms, 52.7MB)
테스트 3 통과 (1.16ms, 50.8MB)
테스트 4 통과 (1.18ms, 53MB)
테스트 5 통과 (1.18ms, 52.7MB)
테스트 6 통과 (1.14ms, 52.9MB)
테스트 7 통과 (1.18ms, 51.4MB)
테스트 8 통과 (1.13ms, 52.7MB)
테스트 9 통과 (1.25ms, 53.3MB)
테스트 10 통과 (1.21ms, 50.7MB)
테스트 11 통과 (1.18ms, 52.4MB)
테스트 12 통과 (4.25ms, 52.5MB)
테스트 13 통과 (1.19ms, 53.2MB)
테스트 14 통과 (1.16ms, 53.1MB)
테스트 15 통과 (1.19ms, 51MB)
테스트 16 통과 (1.16ms, 52.5MB)
테스트 17 통과 (1.14ms, 55.3MB)
테스트 18 통과 (1.16ms, 52.2MB)

효율성

번호 속도
테스트 1 통과 (28.10ms, 94.3MB)
테스트 2 통과 (28.01ms, 95.7MB)
테스트 3 통과 (25.28ms, 97.6MB)
테스트 4 통과 (25.93ms, 101MB)

테스트 케이스

1
2
3
4
5
6
7
8
assertEquals(16, test.solution(new int[][] {{1,2,3,5},{5,6,7,8},{4,3,2,1}}));
assertEquals(20, test.solution(new int[][] {{4, 3, 2, 1}, {2, 2, 2, 1}, {6, 6, 6, 4}, {8, 7, 6, 5}}));
assertEquals(115, test.solution(new int[][] {{1, 2, 3, 5}, {5, 6, 7, 8}, {4, 3, 2, 1}, {100, 0, 9, 8}}));
assertEquals(33, test.solution(new int[][] {{1, 2, 3, 5}, {10, 11, 12, 11}, {16, 15, 13, 13}}));
assertEquals(409, test.solution(new int[][] {{1, 100, 15, 3}, {1, 2, 3, 4}, {100, 99, 98, 97}, {97, 98, 99, 100}, {4, 3, 2, 1}, {100, 100, 100, 100}, {1, 1, 1, 1}}));
assertEquals(16, test.solution(new int[][] {{1, 2, 3, 4}, {5, 6, 7, 9}, {4, 3, 2, 1}}));
assertEquals(125, test.solution(new int[][] {{9, 5, 2, 3}, {9, 8, 6, 7}, {8, 9, 7, 1}, {100, 9, 8, 1}}));
assertEquals(20, test.solution(new int[][] {{4, 3, 2, 1}, {2, 2, 2, 1}, {6, 6, 6, 4}, {8, 7, 6, 5}}));

댓글 공유

프로그래머스: 피보나치 수

문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static final int DIVIDE_NUMBER = 1234567;

public int solution(int n) {
    int[] cache = new int[n+1];

    cache[1] = 1;

    for (int i = 2; i < n+1; i++) {
        cache[i] = ((cache[i-1]) % DIVIDE_NUMBER + (cache[i-2]) % DIVIDE_NUMBER) % DIVIDE_NUMBER;
    }

    int answer = cache[n];
    return answer;
}

흐름

  1. n+1 크기 배열을 생성하는데 이 때 이번 문제에서 n은 1 <= n <= 100,000 이하이다.
  2. n이 1 일땐 1을 return 해야하므로 배열 1 번째엔 1을 할당 해놓아야 한다.
  3. 2부터 n + 1 까지 반복하면서 피보나치 수열 계산하는 것 처럼 i - 1, i - 2 배열에 저장된 값을 더하는데
  4. 문제에서 1234567을 나눈 나머지 값을 return 하라고 하였으므로 % 1234567을 해준다.
  5. cache 배열에서 n 번째에 있는 값을 return하면 끝

결과

번호 속도
테스트 1 통과 (0.85ms, 52.8MB)
테스트 2 통과 (0.80ms, 52.2MB)
테스트 3 통과 (0.78ms, 51.3MB)
테스트 4 통과 (0.81ms, 53.1MB)
테스트 5 통과 (0.84ms, 52.6MB)
테스트 6 통과 (0.85ms, 50.3MB)
테스트 7 통과 (0.95ms, 52.4MB)
테스트 8 통과 (0.86ms, 50.5MB)
테스트 9 통과 (0.86ms, 52MB)
테스트 10 통과 (0.89ms, 51.4MB)
테스트 11 통과 (0.84ms, 51MB)
테스트 12 통과 (0.86ms, 52.4MB)
테스트 13 통과 (3.99ms, 52.7MB)
테스트 14 통과 (3.98ms, 50.4MB)

테스트 케이스

1
2
3
4
5
6
7
assertEquals(2, test.solution(3));
assertEquals(5, test.solution(5));
assertEquals(987, test.solution(16));
assertEquals(256379, test.solution(1234156));
assertEquals(473509, test.solution(100001));
assertEquals(1168141, test.solution(100000));
assertEquals(547662, test.solution(124126347));

참고 사이트

댓글 공유

프로그래머스: 가장 큰 정사각형 찾기

문제

https://programmers.co.kr/learn/courses/18/lessons/1879

코드

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
public int solution(int[][] board) {

    if (board.length < 2 || board[0].length < 2) {
        return smallSquare(board);
    }

    int answer = nomalSquare(board);
    return answer * answer;
}

private int smallSquare(int[][] board) {
    int size = 0;
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (board[i][j] == 1) {
                size = 1;
                break;
            }
        }

        if (size == 1) {
            break;
        }
    }

    return size;
}

private int nomalSquare(int[][] board) {
    int answer = 0;

    int min = Integer.MAX_VALUE;
    for (int i = 1; i < board.length; i++) {
        for (int j = 1; j < board[0].length; j++) {
            if (board[i][j] == 0) {
                continue;
            }

            board[i][j] = Math.min(board[i-1][j-1], Math.min(board[i-1][j], board[i][j-1])) + 1;

            if (board[i][j] > answer) {
                answer = board[i][j];
            }
        }
    }

    return answer;
}

흐름

  1. 배열의 크기가 2보다 작은 경우엔 크기가 1인 정사각형 밖에 존재 할 수 없으므로, 배열의 크키가 2 이하인 배열에 1이 들어있는지 확인
  2. 배열을 [1,1] 부터 반복
  3. 현재 위치의 값이 0인 경우엔 절대 정사각형 일 수 없으므로 더 이상 돌지 않고 continue
  4. 현재 위치(1,1)의 좌상(0,0)과 상(0,1) 좌(1,0)의 값들중 최소값을 구함
  5. 구한 최소값에 1을 더해서 현재 위치에 할당
  6. 구한 최소값이 현재 가장 큰 정사각형의 크기 보다 크면 정사각형의 크기를 구한 최소값으로 변경
  7. 반복
  8. 끝

흐름 이미지 설명

사각형

결과

정확성 테스트

번호 속도
테스트 1 통과 (0.86ms, 52.4MB)
테스트 2 통과 (0.77ms, 52.2MB)
테스트 3 통과 (0.83ms, 52.6MB)
테스트 4 통과 (0.75ms, 50.4MB)
테스트 5 통과 (0.72ms, 52.8MB)
테스트 6 통과 (0.83ms, 52.7MB)
테스트 7 통과 (0.79ms, 50.4MB)
테스트 8 통과 (0.83ms, 54.1MB)
테스트 9 통과 (0.79ms, 52.4MB)
테스트 10 통과 (0.83ms, 52.3MB)
테스트 11 통과 (0.75ms, 52.2MB)
테스트 12 통과 (0.79ms, 52.3MB)
테스트 13 통과 (0.76ms, 52.1MB)
테스트 14 통과 (0.83ms, 49.9MB)
테스트 15 통과 (0.75ms, 50.5MB)
테스트 16 통과 (0.91ms, 50MB)
테스트 17 통과 (0.83ms, 52.4MB)
테스트 18 통과 (0.92ms, 52.3MB)
테스트 19 통과 (1.06ms, 52MB)

효율성 테스트

번호 속도
테스트 1 통과 (24.74ms, 97.5MB)
테스트 2 통과 (25.24ms, 99.6MB)
테스트 3 통과 (26.48ms, 99.8MB)

테스트 케이스

1
2
3
assertEquals(9, test.solution(new int[][]{{0,1,1,1} ,{1,1,1,1},{1,1,1,1},{0,0,1,0}}));
assertEquals(4, test.solution(new int[][]{{0,0,1,1} ,{1,1,1,1}}));
assertEquals(1, test.solution(new int[][]{{0,0,1,1}}));

참고 사이트

댓글 공유

  • page 1 of 1

Junggu Ji

author.bio


author.job