프로그래머스: 괄호 변환

문제

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

코드

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
private static final Character LEFT = '(';
private static final Character RIGHT = ')';

public String solution(String p) {
    String answer = getDivide(p);
    return answer;
}

private String getDivide(String w) {
    if (w.isEmpty()) {
        return w;
    }

    String[] uAndv = getUAndV(w);
    String u = uAndv[0];
    String v = uAndv[1];

    if (!isPerfectBracket(u)) {
        return createPerfectBracket(u, v);
    }

    return u + getDivide(v);
}

private String[] getUAndV(String w) {
    StringBuilder sb = new StringBuilder();
    char[] tochar = w.toCharArray();
    Stack<Character> stack = new Stack<>();
    char popChar = (tochar[0] == LEFT) ? RIGHT : LEFT;

    for (char ch : tochar) {
        if (ch == popChar) {
            stack.pop();
            sb.append(popChar);
        } else {
            sb.append(stack.push(ch));
        }

        if (stack.isEmpty()) {
            break;
        }
    }

    String[] uAndv = new String[2];
    uAndv[0] = sb.toString();
    uAndv[1] = new String(tochar, uAndv[0].length(), tochar.length - uAndv[0].length());

    return uAndv;
}

private boolean isPerfectBracket(String u) {
    int sum = 0;
    for (int i = 0; i < u.length(); i++) {
        sum += (u.charAt(i) == LEFT) ? +1 : -1;

        if (sum < 0) {
            break;
        }
    }

    return sum == 0;
}

private String createPerfectBracket(String u, String v) {
    StringBuilder str = new StringBuilder();

    str.append(LEFT);
    str.append(getDivide(v));
    str.append(RIGHT);

    char[] newU = u.substring(1, u.length() -1).toCharArray();
    str.append(getChange(newU));

    return str.toString();
}

private char[] getChange(char[] newU) {
    for (int i = 0; i < newU.length; i++) {
        newU[i] = (newU[i] == LEFT) ? RIGHT : LEFT;
    }

    return newU;
}

흐름

  • 문제에 있는 그대로 작성하면 됨
  1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
  2. 문자열 w를 두 “균형잡힌 괄호 문자열” u, v로 분리합니다.
    단, u는 “균형잡힌 괄호 문자열”로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
  3. 문자열 u가 “올바른 괄호 문자열” 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
    1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
  4. 문자열 u가 “올바른 괄호 문자열”이 아니라면 아래 과정을 수행합니다.
    1. 빈 문자열에 첫 번째 문자로 ‘(‘를 붙입니다.
    2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
    3. ‘)’를 다시 붙입니다.
    4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
    5. 생성된 문자열을 반환합니다.

결과

번호 속도
테스트 1 통과 (32.01ms, 55.5MB)
테스트 2 통과 (1.42ms, 52.3MB)
테스트 3 통과 (30.81ms, 55.3MB)
테스트 4 통과 (30.93ms, 52.9MB)
테스트 5 통과 (30.16ms, 55.5MB)
테스트 6 통과 (29.55ms, 55.3MB)
테스트 7 통과 (35.55ms, 53MB)
테스트 8 통과 (29.41ms, 55.2MB)
테스트 9 통과 (28.63ms, 53.6MB)
테스트 10 통과 (30.95ms, 54.9MB)
테스트 11 통과 (30.81ms, 55.9MB)
테스트 12 통과 (28.73ms, 55.3MB)
테스트 13 통과 (30.50ms, 55.7MB)
테스트 14 통과 (38.62ms, 53.5MB)
테스트 15 통과 (31.72ms, 53.5MB)
테스트 16 통과 (31.20ms, 55MB)
테스트 17 통과 (30.63ms, 55.2MB)
테스트 18 통과 (33.95ms, 55.4MB)
테스트 19 통과 (31.25ms, 53.6MB)
테스트 20 통과 (33.02ms, 55.5MB)
테스트 21 통과 (33.70ms, 53.5MB)
테스트 22 통과 (33.13ms, 53.5MB)
테스트 23 통과 (32.43ms, 53MB)
테스트 24 통과 (31.24ms, 55.9MB)
테스트 25 통과 (33.63ms, 56MB)

테스트 케이스

