프로그래머스: 탑

문제

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/42583?language=java

코드

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
public int solution(int bridge_length, int weight, int[] truck_weights) {
    LinkedList<Truck> queue = new LinkedList<Truck>();

    for (int i = 0; i < truck_weights.length; i++) {
        queue.offer(new Truck(bridge_length, truck_weights[i]));
    }

    int answer = 1;
    int bridgeOnTruck = 0;
    while (!queue.isEmpty()) {

        int totalWeight = 0;
        for (int i = 0; i < bridgeOnTruck; i++) {
            totalWeight += queue.get(i).weight;
        }

        int nextWeight = 0;
        if (queue.size() > bridgeOnTruck) {
            nextWeight = queue.get(bridgeOnTruck).weight;
        }

        if (totalWeight + nextWeight <= weight) {
            if (queue.size() > bridgeOnTruck) {
                ++bridgeOnTruck;
            }
        }

        for (int i = 0; i < bridgeOnTruck; i++) {
            Truck truck = queue.get(i);
            truck.position = truck.position - 1;
        }

        if (queue.peek().position == 0) {
            queue.poll();
            --bridgeOnTruck;
        }

        ++answer;
    }

    return answer;
}

class Truck {
    public int position;
    public int weight;

    public Truck(int position, int weight) {
        this.position = position;
        this.weight = weight;
    }
}

흐름

  1. 트럭 array를 queue에 모두 저장
  2. 트럭 모두 건널 때 까지 반복
  3. 한 번에 몇 개의 트럭까지 건널 수 있을 지 계산하기 위해 현재 다리 위에 있는 트럭의 개수 만큼 돌면서 트럭 무게를 더함
  4. 다음 번 트럭까지 다리에 올라 올 수 있는 지 확인하기 위해 큐의 마지막 index가 아니라면 queue에서 다음 번 트럭의 무게를 가져옴
  5. 현재 다리에 있는 트럭들의 무게 + 다음 트럭의 무게를 더한 값이 다리가 버틸 수 있는 무게 보다 가벼우면
  6. 큐의 마지막인지 체크해서 큐의 마지막이 아니라면 그 다음 트럭도 다리 위에 올라와야 하기 때문에 다리 위 트럭의 개수(truckAmount)를 증가 시킴
  7. 다리 위 트럭의 수 만큼 반복하면서 트럭을 앞으로 한칸 씩 움직임
  8. 첫 번째 트럭이 다리를 건넜다면 queue에서 제거하고 다리 위 트럭 수를 하나 감소 시킴
  9. 초를 증가 시킴
  10. 끝

결과

번호 속도
테스트 1 통과 (3.63ms, 52.1MB)
테스트 2 통과 (14.16ms, 52.1MB)
테스트 3 통과 (1.65ms, 53.3MB)
테스트 4 통과 (41.49ms, 53.8MB)
테스트 5 통과 (70.64ms, 53.9MB)
테스트 6 통과 (53.31ms, 56.1MB)
테스트 7 통과 (3.09ms, 50MB)
테스트 8 통과 (1.97ms, 50.3MB)
테스트 9 통과 (10.68ms, 54.6MB)
테스트 10 통과 (2.20ms, 53MB)
테스트 11 통과 (1.10ms, 52.5MB)
테스트 12 통과 (2.35ms, 52.2MB)
테스트 13 통과 (4.50ms, 52.2MB)
테스트 14 통과 (1.26ms, 53MB)

테스트 케이스

1
2
3
assertEquals(8, test.solution(2, 10, new int[] {7,4,5,6}));
assertEquals(101, test.solution(100, 100, new int[] {10}));
assertEquals(110, test.solution(100, 100, new int[] {10,10,10,10,10,10,10,10,10,10}));

댓글 공유

프로그래머스: 프린터

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

코드

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
public int solution(int[] priorities, int location) {
    int answer = 0;

    LinkedList<Integer> queue = new LinkedList<Integer>();
    for (int i = 0; i < priorities.length; i++) {
        queue.offer(priorities[i]);
    }

    while (queue.size() != 0) {
        for (int i = 1; i < queue.size(); i++) {
            if (queue.peek() < queue.get(i)) {
                queue.offer(queue.poll());

                if (location == 0) {
                    location = queue.size() - 1;
                } else {
                    --location;
                }

                i = 0;
            }
        }

        answer++;
        if (location == 0) {
            break;
        }

        --location;
        queue.poll();
    }

    return answer;
}

