문제

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

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

풀이

단지 H-index의 개념이 잘 이해가 안돼서 조금 막힌 문제

거꾸로 정렬해서 가장 큰 논문이 인용된 수부터

현재 논문의 인용된 수보다 전체 몇 개 인용 됐는가 비교해서

전체 인용된 논문 수보다 큰 각 논문의 인용된 수가 몇개인지 찾는 문제

뭔가 국어문제같지만.. 문제에서 친절히 걸어준 링크를 참조하자

https://en.wikipedia.org/wiki/H-index

코드

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/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;
    }
}

메모

스스로 풀었는가 : ❎