1
2
3
4
5
6
7
8
9
assertEquals("(()())()", test.solution("(()())()"));
assertEquals("()", test.solution(")("));
assertEquals("()(())()", test.solution("()))((()"));
assertEquals("(((())))", test.solution(")()()()("));
assertEquals("()()((()))", test.solution("))()))(((("));
assertEquals("()", test.solution("()"));
assertEquals("()()()()()()((()))", test.solution("()()()()()()((()))"));
assertEquals("((((())())))()(())", test.solution("((((())()))))))((("));
assertEquals("(((()())())())((()))", test.solution("))))((((((()())()))("));

댓글 공유

프로그래머스: 탑

문제

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

코드

본인의 코드가 아닌 해당 문제 최다 좋아요를 받은 코드

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
public int[] solution(int[] heights) {
    Stack<Tower> st = new Stack<>();
    int[] answer = new int[heights.length];

    for (int i = 0; i < heights.length; i++) {
        Tower tower = new Tower(i + 1, heights[i]);
        int receiveIdx = 0;

        while (!st.isEmpty()) {
            Tower top = st.peek();

            if (top.height > tower.height) {
                receiveIdx = top.idx;
                break;
            }

            st.pop();
        }

        st.push(tower);
        answer[i] = receiveIdx;
    }

    return answer;
}

class Tower {
    int idx;
    int height;

    public Tower(int idx, int height) {
        this.idx = idx;
        this.height = height;
    }
}

본인의 코드가 아닌 해당 문제 최다 좋아요를 받은 코드

흐름

  1. 탑의 index와 높이를 저장 할 Tower class 생성
  2. 탑의 개수만큼 반복
  3. 1 번쨰부터 시작되야하므로 현재 index에서 +1 한 index와 현재 높이를 갖는 tower를 생성
  4. tower가 저장된 stack이 비었는지 체크
  5. 비어 있지 않다면 stack의 맨 위를 가져와서 현재 tower의 높이와 비교함
  6. stack에 저장된 stack이 더 크다면 현재 타워에 전파를 받을 타워이므로 index를 receiveIdx 변수에 할당
  7. 크지 않다면 stack에 저장된 tower를 pop함
  8. stack에 현재 tower를 push
  9. answer에 아까 저장한 receiveIdx를 저장
  10. answer return
  11. 끝

결과

번호 속도
테스트 1 통과 (1.89ms, 50.7MB)
테스트 2 통과 (1.84ms, 52.6MB)
테스트 3 통과 (1.96ms, 52.3MB)
테스트 4 통과 (2.04ms, 52.5MB)
테스트 5 통과 (2.02ms, 50.8MB)
테스트 6 통과 (2.28ms, 52.7MB)
테스트 7 통과 (1.78ms, 52.6MB)
테스트 8 통과 (2.06ms, 52.1MB)

테스트 케이스

1
2
3
assertArrayEquals(new int[] {0,0,2,2,4}, test.solution(new int[] {6,9,5,7,4}));
assertArrayEquals(new int[] {0,0,0,3,3,3,6}, test.solution(new int[] {3,9,9,3,5,7,2}));
assertArrayEquals(new int[] {0,0,2,0,0,5,6}, test.solution(new int[] {1,5,3,6,7,6,5}));

댓글 공유

프로그래머스: 쇠막대기

문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int solution(String arrangement) {
    char[] ch = arrangement.toCharArray();

    int answer = 0;
    char pre = 0;
    Stack<Character> stack = new Stack<Character>();
    for (char c : ch) {
        if (c == '(') {
            stack.push(c);
        } else {
            stack.pop();
            if (pre == c) {
                answer += 1;
            } else {
                answer += stack.size();
            }
        }

        pre  = c;
    }

    return answer;
}

흐름

  1. 문자열을 char array로 변경
  2. char array를 반복하면서 문자가 ‘(‘ 인지 비교
  3. 맞으면 새 막대기가 시작되야 하므로 stack에 push 함
  4. 아니라면 레이저를 발사해서 stack을 잘라야 하므로 pop 하는데
  5. 이전 pop한 문자가 똑같이 ‘)’ 이라면 하나만 더 짤린 것이므로 +1 만하고
  6. 이전 문자가 ‘)’이 아니라면 stack의 크기가 막대의 개수 이므로 stack size만큼 더함
  7. 막대를 하나만 추가할 지 판단하기 위해 현재 문자를 저장함
  8. 문자열을 모두 반복 하면 끝