흐름

  1. 우선순위가 담긴 배열(priorities)을 Queue에 저장

  2. 큐에 첫 번째 값을 꺼내서 그 뒤 값들과 비교

  3. 첫 번째 값이 뒤에 있는 값들 보다 작다면 큐에 맨 뒤로 보냄

  4. 출력해야 되는 프린터의 index를 조정

    • index가 0 이라면 맨 뒤로 이동했을테니 큐 크기 - 1;
    • 아니라면 앞으로 한 칸 이동 했을테니 -1

  5. 맨 뒤로 이동 시켰으면 맨 앞에 값이 변경 됐으므로 처음부터 다시 검사

  6. 큐의 0 번째 인덱스가 가장 큰 값이라면 count를 증가시키고 출력해야 하는 프린터의 위치를 확인

  7. 출력해야하는 프린터가 맨 앞이라면 break로 반복문을 빠져나와 프로그램 종료

  8. 아니라면 맨 앞에 값을 삭제하고 index를 -1 해서 한 칸 앞으로 당김

  9. 끝날 때 까지 반복

  10. 끝

결과

번호 속도
테스트 1 통과 (3.17ms, 52.8MB)
테스트 2 통과 (3.41ms, 52.6MB)
테스트 3 통과 (1.33ms, 52.6MB)
테스트 4 통과 (1.15ms, 50.8MB)
테스트 5 통과 (0.85ms, 52.2MB)
테스트 6 통과 (1.44ms, 52.7MB)
테스트 7 통과 (1.58ms, 50.4MB)
테스트 8 통과 (3.89ms, 52.9MB)
테스트 9 통과 (1.04ms, 52.8MB)
테스트 10 통과 (1.57ms, 52.3MB)
테스트 11 통과 (3.90ms, 52.7MB)
테스트 12 통과 (1.07ms, 52.3MB)
테스트 13 통과 (4.36ms, 52.1MB)
테스트 14 통과 (0.83ms, 52MB)
테스트 15 통과 (0.95ms, 50.4MB)
테스트 16 통과 (1.21ms, 50.3MB)
테스트 17 통과 (2.79ms, 50.7MB)
테스트 18 통과 (0.94ms, 50.7MB)
테스트 19 통과 (2.61ms, 53.1MB)
테스트 20 통과 (1.51ms, 52.3MB)

테스트 케이스

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

댓글 공유

프로그래머스: 기능개발

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

소스

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
public int[] solution(int[] progresses, int[] speeds) {
    int start = 0;
    List<Integer> list = new ArrayList<Integer>();
    while (start != progresses.length) {
        int deploy = 0;
        for (int i = start; i < progresses.length; i++) {
            progresses[i] += speeds[i];
        }

        for (int i = start; i < progresses.length; i++) {
            if (progresses[start] < 100) {
                break;
            }

            if (progresses[i] >= 100) {
                ++start;
                ++deploy;
            }
        }

        if (deploy != 0) {
            list.add(deploy);
        }
    }

    int[] answer = list.stream().mapToInt(i -> i).toArray();
    return answer;
}

흐름

  1. 기능개발이 완료된 인덱스부터 반복하기 위해 start 변수 생성

  2. 기능개발이 끝날 때 까지 반복

  3. 개발이 안 끝난 기능 index 부터 돌면서 작업 속도를 더 함

  4. 개발이 안 끝난 기능 index 부터 돌면서 첫 번째 기능이 개발 됐는지 확인하고 안 끝났으면 3 번으로 돌아감

  5. 첫 번째 기능이 완료 되었으면 그 다음 기능개발을 위해 ++start 하고, deploy된 기능을 카운팅하는 deploy 변수를 증가

  6. deploy한 기능이 있는 경우에만 list에 저장

  7. ArrayList를 int[]로 변경

  8. 끝

다른 분의 소스

1
2
3
4
5
6
7
8
9
10
11
public int[] solution(int[] progresses, int[] speeds) {
    int[] dayOfend = new int[100];
    int day = -1;
    for(int i=0; i<progresses.length; i++) {
        while(progresses[i] + (day*speeds[i]) < 100) {
            day++;
        }
        dayOfend[day]++;
    }
    return Arrays.stream(dayOfend).filter(i -> i!=0).toArray();
}

로직

  • 기능 갯수 만큼 돌면서 진도율과 날짜 * 개발 속도를 비교해서 100 보다 작으면 다음날로 증가시키고 크면 그 날짜에 저장되는 갯수를 증가시킴

  • 대박

결과

1 번

