[코테 준비 : day16] 스택/큐.1

1. 같은 숫자는 싫어(다시 풀기)

https://school.programmers.co.kr/learn/courses/30/lessons/12906

[문제 풀이 고민]

• 연속적으로 나오는 숫자는 하나만 남기고 모두 제거

1. 잘못 이해함

• 중복을 모두 제거하는 방식으로 이해해서 해시를 사용했음

import java.util.*;

class Solution {
    public int[] solution(int []arr) {
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < arr.length; i++){
            set.add(arr[i]);
        }

        int[] answer = new int[set.size()];

        int index = 0;
        for (int number : set) {
            answer[index++] = number;
        }

        return answer;
    }
}

2. 제출 코드

• 먼저 arr[0]을 저장후 중복일 경우 삭제 아닐경우 새 배열에 저장후 다시 비교하는 방식

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        //중복되는 것 제외를 저장하는 배열
        int[] answer =  new int[arr.length];
        int index = 0;
        //값을 저장
        int prev = arr[0];
        answer[index ++] = prev;

        //값을 비교해서 중복일경우 저장하지 않고, 
        //중복이 아니면 저장하고 새로 prev에서 비교
        for(int i = 0; i < arr.length; i++){
            if(prev != arr[i]){
                answer[index ++] = arr[i];
                prev = arr[i];
            }
        }
        
        //남은 0를 가지고 있는 배열 부분을 없애기 위함
        int[] result = new int[index];

        for(int i = 0; i < index; i++){
            result[i] = answer[i];
        }

        return result;
    }
}

---

2. 올바른 괄호 (다시 풀기)

https://school.programmers.co.kr/learn/courses/30/lessons/12909

[문제 풀이 고민]
반드시 앞과 뒤의 괄호가 닫혀야함 + 짝이 지어져야함

1. 5,11,17 번 테스트 불통 + 효율성 실패

class Solution {
    boolean solution(String s) {
        boolean answer = true;

        String[] arr = s.split("");

        int left = 0;
        int right = 0;

        if(!arr[0].equals("(") || !arr[arr.length - 1].equals(")"))
            return false;

        for(int i = 0; i < arr.length; i++){
            if(arr[i] == "(")
                left ++;
            else if(arr[i] == ")")
                right ++;
            
        }

        if(left == right)
            answer = true;

        return answer;
    }
}

2. 제출 코드

• stack을 사용하여 ( 는 계속 집어넣고 짝인 )가 만날경우 하나씩 pop을 한 후 비어있지 않을경우 짝이 안되는 경우임으로 false를 출력함

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        char[] arr = s.toCharArray();
        Stack<Character> stack = new Stack<>();

        for(int i = 0; i < arr.length; i++){
            if(arr[i] == '('){
                stack.push(arr[i]);
            }
            else if(arr[i] == ')'){
                if(stack.isEmpty()){
                    answer = false;
                    break;
                }
                else{
                    stack.pop();
                }
            }
        }

        if(!stack.isEmpty())
            answer = false;

        
        return answer;
    }
}

---

3. 기능개발

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

[풀이 코드 고민]
-진도가 100%만 반영 가능하며, progresses는 완료되어 있는 상황과 먼저 배포해야하는 순서
speeds는 각 작업의 개발 속도
(출력) 각 배포마다 몇개의 기능이 배포되는지를 리턴
1. 각각의 남은 작업량을 해당속도에 따라 몇일이 걸리는지 저장하는 result 배열을 만듬
2. 다음은 배열에 0을 삭제한다.

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int index = 0;
        int[] answer = new int[progresses.length];
        int[] result = new int[progresses.length];

        for(int i = 0; i < progresses.length; i++){
            int a = (100 - progresses[i]);
            if(a % speeds[i] == 0){
                result[i] = a / speeds[i];
            }
            else{
                result[i] = a / speeds[i] + 1;
            }
        }

        //일 출력
        int prev = result[0];
        int count = 1;

        for(int i = 1; i < result.length; i++){
            if(prev >= result[i]){
                count++;
            }
            else{
                answer[index++] = count;
                prev = result[i];
                count = 1;
            }
        }

        answer[index++] = count;

        //0을 제외하자
        int count2 = 0;
        for (int i = 0; i < answer.length; i++) {
            if (answer[i] != 0) {
                count2++;
            }
        }

        int[] result2 = new int[count2];
        int index2 = 0;
        for (int i = 0; i < answer.length; i++) {
            if (answer[i] != 0) {
                result2[index2++] = answer[i];
            }
        }
        

        return result2;
    }
}

[다른 풀이]

• 아무래도 스택/큐 문제이니 해당 방법으로도 고민해보자

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Stack<Integer> stack = new Stack<>();
        int[] daysLeft = new int[progresses.length];

        for (int i = 0; i < progresses.length; i++) {
            int days = (100 - progresses[i]) / speeds[i];
            if ((100 - progresses[i]) % speeds[i] > 0) {
                days++;
            }
            daysLeft[i] = days;
        }

        for (int i = 0; i < daysLeft.length; i++) {
            int cnt = 1;
            for (int j = i + 1; j < daysLeft.length; j++) {
                if (daysLeft[i] >= daysLeft[j]) {
                    cnt++;
                    i++;
                } else {
                    break;
                }
            }
            stack.push(cnt);
        }

        int[] answer = new int[stack.size()];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = stack.pop();
        }

        return answer;
    }
}