결과

번호 속도
테스트 1 통과 (19.66ms, 51.2MB)
테스트 2 통과 (1.24ms, 53MB)
테스트 3 통과 (19.95ms, 51MB)
테스트 4 통과 (2.78ms, 53.1MB)
테스트 5 통과 (4.04ms, 53MB)
테스트 6 통과 (3.95ms, 52.8MB)
테스트 7 통과 (14.81ms, 52.5MB)
테스트 8 통과 (16.84ms, 52.6MB)
테스트 9 통과 (17.09ms, 52.8MB)
테스트 10 통과 (16.32ms, 52.6MB)
테스트 11 통과 (13.59ms, 52.2MB)
테스트 12 통과 (14.53ms, 50.6MB)
테스트 13 통과 (15.35ms, 52MB)
테스트 14 통과 (17.90ms, 50.4MB)
테스트 15 통과 (18.95ms, 52.3MB)
테스트 16 통과 (20.62ms, 50.7MB)
테스트 17 통과 (20.66ms, 53.1MB)
테스트 18 통과 (18.49ms, 52.8MB)
테스트 19 통과 (19.85ms, 53MB)
테스트 20 통과 (18.93ms, 52.5MB)

테스트 케이스

1
2
assertEquals(17, test.solution("()(((()())(())()))(())"));
assertEquals(18, test.solution("(((((((((())))))))))"));

댓글 공유

프로그래머스: 타겟넘버

문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int solution(int[] numbers, int target) {
    int answer = dfs(numbers, target, 0, 0);
    return answer;
}

private int dfs(int[] numbers, int target, int depth, int sum) {
    if (depth == numbers.length) {
        return sum == target ? 1 : 0;
    }

    int left = dfs(numbers, target, depth + 1, sum + numbers[depth]);
    int right = dfs(numbers, target, depth + 1, sum - numbers[depth]);

    return left + right;
}

흐름

  • DFS 알고리즘 (재귀) 으로 해결
  • array index를 depth로 치고 모든 경우의 수를 탐색
  1. 0 번째 인덱스부터 시작
  2. depth가 array length와 같으면 제일 깊은 곳 까지 모두 탐색한 것이므로
  3. 합이 target과 같은 지 판단해서 같으면 1, 다르면 0을 return
  4. depth가 length와 다르면, 더 깊이 들어가야 하므로 dfs() 메서드를 depth + 1 하고 해당 깊이 까진 더 한 값을 파라미터로 넘김
  5. 2번부터 다시 반복
  6. 끝

마지막 return 부연 설명

1
2
3
if (depth == numbers.length) {
    return sum == target ? 1 : 0;
}

트리

  1. 맨 아래에서 맨 왼쪽 1+1+1+1+1은 3이 아니므로 0
  2. 그 옆 1+1+1+1-1은 3이므로 1 return
  3. 그럼 그 윗 노드인 1+1+1+1은 1
  4. 다음 탐색 순서인 1+1+1-1+1은 3이므로 1 return
  5. 1+1+1-1-1 = 1 이므로 0 return
  6. 이들의 부모 노드인 1+1+1-1은 1
  7. 그 위 부모 노드는 1 + 1 이므로 2가 됨
  8. 이런 식으로 마지막 까지 올라가면 결국 +1에선 4, -1 에선 1 되서 정답인 5를 return하게 되고
  9. 실제로 양수로 시작하는 부분에선 4개의 경우가 3이 return 되고, 음수로 시작하는 경우에는 1이 return 되므로 정답임을 알 수 있다.

결과

번호 속도
테스트 1 통과 (6.69ms, 54.4MB)
테스트 2 통과 (6.56ms, 52.9MB)
테스트 3 통과 (0.97ms, 52.8MB)
테스트 4 통과 (1.26ms, 50.9MB)
테스트 5 통과 (1.75ms, 50.1MB)
테스트 6 통과 (1.00ms, 52.3MB)
테스트 7 통과 (0.93ms, 52.5MB)
테스트 8 통과 (1.44ms, 52.6MB)

테스트 케이스

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

참고 사이트

댓글 공유

프로그래머스: 카카오 프렌즈 컬러링북

