[Java] 프로그래머스. Study 2주차

1. 같은 숫자는 싫어

문제 설명

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

• arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
• arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 arr의 크기 : 1,000,000 이하의 자연수
• 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

---

입출력 예

arr answer

[1,1,3,3,0,1,1]	[1,3,0,1]
[4,4,4,3,3]	[4,3]

풀이

array : 반환할 값들을 담을 ArrayList

prev : 비교할 값

 

매개변수 arr 배열을 순회하며 값을 비교할 거라 prev에는 초기값으로 arr[0]+1을 넣어준다.

배열을 순회하며 만약 prev와 값이 다르다면 array에 추가하고 prev를 해당 값으로 바꿔준다.

정답

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        ArrayList<Integer> array = new ArrayList<>();
        int prev = arr[0]+1;
        for(int i : arr) {
            if(prev!=i) {
                array.add(i);
                prev = i;
            }
        }
        int[] answer = array.stream().mapToInt(i->i).toArray();
        return answer;
    }
}

 

 

2. 기능 개발

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

progresses speeds return

[93, 30, 55]	[1, 30, 5]	[2, 1]
[95, 90, 99, 99, 80, 99]	[1, 1, 1, 1, 1, 1]	[1, 3, 2]

풀이

days : 기능 별로 배포까지 걸리는 날짜 ((100-현재 작업율)/하루 작업율)

count : 한 번에 배포가 가능한 기능의 수

array : count를 담을 ArrayList

start : 작업 날짜를 비교할 변수

 

먼저 기능 별로 배포까지 걸리는 날짜를 계산해서 days 배열에 넣어준다.

start에 days[0]을 초기값으로 넣어준다.

days 를 순회하며 start보다 값이 작으면 함께 배포가 가능하기 때문에 count에 1을 더해준다.

start보다 값이 크다면 함께 배포가 불가능하기 때문에 현재 count 값을 리스트 array에 넣어주고 count는 1로, start는 현재의 배열 값으로 넣어주고 이어서 배열을 순회한다.

정답

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] days = new int[progresses.length];
        
        for(int i=0; i< progresses.length; i++) {
            days[i] = (int)Math.ceil((double)(100-progresses[i])/speeds[i]);
            System.out.println(days[i]);
        }

        ArrayList<Integer> array = new ArrayList<>();
        int count = 1;
        int start = days[0];
        for(int i=1; i< days.length; i++) {
            if(days[i]<=start) {
                count++;
            }
            else {
                array.add(count);
                count = 1;
                start = days[i];
            }
        }
        array.add(count);

        return array.stream().mapToInt(i->i).toArray();
    }
}

 

 

3. 올바른 괄호

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

---

입출력 예

s answer

"()()"	true
"(())()"	true
")()("	false
"(()("	false

풀이

st : 문자열을 한 글자씩 넣어줄 스택

 

문자열을 한 글자씩 잘라서 봤을 때 “(”라면 st에 넣는다.

“)”일 때는 스택이 비어있으면 괄호의 짝이 맞지 않는 경우이기 때문에 false를 return하고 그게 아니라면 st에서 값을 빼준다.

문자열의 끝까지 돌았을 때 st에 값이 남아있으면 false를, 비어있다면 true를 return한다.

정답

import java.util.*;
class Solution {
    boolean solution(String s) {
        Stack<Character> st = new Stack<>();
        for(Character c : s.toCharArray()) {
            if(c=='(') st.push(c);
            else {
                if(st.isEmpty()) return false;
                else st.pop();
            }
        }

        return st.isEmpty() ? true : false;
    }
}

 

 

4. 프린터

문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다.

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
• 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
• location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

입출력 예

priorities location return

[2, 1, 3, 2]	2	1
[1, 1, 9, 1, 1, 1]	0	5

풀이

q : 인쇄 대기열을 표현하는 큐(원하는 문서가 언제 인쇄되는지 찾아야하기 때문에 int[] 타입으로 생성)