번호 속도
테스트 1 통과 (4.53ms, 50.8MB)
테스트 2 통과 (5.07ms, 50.6MB)
테스트 3 통과 (5.09ms, 52.8MB)
테스트 4 통과 (5.29ms, 52.4MB)
테스트 5 통과 (8.36ms, 55MB)
테스트 6 통과 (4.95ms, 51.2MB)
테스트 7 통과 (5.58ms, 52.6MB)
테스트 8 통과 (5.18ms, 50.7MB)
테스트 9 통과 (5.44ms, 52.5MB)
테스트 10 통과 (5.22ms, 50.5MB)

2 번

번호 속도
테스트 1 통과 (6.60ms, 51.4MB)
테스트 2 통과 (6.83ms, 53.1MB)
테스트 3 통과 (6.92ms, 52.5MB)
테스트 4 통과 (6.70ms, 52.8MB)
테스트 5 통과 (19.88ms, 52.4MB)
테스트 6 통과 (5.05ms, 50.7MB)
테스트 7 통과 (7.01ms, 52.5MB)
테스트 8 통과 (4.68ms, 50.5MB)
테스트 9 통과 (6.95ms, 52.2MB)
테스트 10 통과 (5.31ms, 50.8MB)
  • 두 소스 모두 Arrays.stream을 사용하지 않고 반복해서 저장하면 1초 대로 줄어듬.
  • 확실히 스트림이 느린 듯함.

테스트 케이스

1
2
3
assertArrayEquals(new int[] {2,1}, test.solution(new int[] {93, 30, 55}, new int[] {1, 30, 5}));
assertArrayEquals(new int[] {3}, test.solution(new int[] {0, 30, 55}, new int[] {1, 99, 99}));
assertArrayEquals(new int[] {1,1,1}, test.solution(new int[] {3, 2, 1}, new int[] {1, 1, 1}));

전체 소스

https://github.com/jungguji/algorithm_training/blob/master/src/main/java/algorithm/programmers/level2/stackqueue/%EB%8B%A4%EB%A6%AC%EB%A5%BC_%EC%A7%80%EB%82%98%EB%8A%94_%ED%8A%B8%EB%9F%AD.java

댓글 공유

프로그래머스: 스킬트리

https://programmers.co.kr/learn/courses/30/lessons/49993?language=java

소스

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
public int solution(String skill, String[] skill_trees) {
    char[] ch = skill.toCharArray();

    List<ArrayList<Skill>> l = new ArrayList<ArrayList<Skill>>();
    for (String element : skill_trees) {
        ArrayList<Skill> list = new ArrayList<Skill>();

        for (int i = 0; i < ch.length; i++) {
            Skill s = new Skill();
            s.skill = ch[i];
            s.index = element.indexOf(ch[i]);

            if (s.index != -1) {
                list.add(s);
            }
        }

        l.add(list);
    }

    int answer = 0;
    for (ArrayList<Skill> list : l) {
        Collections.sort(list, new Comparator<Skill>() {
            @Override
            public int compare(Skill o1, Skill o2) {
                return o1.getIndex().compareTo(o2.getIndex());
            }
        });

        StringBuilder sb = new StringBuilder();
        for (Skill s : list) {
            sb.append(s.getSkill());
        }

        if (skill.startsWith(sb.toString())) {
            answer++;
        }
    }

    return answer;
}

public class Skill {
    private int index;
    private char skill;

    public Integer getIndex() {
        return index;
    }
    public void setIndex(int index) {
        this.index = index;
    }
    public char getSkill() {
        return skill;
    }
    public void setSkill(char skill) {
        this.skill = skill;
    }
}

흐름

  1. 스킬트리에 있는 스킬들을 선행스킬 만큼 반복한다.

  2. 돌면서 스킬들에서 선행스킬의 index와 선행스킬명을 저장하는 클래스(Skill)에 저장하고 그 클래스를 List에 저장한다.

    • ex) List = [{index = 1, skill = A}, {index = 7, skill = Q}, …]

  3. 선행스킬명을 저장한 List를 다른 List(AllSkillList)에 저장한다.

    • 전체 스킬을 저장해야 하므로
    • ex) AllSkillList = [List1, List2, List3, …]

  4. 전체 스킬이 저장된 List(AllSkillList)를 돌면서 저장된 List의 Skill의 Index 순으로 정렬 시킨다.

  5. 정렬된 List를 돌면서 StringBuilder에 스킬명을 담는다.

  6. 입력받은 선행스킬과 비교하여 일치하면 answer을 증가 시킨다.

  7. 끝