문제

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

코드

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
public int[] solution(int m, int n, int[][] picture) {
    int numberOfArea = 0;
    int maxSizeOfOneArea = 0;

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

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {

            if (picture[i][j] == 0 || isPassedArea[i][j]) {
                continue;
            }

            int areaRange = breadthFirstSearch(i, j, picture, isPassedArea);
            maxSizeOfOneArea = (maxSizeOfOneArea < areaRange) ? areaRange : maxSizeOfOneArea;
            ++numberOfArea;
        }
    }

    int[] answer = new int[2];
    answer[0] = numberOfArea;
    answer[1] = maxSizeOfOneArea;

    return answer;
}

private int breadthFirstSearch(int x, int y, int[][] picture, boolean[][] isPassedArea) {
    final int[] xAround = new int[]{1, -1, 0, 0};
    final int[] yAround = new int[]{0, 0, 1, -1};

    int areaRange = 1;

    Queue<Position> queue = new LinkedList<Position>();

    setPassedArea(isPassedArea, queue, x, y);

    while (!queue.isEmpty()) {
        Position currentPosition = queue.poll();

        for (int i = 0; i < xAround.length; i++) {
            int moveX = xAround[i] + currentPosition.x;
            int moveY = yAround[i] + currentPosition.y;

            if (!isSameAreaValidation(moveX, moveY, picture, isPassedArea, currentPosition)) {
                continue;
            }

            setPassedArea(isPassedArea, queue, moveX, moveY);
            ++areaRange;
        }
    }

    return areaRange;
}

private boolean isSameAreaValidation(int moveX, int moveY, int[][] picture, boolean[][] isPassedArea, Position currentPosition) {
    if (isOutOfPicture(moveX, moveY, picture)) {
        return false;
    }

    if (picture[moveX][moveY] == 0) {
        return false;
    }

    if (isPassedArea[moveX][moveY]) {
        return false;
    }

    if (picture[currentPosition.x][currentPosition.y] != picture[moveX][moveY]) {
        return false;
    }

    return true;
}

private boolean isOutOfPicture(int moveX, int moveY, int[][] picture) {
    if (moveX < 0 || moveY < 0) {
        return true;
    }

    if (picture.length <= moveX || picture[0].length <= moveY) {
        return true;
    }

    return false;
}

private void setPassedArea(boolean[][] isPassedArea, Queue<Position> queue, int x, int y) {
    isPassedArea[x][y] = true;
    queue.offer(new Position(x, y));
}

class Position {
    private int x = 0;
    private int y = 0;

    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

흐름

  1. 이미 지나온 배열인지 확인하기 위해 picture array와 똑같은 크기의 boolean array를 만듦
  2. 2차원 배열 크기만큼 돌면서 picture[i][j] value가 0이거나 이미 지나온 길이면 찾아갈 필요가 없으므로 continute 해서 길을 찾지 않음
  3. 아니면 좌표 x,y를 저장할 class를 담는 Queue를 생성함
  4. queue에 현재 좌표를 저장하고 boolean array[x][y]를 true로 할당
  5. queue에 있는 값을 하나씩 꺼내면서 queue가 전부 비워질 때까지 반복
  6. queue에서 꺼낸 현재 좌표에서 상하 좌우를 비교해서 같은지 판단해야 하므로 현재 좌표에서 x -1 , +1, y +1, -1 씩 돌아가면서 판단할 좌표를 구함
  7. 구한 좌표가 validation을 통과하면 4번과 마찬가지로 좌표를 queue에 저장하고 true로 변경
    1. 구한 좌표 x, y가 array 범위를 넘어가진 않는 지
    2. 구한 좌표의 value가 0이 아닌 값 인지
    3. 구한 좌표가 이미 지나간 길이 아닌지
    4. 구한 좌표의 value가 현재 좌표의 value와 같은 지
    5. 위 4가지를 모두 통과해야 validation 통과
  8. 현재 영역의 크기를 증가시킴
  9. queue가 전부 비워지면 영역의 크기를 return해서 이전에 구한 영역의 크기와 비교해서 큰 값을 저장
  10. 영역 개수를 증가시킴
  11. 끝

결과

결과

테스트 케이스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int[][] picture = new int[][] {{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}};
assertArrayEquals(new int[] {4 , 5}, test.solution(6, 4, picture));

int[][] picture1 = new int[][] {{0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}};
assertArrayEquals(new int[] {0 , 0}, test.solution(5, 5, picture1));

int[][] picture2 = new int[][] {{1, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 1}};
assertArrayEquals(new int[] {3 , 1}, test.solution(5, 5, picture2));

int[][] picture3 = new int[][] {{1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}};
assertArrayEquals(new int[] {1 , 25}, test.solution(5, 5, picture3));

int[][] picture4 = new int[][] {{1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 100, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}};
assertArrayEquals(new int[] {2 , 24}, test.solution(5, 5, picture4));

int[][] picture5 = new int[][] {{1, 1, 1, 0}, {1, 1, 1, 0}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}};
assertArrayEquals(new int[] {2 , 6}, test.solution(6, 4, picture5));

