Code-store

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

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

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

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

입출력 예

입출력 예 설명

입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.

import java.util.*;
class Solution {
    public List<Integer> solution(int[] progresses, int[] speeds) {
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> answer = new ArrayList<>();
        int check = 0, deQ = 0, progress = 0;
        // 작업일수 계산
        for(int i=0; i<progresses.length; i++){
            if(((float)(100-progresses[i])/speeds[i]) % 1 > 0){
                queue.add(((100-progresses[i])/speeds[i]) + 1);    
            }else{
                queue.add((100-progresses[i])/speeds[i]);
            }
        }
        
        // 초기화
        progress = queue.poll();
        check = 1;
        // 배포 가능한 작업량 계산
        while(!queue.isEmpty()){
            deQ = queue.poll();
            if(progress < deQ){
                progress = deQ;
                answer.add(check);
                check = 1;
            }else{
                check++;
            }
        }
        answer.add(check);
        return answer;
    }
}

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

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

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

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        int check = 0;
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == '(')
                check++;
            else
                check--;
            
            // 닫는 괄호수가 이미 열은 괄호수보다 많은 경우
            if(check < 0)
                return false;
        }
        
        // 괄호수가 일치하지 않은 경우
        if(check != 0)
            answer = false;
        return answer;
    }
}

배열 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보다 작거나 같은 정수

연속된 수를 입력하지 않는것이기 때문에 스택의 성질을 이용해서 직전에 입력한 데이터를 확인한뒤에 처리를 하면 된다.

import java.util.*;

public class Solution {
    public Stack<Integer> solution(int []arr) {
        Stack<Integer> answer = new Stack<>();
        for(int num: arr){
            if(answer.isEmpty() || answer.peek() != num){
                answer.push(num);
            }
        }        
        return answer;
    }
}

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항
phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

입출력 예 설명
입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

처음에는 일반적인 방식으로 확인을 했는데

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        for(String phone_num: phone_book){
            for(String comp : phone_book){
                if(phone_num.length() < comp.length()){
                    if(comp.indexOf(phone_num) == 0)
                        return false;
                }
            }
        }
        return answer;
    }
}

해당 코드로 실행을 시켜보니 일반적인 경우에서는 다 통과를 했는데 효율성 테스트에서 문제가 발생했다.

케이스가 많아 질수록 비교 해야하는 경우의수가 많아 지면서 지연 시간이 많이 발생하기 때문에 효율성 테스트에서 문제가 발생한것으로 생각된다.

그렇기 때문에 제외할수 있는 케이스들을 생각해보니

• 정렬을 하는 경우 앞에서부터 정렬이 되기 때문에 랜덤으로 제공되는 번호에 대한 규칙이 발생하기 때문에 구분하기 편해진다는것
• 같은 번호가 없다는 가정이 있다보니 길이가 같은 경우는 절대 같은 수가 될수가 없다는 것
• 본인을 비교할 이유가 없음

위의 두가지의 케이스를 고려해서 다시 한번 고친 코드가 아래의 코드

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);
        for(int i=0; i<phone_book.length; i++){
            for(int j=i+1; j<phone_book.length; j++){
                if(phone_book[i].length() >= phone_book[j].length())
                    break;
                if(phone_book[j].indexOf(phone_book[i]) == 0){
                    return false;
                }
            }
        }
        return answer;
    }
}

해당 코드로 테스트는 통과했습니다.

다른 사람의 풀이로 보니 여러 방법으로 효율을 극대화 시키는 방식이 있을것 같아 보이네요.