count : 인쇄된 문서의 수

start : q의 첫 번째 요소를 임시로 담아 놓을 변수

max : q의 첫 번째 요소를 빼고 남아있는 문서 중 최대값

 

먼저 int[] 타입의 큐를 만들고 배열 priorities 원소들을 index, value 쌍으로 만들어 큐에 넣어준다.

큐의 첫번째 요소를 빼고 max보다 작다면 큐에 다시 넣어준다.

max보다 크다면 인쇄가 가능하기 때문에 count를 +1해준다. (큐에 다시 넣지 않음)

이 때, 인쇄할 문서의 index와 location 값이 일치하면 loop를 탈출한다.

정답

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        Queue<int[]> q = new LinkedList<>();
        for(int i=0; i< priorities.length; i++) {
            q.add(new int[]{i, priorities[i]});
        }

        int count = 0;
        while(!q.isEmpty()) {
            int[] start = q.poll();
            if(q.isEmpty()) {
                count++;
                break;
            }
            int max = q.stream().map(i->i[1]).mapToInt(i->i).max().getAsInt();
            if(start[1]<max) {
                q.add(start);
            }
            else {
                count++;
                if(start[0]==location) break;
            }
        }
        
        return count;
    }
}

 

 

5. 다리를 지나는 트럭

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간 다리를 지난 트럭 다리를 건너는 트럭 대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

bridge_length weight truck_weights return

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

풀이

마찬가지로 코플릿에서 풀었던 문제.

큐에 다리 길이만큼 0으로 초기값을 넣어준다.

그리고 대기하는 트럭의 무게를 새로운 배열로 만들어준다.

큐에 값이 있거나 대기하는 트럭이 있을 때 아래 과정을 반복한다.

1. 대기하는 트럭이 있을 때 큐의 첫번째 요소를 제거하고 남은 요소들의 합을 구한다. 위에서 구한 합과 대기하는 첫 번째 트럭의 무게를 더했을 때 다리가 견딜 수 있는 최대 무게보다 크다면 다리에 올라갈 수 없기 때문에 큐에 다시 0을 채워준다. 만약 작다면 큐에 넣어주고 해당 값을 제외한 나머지로 배열을 수정한다.
2. 대기하는 트럭이 없을 때 큐에 남은 요소들을 제거하며 시간만 계산해준다.

정답

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> q = new LinkedList<>();
        int[] arr = truck_weights.clone();
        for(int i=0; i<bridge_length; i++) {
            q.add(0);
        }

        int time = 0;
        while(!q.isEmpty()||arr.length!=0) {
            if(arr.length>0) {
                q.poll();
                int sum = q.stream().mapToInt(i->i).sum();
                if(sum+arr[0]<=weight) {
                    q.add(arr[0]);
                    arr = Arrays.copyOfRange(arr, 1, arr.length);
                    time++;
                }
                else {
                    q.add(0);
                    time++;
                }
            }
            else {
                while(!q.isEmpty()) {
                    q.poll();
                    time++;
                }
            }
        }
        
        return time;
    }
}

 

 

6. 주식가격

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

prices return

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

풀이

array : 가격이 유지되는 시간을 담을 리스트

prices 배열을 순회하며 뒤에 값들이 현재 값보다 작아질 때가 있는지 확인한다.

 

값을 한 번 비교할 때마다 1초씩 증가하기 때문에 time에 1을 더해준다.

만약 현재 값보다 작아진다면 내부 반복문을 탈출하고 현재의 time을 array에 추가한다.

정답

import java.util.*;
class Solution {
    public int[] solution(int[] prices) {
        ArrayList<Integer> array = new ArrayList<>();

        for(int i=0; i< prices.length; i++) {
            int time = 0;
            for(int k=i+1; k< prices.length; k++) {
                time++;
                if(prices[k]<prices[i]) {
                    break;
                }
            }
            array.add(time);
        }
        
        return array.stream().mapToInt(i->i).toArray();
    }
}