int[][] picture6 = new int[][] {{0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0}, {0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0}, {0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 0}, {0, 1, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 0}, {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0}, {0, 1, 3, 3, 3, 1, 1, 1, 1, 1, 1, 3, 3, 3, 1, 0}, {0, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 0}, {0, 0, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 0}, {0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0}};
assertArrayEquals(new int[] {12 , 120}, test.solution(13, 16, picture6));

참고 사이트

댓글 공유

백준 11047번: 동전 0

문제

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

코드

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
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String coinAndMoney = br.readLine();

    String[] coinAndMoneyArray = coinAndMoney.split(" ");

    int coinAmount = Integer.parseInt(coinAndMoneyArray[0]);
    long money = Long.parseLong(coinAndMoneyArray[1]);

    long[] coinCategory = getCoincategory(coinAmount, br);

    long answer = solution(coinAmount, money, coinCategory);

    System.out.println(answer);
}

public static long[] getCoincategory(int coinAmount, BufferedReader br) throws IOException {
    long[] result = new long[coinAmount];
    for (int i = 0; i < coinAmount; i++) {

        result[i] = Integer.parseInt(br.readLine());
    }

    return result;
}

public static long solution(int n, long money, long[] array) {
    long answer = 0;

    for (int i = n - 1; i >= 0; i--) {
        if (array[i] > money) {
            continue;
        }

        answer += (money / array[i]);
        money %= array[i];

        if (money == 0) {
            break;
        }
    }

    return answer;
}

흐름

  1. 돈의 종류 만큼 돌면서 큰 수 부터 가지고 있는 돈을 나눔
  2. 돈의 가치가 더 큰 경우엔 나눌 수 없으므로 continue
  3. 돈으로 갖고 있는 돈을 나눈 값을 더하고 남은 값은 다시 나눠야 하므로 money에 다시 저장함
  4. momeny가 0이 되면 나눌 돈이 없는 것이므로 사용한 돈 갯수 return
  5. 끝

결과

결과

테스트 케이스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
long[] array = new long[] {1,5,10,50,100,500,1000,5000,10000,50000};
assertEquals(6, test.solution(10, 4200, array));
assertEquals(12, test.solution(10, 4790, array));
assertEquals(1, test.solution(10, 50000, array));
assertEquals(2000, test.solution(10, 100000000, array));

array = new long[] {1};
assertEquals(2, test.solution(1, 2, array));
assertEquals(1, test.solution(1, 1, array));
assertEquals(100000000, test.solution(1, 100000000, array));

array = new long[] {1, 5};
assertEquals(1, test.solution(2, 5, array));

array = new long[] {1, 3};
assertEquals(2, test.solution(2, 4, array));

array = new long[] {1, 100};
assertEquals(1, test.solution(2, 100, array));

array = new long[] {5000};
assertEquals(1, test.solution(1, 5000, array));
  • 나머지는 입력 값 처리이고 solution 메서드가 주요 로직이므로 solution 메서드를 테스트
  • 이렇게 테스트 할 경우 입력처리 때문에 에러가 발생 할 수 있으니 꼭 java application으로 함께 테스트 해볼 것

댓글 공유

프로그래머스: 소수 찾기(완전 탐색)

문제

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

코드

  • 순열을 이용한 완전탐색으로 해결
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
public int solution(String numbers) {
    char[] tochar = numbers.toCharArray();

    int numbersLength = tochar.length;

    Set<Integer> numberSet = new HashSet<Integer>();
    for (int i = 1; i <= numbersLength; i++) {
        perm(tochar, 0, i, numberSet);
    }

    int answer = getPrimeCount(numberSet);

    return answer;
}

