망꼬누나의 개발 공부

[문제링크]

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int idx = 0;
        Arrays.sort(people);
        
        for(int i = people.length - 1; i >= idx; i--) {
            if(people[i] + people[idx] <= limit) {
                idx++;
            }
            answer++;
        }        
        return answer;
    }
}

접근법

1. people 배열을 오름차순 정렬한다.
2. [제일 가벼운 + 제일 무거운]조합을 먼저 처리하는 것이 효율적인 방법이므로 가벼운 값을 기준으로 조건을 만족하는지 확인한다.
3. 이때, 조건이 맞다면 인덱스 값을 증가시켜 그 다음 가벼운 수를 기준으로 조건을 확인한다.
4. for문을 돌 때마다 answer을 증가하도록 한다.

탐욕법 (그리디 알고리즘)
매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법으로
위의 코드와 같은 진행 방식을 가진다.

자세한 설명은 구글링을 통해 쉽게 학습할 수 있다.

[문제링크]

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        int area = brown + yellow;          //12
        
        for(int w = area; w > 1; w--){
            if(area % w == 0) {            //12, 6, 4, 3, 2
                int h = area / w;          //1, 2, 3, 4, 6
                
                if(w*2 + ((h-2) * 2) == brown) {
                    answer[0] = w;
                    answer[1] = h;
                    break;
                }
            } 
        }
        return answer;
    }
}

접근법

1.  brown과 yellow 값을 더해서 넓이인 area를 구한다.
2. 가로가 큰 값이므로 w (width) 값을 최대값인 넓이에서부터 시작하여 값을 줄이며 반복문을 실행한다. (이때, w는 1이 될 수 없다.)
3. 가로의 값이 넓이의 약수인 수를 찾는다.
4. 이때, 가로의 값에 따라 '넓이/가로'를 수행하여 세로의 값도 구한다.
5. 이때, 세로와 가로의 값을 2배하여 모두 더했을 때(겹치는 부분 제외), brown 값과 같으면 답이다.
6. 큰 값부터 시작하였으므로 answer 값이 정해졌을 때, 바로 break 한다.

⬇️ 이해하기 쉽게 나타낸 그림이다.

'가로값이 1이 될 수 없다',

'넓이의 약수값이다' 정도의 내용은 이해했지만

어떻게 코드를 짜야할지 감이 잘오지 않았다.

겹치는 값을 제외하는 h-2 부분을 생각하지 못해서

생각이 막혔다는 것을 깨달았다.

또한, 완전 탐색으로 풀면

효율성에서 실패할 것이라 생각한 점도 큰 것 같다.

프로그래머스 스쿨에 뜨는 것처럼

무식해보여도 사실은 최고의 방법일 때도 있는 것 같다.

생각으로 안될 것 같다고 멈추는 것이 아니라

일단 도전해보는 것이 좋은 것 같다.

[문제 링크]

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        Stack<String> stackStr = new Stack<>();
        String[] str = s.split("");
        
        for(int i = 0; i < str.length; i++){
            if(stackStr.isEmpty()) {
                stackStr.push(str[i]);
            }
            else if(stackStr.peek().equals(str[i])){
                stackStr.pop();
            }
            else{
                stackStr.push(str[i]);
            }
        }
        return stackStr.isEmpty() ? 1 : 0;
    }
}

접근법

1. 스택과 배열을 String 타입으로 생성한다.
2. 스택이 비어있을 때, 스택에 값을 넣는다.
3. 비어있지 않고, 넣을 값과 스택의 최상위 값이 같으면 스택의 최상위 값을 삭제한다.
4. 비어있지 않고, 넣을 값과 스택의 최상위 값이 같지 않으면 값을 넣는다.
5. 그 결과로 스택이 empty면 1, 아니면 0을 반환한다.

스택에 대해서 더 설명하자면..

스택 (Stack)이란,
사전적 의미로 '쌓다'를 뜻하며, 말 그대로 데이터를 쌓고 나중에 넣은 데이터가 먼저 나가는 구조를 말한다.
즉, LIFO(Last In First Out) 구조이다.

⬇️ 문자열 'baa'를 예시로 작성한 스택 구조이다.

이때, 데이터를 넣는 과정을 push, 데이터를 삭제하는 과정을 pop이라 한다.

추가로 제일 위에 있는 데이터를 top이라 한다.

스택 내부 메소드

처음에는 이중 for문, 정규표현식, while문 등을 생각했지만,

코드를 작성하는 과정에서 비효율적이라고 느끼고, 생각처럼 쉽게 문제가 풀리지 않았다.

단 2개만 연속되는 문자열을 제거해야 하는 것이라 어려움을 겪었던 것 같다.

그러다 질문하기를 통해 스택을 이용해야 한다는 것을 깨달았고,

허무하게도 스택을 활용하니 너무 쉽게 풀려버렸다...😅

스택의 성질을 알고 있다고 가정했을 때,

접근법을 다른 시각으로 봤으면 쉽게 풀었을 문제인 것 같다.

[문제링크]

class Solution {
    public String solution(String s) {
        String answer = "";
        String [] arr = s.split(" ");
        
        int min = Integer.parseInt(arr[0]);
        int max = min;
        
        for(int i = 1; i < arr.length; i++){
            int temp = Integer.parseInt(arr[i]);
            min = Math.min(min, temp);
            max = Math.max(max, temp);
        }
        
        answer = min + " " + max;
        
        return answer;
    }
}

접근법

1. 공백을 없애고 각 숫자를 배열로 저장한다. (배열로 저장함으로써 각 인덱스의 값 비교가 쉬워졌다.)
2. 최솟값과 최댓값을 넣을 변수를 생성하고,
3. 문자를 숫자 타입으로 변환하여
4. Math.min, Math.max 함수를 사용하여 값 비교를 한다.

Integer.parseInt를 사용하여 

형 변환을 해주는 것이 관건인 것 같다.