다른 분의 소스

1
2
3
4
5
6
7
8
9
10
11
12
13
public int solution(String skill, String[] skill_trees) {
    int answer = 0;
    ArrayList<String> skillTrees = new ArrayList<String>(Arrays.asList(skill_trees));
    Iterator<String> it = skillTrees.iterator();

    while (it.hasNext()) {
        if (skill.indexOf(it.next().replaceAll("[^" + skill + "]", "")) != 0) {
            it.remove();
        }
    }
    answer = skillTrees.size();
    return answer;
}

로직

  • 스킬트리에 있는 스킬들 중 선행스킬이 아닌 녀석들을 없애버리고 선행스킬과 일치하는 지 확인해서 일치하지 않으면 List에서 삭제하고 List의 갯수를 return 하는 것으로 끝을 낸다.

  • ex) “CBD” 인 경우 “BACDE”에서 “C”, “B”, “D”가 아닌 녀석들은 삭제되서 “BCD”가 남지만 “CBD”.indexOf(“BCD”) 할 경우 “CBD”에 “BCD”가 존재 하지 않으므로 1을 return 하고 -1은 0이 아니므로 List에서 삭제된다.

  • “BDA” 인 경우엔 “CBD”.indexOf(“BD”) 할 경우 “CBD”에 존재하지만 1 번째 index에 존재하므로 1을 return 하고 List에서 삭제된다.

  • 직관적이고 가독성이 좋다.

  • 정규표현식 활용도 굿

결과

1 번

번호 속도
테스트 1 통과 (1.40ms, 52.1MB)
테스트 2 통과 (1.37ms, 50.1MB)
테스트 3 통과 (1.29ms, 52.7MB)
테스트 4 통과 (1.11ms, 52.3MB)
테스트 5 통과 (1.42ms, 50.6MB)
테스트 6 통과 (1.33ms, 52.4MB)
테스트 7 통과 (1.38ms, 50.5MB)
테스트 8 통과 (1.38ms, 50.8MB)
테스트 9 통과 (1.46ms, 52MB)
테스트 10 통과 (1.26ms, 52.4MB)
테스트 11 통과 (1.36ms, 54.3MB)
테스트 12 통과 (1.72ms, 52.5MB)
테스트 13 통과 (1.27ms, 52.3MB)
테스트 14 통과 (1.31ms, 52.2MB)

2 번

번호 속도
테스트 1 통과 (17.73ms, 54.5MB)
테스트 2 통과 (18.75ms, 52.2MB)
테스트 3 통과 (17.83ms, 52.4MB)
테스트 4 통과 (19.98ms, 54.3MB)
테스트 5 통과 (20.10ms, 52.3MB)
테스트 6 통과 (20.89ms, 52.5MB)
테스트 7 통과 (20.94ms, 54.3MB)
테스트 8 통과 (18.68ms, 52.2MB)
테스트 9 통과 (19.60ms, 52.8MB)
테스트 10 통과 (20.75ms, 54.4MB)
테스트 11 통과 (18.02ms, 52.3MB)
테스트 12 통과 (18.70ms, 54.3MB)
테스트 13 통과 (18.79ms, 52.5MB)
테스트 14 통과 (19.85ms, 54.8MB)
  • 2 번의 경우 Arrays.asList(skill_trees) 와 replace 때문에 속도가 살짝 느려진 것으로 판단된다.

테스트 케이스

1
2
3
4
5
6
assertEquals(3, test.solution("CBD", new String[] {"BACDE", "CBADF", "AECB", "BDA", "ASF", "BDF","CEFD"}));
assertEquals(4, test.solution("C", new String[] {"BACDE", "CBADF", "AECB", "BDA"}));
assertEquals(2, test.solution("CBD", new String[] {"C", "D", "CB", "BDA"}));
assertEquals(2, test.solution("AC", new String[] {"ABC", "CA", "ATEW", "SFCQTA"}));
assertEquals(2, test.solution("ACHQ", new String[] {"TWER", "FGCHQEA", "ATEW", "SFCQTA"}));
assertEquals(4, test.solution("CBDK", new String[] {"CB", "CXYB", "BD", "AECD", "ABC", "AEX", "CDB", "CBKD", "IJCB", "LMDK"}));
  • 임의로 만든 테스트 케이스 이므로 위 테스트 케이스를 통과해도 시험에서 통과하지 못할 가능성이 있다.

댓글 공유

  • page 1 of 1

Junggu Ji

author.bio


author.job