private void perm(char[] array, int depth, int length, Set<Integer> numberSet) {
    if (depth == length) {

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; i++) {
            sb.append(array[i]);
        }

        int number = Integer.parseInt(sb.toString());
        if (number > 1) {
            numberSet.add(number);
        }

        return;
    }

    for (int i = depth; i < array.length; i++) {
        swap(array, i, depth);
        perm(array, depth + 1, length, numberSet);
        swap(array, i, depth);
    }
}

private void swap(char[] arrary, int i, int j) {
    char temp = arrary[i];
    arrary[i] = arrary[j];
    arrary[j] = temp;
}

private int getPrimeCount(Set<Integer> numberSet) {
    int result = 0;
    for (int i : numberSet) {
        boolean isPrime = true;

        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }

        if (isPrime) {
            ++result;
        }
    }

    return result;
}

흐름

  1. [1,2,3] 배열일 경우 3 자리 수 까지 나타날 수 있으므로, numbers의 길이 만큼 반복하면서 순열을 만듬
  2. perm() 메서드를 재귀로 돌면서 깊이 만큼 index를 스위칭하면서 순열을 만듬
    • ex) [1,2,3] 인 경우, 0번째와 0번째를 스왑하여 123이 되고 그 이후엔 0번째와 1번째를 스왑해서 213, 그 이후엔 0과 2를 스왑해서 321 … 이런 식으로 진행된다
  3. 돌다가 깊이랑 이번에 만들 숫자의 길이가 같으면 중복되지 않게 Set에 저장하는데 1 이하인 경우엔 소수가 아니므로 저장하지 않음
  4. 다시 swap() 해서 배열 index를 원상복귀 시킴
  5. 반복해서 모든 순열을 만든 후 해당 Set에 저장된 수들이 소수 인지 판별해서 소수면 카운트 증가시킴
  6. 끝

결과

번호 속도
테스트 1 통과 (1.06ms, 50.3MB)
테스트 2 통과 (9.99ms, 53MB)
테스트 3 통과 (0.83ms, 52.1MB)
테스트 4 통과 (7.08ms, 52.6MB)
테스트 5 통과 (23.43ms, 56MB)
테스트 6 통과 (0.91ms, 52.6MB)
테스트 7 통과 (1.13ms, 51.9MB)
테스트 8 통과 (18.16ms, 55.9MB)
테스트 9 통과 (0.96ms, 49.9MB)
테스트 10 통과 (10.37ms, 52.9MB)
테스트 11 통과 (2.51ms, 51.5MB)
테스트 12 통과 (2.16ms, 52MB)

테스트 케이스

1
2
3
4
5
6
assertEquals(3, test.solution("17"));
assertEquals(2, test.solution("011"));
assertEquals(1, test.solution("2"));
assertEquals(12, test.solution("7843"));
assertEquals(0, test.solution("9999999"));
assertEquals(1336, test.solution("1276543"));

참고 사이트

댓글 공유

백준 1152번: 단어의 개수

문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static long solution(String args) {
    char[] tochar = args.trim().toCharArray();

    long answer = 0;
    if (tochar.length == 0) {
        return answer;
    }

    for (char ch : tochar) {
        if (ch == ' ') {
            ++answer;
        }
    }

    return answer + 1;
}

흐름

  1. 문자열 앞 뒤로 공백이 존재 할 수 있으므로 trim()
  2. 공백만 있는 문자열인 경우 0 return
  3. char array로 변환된 문자열을 돌면서 공백인 경우 count 증가
  4. 공백을 기준으로 단어가 만들어졌으니 공백 개수 + 1 return
    • ex) hello, wolrd! = 공백 1개, 문자 2개
  5. 끝

결과

결과

테스트 케이스

1
2
3
4
5
assertEquals(6, test.solution("The Curious Case of Benjamin Button"));
assertEquals(3, test.solution(" Mazatneunde Wae Teullyeoyo"));
assertEquals(2, test.solution("Teullinika Teullyeotzi "));
assertEquals(7, test.solution(" a b c d e f g "));
assertEquals(0, test.solution(" "));

