내일배움캠프 54일차 TIL _ 12주 1일차

 

• 오늘 있었던 일
  
  • 스프링 공부
  • 알고리즘

알고리즘 문제 풀기

 

     ● 뒤에 있는 큰 수 찾기

● 뒤에 있는 큰 수 찾기 //링크

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> stack = new Stack<>();

        stack.push(0);
        for (int i = 0; i < numbers.length; i++) {
            while (!stack.isEmpty() && numbers[i] > numbers[stack.peek()]) {
                answer[stack.pop()] = numbers[i];
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            answer[stack.pop()] = -1;
        }
        return answer;
    }
}

• 첫 도전엔 실패했지만 다음 문제를 고쳐서 통과했다.
  • 문제 지문에
    • 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.
  • 각수의 다음값을 컬렉션의 큐를 이용해 구했지만 -1가 나오는 수를 설정하지 못해 다시했다.
  • 스택을 이용해 수를 구하는게 아닌 인덱스를 구하는 방식으로해서 통과했다.
• 밑은 다른 사람의 풀이

• import java.util.*;
  
  class Solution {
      public int[] solution(int[] numbers) {
          int[] answer = new int[numbers.length];
          Arrays.fill(answer, -1);
          Stack<Integer> s = new Stack<>();
          s.push(0);
          for(int i = 1; i < numbers.length; i++){
              while(!s.isEmpty()){
                  int idx = s.pop();
                  if(numbers[i] > numbers[idx]){ // 뒤가 더 클때
                      answer[idx] = numbers[i];
                  } else { // 앞이 더 크거나 같을 때
                      s.push(idx);
                      break;
                  } 
              }
              s.push(i);
          }
  
          return answer;
      }
  }

• 컬렉션... 필요없었네

 

     ● 롤케이크 자르기

● 롤케이크 자르기 //링크

import java.util.*;

class Solution {
    public int solution(int[] topping) {
         int answer = 0;

        Map<Integer, Integer> leftMap = new HashMap<>();
        Map<Integer, Integer> rightMap = new HashMap<>();

        for (int i = 0; i < topping.length; i++) {
            rightMap.put(topping[i], rightMap.getOrDefault(topping[i], 0) + 1);
        }

        for (int i = 0; i < topping.length; i++) {
            leftMap.put(topping[i], leftMap.getOrDefault(topping[i], 0) + 1);
            if (rightMap.get(topping[i]) == 1) {
                rightMap.remove(topping[i]);
            } else {
                rightMap.put(topping[i], rightMap.get(topping[i]) - 1);
            }

            if (leftMap.size() == rightMap.size()) {
                answer++;
            }
        }
      return answer;
    }
}

• • 2번만에 통과했다.
  • 문제 지문에
    • 동생은 네 가지 토핑(1, 2, 3, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것이 아닙니다. 만약 롤케이크의 네 번째 토핑(3)과 다섯 번째 토핑(1) 사이를 자르면 [1, 2, 1, 3], [1, 4, 1, 2]로 나뉘게 됩니다
  •  스택을 이용해 각 경우를 구해서 했을때 시간 초과로 실패했다.
  • 멥을 이용해 각 수를 구해 배열을 순회 해서 값을 구했다.
• 밑은 다른 사람의 풀이

• class Solution {
      public int solution(int[] topping) {
          int answer = 0;
          int[] left = new int[10001], right = new int[10001];
          int ls = 0, rs = 0;
          for(var i : topping) right[i]++;
          for(var i : right) rs += i > 0 ? 1 : 0;
          for(var i : topping) {
              right[i]--;
              if (right[i] == 0) rs--;
              if (left[i] == 0) ls++;
              left[i]++;
              if (rs == ls) answer++;
          }
          return answer;
      }
  }

• 다른 사람의 댓글
  • for(var i : right) rs += i > 0 ? 1 : 0;
  • rs 에 i > 0 큰 경우 +=1 아니면 += 0
• 이렇게도 구할수 있구나

 

---

당일 회고

• 오늘 너무 더워서 샤워를 2번이나 했는데 덥다.
  너무 어지러운데 열사병인가?