문제

링크 : https://programmers.co.kr/learn/courses/30/lessons/42584

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

풀이

문제에서 스택을 쓰라고하니 스택을 쓰는 것 까지는 ok인데..

분명 예전에 본 것 같은 문제인데도 풀이법이 잘 떠오르지 않았다.. 🙀

찾아보니 스택에 다음 값을 담는다고 생각하면 이해가 됐다.

일단 가장 높은 주식 가격의 인덱스가 항상 스택의 top에 있다.

1

stack.push(i);

만약 가장 높은 주식 가격이 붕괴됐다면 붕괴된 값은 빼주고 정답에 붕괴될 때까지 얼마나 걸렸는지 기록한다.

1
2
3
4
5

while( !(stack.empty()) && prices[stack.peek()] > prices[i])
{
    int tmp = stack.pop();
    answer[tmp] = i - tmp;
}

코드

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

import java.util.Stack;


class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> stack = new Stack<Integer>();
        
        for(int i=0;i<prices.length;i++)
        
        {
            while( !(stack.empty()) && prices[stack.peek()] > prices[i])
            {
                int tmp = stack.pop();
                answer[tmp] = i - tmp;
            }
            stack.push(i);
            
        }

        while(!stack.empty())
        {
            int tmp = stack.pop();
            answer[tmp] = prices.length - 1 - tmp;
        }
        
        return answer;
    }
    
    
}

메모

스스로 풀었는가 : ❎

뭔가 아이디어가 생각나지 않아 풀지 못한 문제.. 능지 어떡함!!!😡

문제

링크 : https://programmers.co.kr/learn/courses/30/lessons/42583

• 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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 함수를 완성하세요.

풀이

문제에서 언제 다리에 올라가고 내리는지의 경계선을 주의해서 생각해야하는 문제

반복문 첫번째 if문

반복문이 한 번 동작할때를 1초라고 생각하고 내리는 것을 우선했다

이 때 내리는 것은 다리를 건너기 위해서는 다리길이만큼의 초가 필요하다는 점을 유의하여 계산해주어야 한다.

반복문 두번째 if문

다리의 무게가 버틸 수 있어 올릴 수 있다면 한 트럭을 올린다.

위 두 과정을 모두 건널 때 까지 반복한다.

이제보니 코드에 조건문을 너무 난발한 것 같다 중복되는 조건도 있고..

🙀

코드

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

import java.util.Queue;
import java.util.LinkedList;

class Solution
{
    //트럭이 몇대 올라갈 수 있느냐
    static Queue<Integer> que = new LinkedList<Integer>();
    
    public static int solution(int bridge_length, int weight, int[] truck_weights) {
        int curTime = 0;
        int curWeight = 0;
        int outIdx = 0;
        //2초 경과하면 그냥 나가
        int i = 0;
        while(i != truck_weights.length || que.size() != 0)
        {
            if(que.size() != 0 && ((curTime - que.peek()) >= bridge_length))
            {
                curWeight -= truck_weights[outIdx++];
                que.poll();
                

            }
            if(i != truck_weights.length && curWeight + truck_weights[i] <= weight)
            {
                que.add(curTime);
                curWeight += truck_weights[i];
                i++; 
            }
            curTime++;
        }

        return curTime;
    }

}

메모

스스로 풀었는가 : ✅

문제

링크 : https://programmers.co.kr/learn/courses/30/lessons/42578

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 ‘_’ 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

풀이

문제 주제도 해시이고 문제를 읽어보면 뭔가 자바 HashMap을 사용하면 될 것 같은 문제

처음 생각하기로는 map을 String,String으로 만들어 중복된 옷을 제외하고 일일이 숫자를 세는 방식을 생각했는데

그것보다는 map을 String,int로 만들어 애초에 각 옷의 종류(key)에 몇가지의 옷 종류가 있는지를 계산하면 더욱 우아하게 풀 수 있음 🏆

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import java.util.HashMap;
import java.util.Map.Entry;
class Solution {
    public static int solution(String[][] clothes) {
        String key;
        HashMap <String,Integer> map = new HashMap<String,Integer>();
        
        for(int i=0;i<clothes.length;i++)
        {
            key = clothes[i][1];
            map.put(key, map.getOrDefault(key, 0)+1);
        }

        int answer = 1;
        for(Entry<String,Integer> entry : map.entrySet())
        {
            answer *= entry.getValue() + 1;
        }
        return answer - 1;
    }
}

메모

스스로 풀었는가 : ❎

문제

링크 : https://programmers.co.kr/learn/courses/30/lessons/12953

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

풀이

문제 그대로 최소공배수를 구하는 문제

gcd는 유클리드 호제법이라는 방법을 사용했고

두 수의 최소공배수는 두 수의 곱을 두 수의 최대공약수로 나누면 된다.

만약 모른다고 하여도 금방 찾아보면 쉽게 이해할 수 있을 것임! ✍

코드

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

class Solution {


    static int gcd(int numA,int numB)
    {
        int result = 0;
        if(numA % numB == 0)
        {
            return numB;
        }
        else
        {
            result = gcd(numB,numA % numB);
        }
        return result;
    }
    static int lcd(int numA, int numB) {
        int result = 0;
        int gcd = 0;
        gcd = gcd(numA,numB);
        
        return (numA * numB)/gcd;
    }
    
    public int solution(int[] arr) {
        
        int answer = 0;
        int numA = arr[0];
        for(int i = 1;i<arr.length;i++)
        {
            numA = lcd(numA,arr[i]);   
        }
        answer = numA;
        return answer;
    }

}

메모

스스로 풀었는가 : ✅