전체 코드

https://github.com/jungguji/algorithm_training/blob/master/src/main/java/algorithm/baekjoon/string/%EB%8B%A8%EC%96%B4%EC%9D%98_%EA%B0%9C%EC%88%98.java

댓글 공유

프로그래머스: 조이스틱

문제

문제에 오류가 있는 것으로 판단됌

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

코드

아래 코드는 통과되지 못했음

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
private static final int A_ASCII = 65;

public int solution(String name) {
    char[] toChar = name.toCharArray();

    int answer = getUpDownCount(toChar);

    int[] serialIndex = getLongestSerialIndex(toChar);

    int leftRightCursur = getLeftRightCount(serialIndex[0], serialIndex[1], toChar.length);

    answer += leftRightCursur;

    return answer;
}

private int getUpDownCount(char[] names) {
    int count = 0;
    for (char c : names) {
        int upDownCurour = c - A_ASCII;
        if (upDownCurour > 12) {
            upDownCurour = 26 - upDownCurour;
        }

        count += upDownCurour;
    }

    return count;
}

private int[] getLongestSerialIndex(char[] array) {
    List<Serial> list = getSerialList(array);

    Serial serial = getMaxCountSerial(list);

    int[] result = new int[2];
    result[0] = serial.index;
    result[1] = serial.index + serial.count;

    return result;
}

private List<Serial> getSerialList(char[] array) {
    int count = 0;
    List<Serial> list = new ArrayList<Serial>();

    for (int i = 0; i < array.length; i++) {
        if (array[i] != 'A') {
            count = 0;
            continue;
        }

        if (count == 0) {
            list.add(new Serial(i, 1));
        } else {
            list.get(list.size()-1).count = (count+1);
        }

        count++;
    }

    return list;
}

private Serial getMaxCountSerial(List<Serial> list) {
    int max = 0;
    Serial serial = new Serial();

    for (Serial s : list) {
        if (max <= s.count) {
            max = s.count;
            serial = s;
        }
    }

    return serial;
}

private int getLeftRightCount(int serialIndex, int serialCount, int nameLength) {
    int leftRightCursur = 0;

    if (serialIndex == 0 && serialCount == 0) {
        leftRightCursur = nameLength - 1;
    } else {
        int left = serialIndex == 0 ? 0 : serialIndex - 1;
        int right = nameLength - serialCount;

        leftRightCursur = left > right ? (right * 2) + left : (left * 2) + right;
        leftRightCursur = leftRightCursur > nameLength - 1 ? nameLength - 1 : leftRightCursur;
    }

    return leftRightCursur;
}

class Serial {

    private int index;
    private int count;

    public Serial() {}

    public Serial(int index, int count) {
        this.index = index;
        this.count = count;
    }
}

흐름

위 코드는 통과되지 못했음

  1. 문자들을 A로 뺀 후 거꾸로 도는게 빠른지 정방향으로 도는게 빠른지 확인해서 upDownCurour 변수에 저장
  2. 문자열에서 A가 제일 길게 연속되는 부분을 찾기 위해 inner class를 하나 만들어서 A가 연속될 때 마다 A가 시작된 index와 연속된 길이를 저장
  3. A가 제일 길게 저장된 시작 index와 끝 index를 return
  4. 문자열 내에 A가 없으면 정방향으로 돌리고
  5. A가 있으면 return된 index들을 가지고 왼쪽과 오른쪽에서 몇 칸씩 이동해야 하는 지 구함
  6. left와 right를 더하고 가장 짧게 가야하므로 둘 중에 짧은 방향을 한번 더 더함
  7. 더 한 값이 문자열의 길이보다 길면 정방향으로 가는게 더 짧으므로 비교해서 확인
  8. 그렇게 구한 값을 더해서 return
  9. 끝

위 코드는 통과되지 못했음

테스트 케이스

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
assertEquals(4, test.solution("AAABAA"));
assertEquals(56, test.solution("JEROEN"));
assertEquals(23, test.solution("JAN"));
assertEquals(48, test.solution("CANAAAAANAN"));
assertEquals(8, test.solution("BBBAAB"));
assertEquals(56, test.solution("AAAAACANAAAAANANAAAAAA"));
assertEquals(3, test.solution("BBAAAAA"));
assertEquals(41, test.solution("JJAJAAAAAAAAAJ"));
assertEquals(21, test.solution("AJAJAA"));
assertEquals(7, test.solution("BBAABAA"));
assertEquals(6, test.solution("BBABA"));
assertEquals(10, test.solution("BBAABBB"));
assertEquals(7, test.solution("BBAABAAAA"));
assertEquals(10, test.solution("BBAABAAAAB"));
assertEquals(6, test.solution("ABAAAAAAABA"));
assertEquals(2, test.solution("AAB"));
assertEquals(11, test.solution("AABAAAAAAABBB"));
assertEquals(5, test.solution("ZZZ"));
assertEquals(10, test.solution("BBBBAAAAAB"));
assertEquals(12, test.solution("BBBBAAAABA"));
assertEquals(10, test.solution("ABABAAAAAAABA"));
assertEquals(18, test.solution("BBBBBBBABB"));
assertEquals(5, test.solution("AZAAAZ"));
assertEquals(3, test.solution("AC"));
assertEquals(3, test.solution("BBAAAAA"));
assertEquals(17, test.solution("ABAAABBBBBBB"));

통과된 코드

  • https://by-dev.tistory.com/9
    • 위 주소의 코드는 “AAABAA”인 경우 2를 return
    • 단순히 B까지 이동하는 것만해도 3이 걸리는데 통과 되었다는게 이해가 가지 않음

댓글 공유

프로그래머스: 구명보트

문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int solution(int[] people, int limit) {
    Arrays.sort(people);

    int left = 0;
    int right = people.length - 1;

    int answer = 0;
    while (left <= right) {
        int sum = people[left] + people[right];

        if (sum <= limit) {
            ++left;
        }

        ++answer;
        --right;
    }

    return answer;
}

흐름

  1. 배열을 정렬

  2. 배열 내에서 제일 작은 값이랑 제일 큰 값을 더해서 limit이 넘어가는 지 확인

  3. 넘어가면 제일 작은 값을 증가

  4. 안 넘어가면 제일 큰 값 혼자 빠져야하므로 answer을 증가시키고 right를 감소 시켜서 인덱스를 한칸 땡김

  5. right가 left 보다 작아질 때 까지 반복
    ex) [50,50,70,80] 인 경우 left = 0, right = 4 인데 위 코드르 반복하면 right가 점점 줄어들어 left와 만날 때 끝

  6. 끝

결과

정확성 테스트

번호 속도
테스트 1 통과 (1.92ms, 52.7MB)
테스트 2 통과 (1.56ms, 51.4MB)
테스트 3 통과 (1.66ms, 51MB)
테스트 4 통과 (2.02ms, 50.7MB)
테스트 5 통과 (1.42ms, 53MB)
테스트 6 통과 (1.37ms, 50.9MB)
테스트 7 통과 (1.46ms, 53.1MB)
테스트 8 통과 (0.95ms, 52.6MB)
테스트 9 통과 (1.15ms, 52.5MB)
테스트 10 통과 (2.01ms, 52.4MB)
테스트 11 통과 (1.68ms, 52.7MB)
테스트 12 통과 (1.78ms, 52.7MB)
테스트 13 통과 (2.07ms, 52.5MB)
테스트 14 통과 (1.46ms, 50.5MB)
테스트 15 통과 (1.22ms, 50.1MB)

효율성 테스트

번호 속도
테스트 1 통과 (11.43ms, 56.1MB)
테스트 2 통과 (11.63ms, 55.7MB)
테스트 3 통과 (11.88ms, 53.7MB)
테스트 4 통과 (8.84ms, 56.3MB)
테스트 5 통과 (11.08ms, 55.7MB)

테스트 케이스

1
2
3
4
5
6
assertEquals(3, test.solution(new int[] {70, 50, 80, 50}, 100));
assertEquals(3, test.solution(new int[] {70, 80, 50}, 100));
assertEquals(2, test.solution(new int[] {40, 40, 80}, 160));
assertEquals(2, test.solution(new int[] {20, 50, 50, 80}, 100));
assertEquals(5, test.solution(new int[] {40,50,60,70,80,90}, 100));
assertEquals(2, test.solution(new int[] {40,40,40}, 100));

댓글 공유

Junggu Ji

author.bio


author.job