프로그래머스LV1_5

LV1 리뷰

처음에는 괜찮았는데 뒤쪽 카카오 기출 문제나 정답률이 낮은 문제는 LV1 문제가 맞나 싶은 의아함이 들정도였다.(내 실력이 아직 부족한 거겠지... 😮‍💨
이제 LV1 문제는 참고해서라도 다 풀어봤으니 내일부터는 LV2 문제를 풀면서 리뷰할 것이다!
정진하자

• 붕대 감기 🤔

  import java.util.*;
  
  class Solution {
      public int solution(int[] bandage, int health, int[][] attacks) {
          int answer = health;
          Arrays.sort(attacks, (a, b) -> a[0] - b[0]);
          int last = attacks[attacks.length - 1][0];
          Map<Integer, Integer> m = new HashMap<>();
          for(int[] a : attacks){
              m.put(a[0], a[1]);
          }
          int cur = 0;
          for(int i = 1; i <= last; i++){
              int damage = m.getOrDefault(i, -1);
              if(damage == -1){
                  if(answer < health){
                      answer = Math.min(health, answer + bandage[1]);
                      cur++;
                      if(cur == bandage[0]){
                          answer = Math.min(health, answer + bandage[2]);
                          cur = 0;
                      }
                  }
              }
              else{
                  answer -= damage;
                  cur = 0;
                  if(answer <= 0) return -1;
              }
          }
          return answer;
      }
  }
  
  // 개선
  class Solution {
      public int solution(int[] bandage, int health, int[][] attacks) {
          int answer = health;
          int currentTime = 0;
          for (int[] attack : attacks) {
              int attackTime = attack[0];
              int damage = attack[1];
              int timeDiff = attackTime - currentTime - 1;
              if (timeDiff > 0) {
                  int heal = (timeDiff * bandage[1]) + ((timeDiff / bandage[0]) * bandage[2]);
                  answer = Math.min(health, answer + heal);
              }
              answer -= damage;
              if (answer <= 0) return -1;
              currentTime = attackTime;
          }
          return answer;
      }
  }

공격을 시간 오름차순으로 정렬하고 맵에 시간, 데미지를 넣고 1부터 마지막 공격까지 시뮬레이션 식으로 구현하여 해결했는데 다른 사람 풀이를 봤는데 시뮬레이션이 아닌 공격 배열만 반복문만 돌면 해결되는 것을 보고 개선해보았다.

• 신고 결과 받기 🤔

  import java.util.*;
  
  class Solution {
      public int[] solution(String[] id_list, String[] report, int k) {
          int[] answer = new int[id_list.length];
          Map<String, Integer> m1 = new HashMap<>();
          for(int i = 0; i < id_list.length; i++) m1.put(id_list[i], i);
          Map<String, Integer> m2 = new HashMap<>();
          Set<String>[] reportSet = new HashSet[id_list.length];
          for(int i = 0; i < id_list.length; i++) {
              reportSet[i] = new HashSet<>();
          }
          for(String st : report){
              String[] str = st.split(" ");
              String s1 = str[0], s2 = str[1];
              if(!reportSet[m1.get(s1)].contains(s2)){
                  reportSet[m1.get(s1)].add(s2);
                  int cnt = m2.getOrDefault(s2, 0);
                  m2.put(s2, cnt + 1);   
              }
          }
          for(int i = 0; i < id_list.length; i ++){
              for(String to : reportSet[i]) {
                  if(m2.getOrDefault(to, 0) >= k) {
                      answer[i]++;
                  }
              }
          }
          return answer;
      }
  }

각 사람의 인덱스를 맵에 저장, 각 사람이 신고 받은 횟수를 저장할 맵과 신고한 사람을 저장할 Set 배열을 준비하여 report를 돌면서 신고한 사람이 이미 있는지 체크하여 없다면 횟수를 늘리고 Set에 신고한 사람을 추가한다. 그러고 마지막에 해당 신고한 사람 Set에서 k보다 크거나 같은 사람이 있으면 ++하여 해결

• 동영상 재생기 🤔

  import java.util.*;
  
  class Solution {
      public String solution(String video_len, String pos, String op_start, String op_end, String[] commands) {
          int len = timeToNum(video_len);
          int start = timeToNum(pos);
          int opS = timeToNum(op_start);
          int opE = timeToNum(op_end);
          if(start >= opS && start <= opE) start = opE;
          for(String c : commands){
              start = start + (c.equals("next")? 10 : -10);
              if(start < 0) start = 0;
              else if(start > len) start = len;
              if(start >= opS && start <= opE) start = opE;
          }
          return String.format("%02d:%02d", start / 60, start % 60);
      }
      
      private int timeToNum(String time){
          String[] t = time.split(":");
          return Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
      }
  }

시간을 문자열로 보는 것이 아니라 정수로 바꾸어 접근하면 간단히 해결할 수 있다. 오프닝 건너뛰기, 0 미만, 비디오 길이 초과 이 3가지를 잘 지키면 해결할 수 있으며 마지막 정규식으로 틀을 고정하는 것은 찾아보았다.

• 택배 상자 꺼내기

  class Solution {
      public int solution(int n, int w, int num) {
          int answer = 0;
          int r = (n % w == 0)? n / w : n / w + 1;
          int c = (n - 1) % w;
          if(r % 2 == 0) c = w - 1 - c;
          int t_r = (num % w == 0)? num / w : num / w + 1;
          int t_c = (num - 1) % w;
          if(t_r % 2 == 0) t_c = w - 1 - t_c;
          if(r % 2 == 0){
              if(t_c < c) answer = r - t_r;
              else answer = r - t_r + 1;
          }
          else{
              if(t_c > c) answer = r - t_r;
              else answer = r - t_r + 1;
          }
          return answer;
      }
  }

조금 계산이 복잡한데 규칙을 찾아보았다. 지그재그로 이동하니까 최대 행과 열의 길이를 찾고 타겟의 행과 열을 찾았다. 그러고 해당 열이 최대 행보다 1 작을 수 있기에 행과 열의 위치에 따라 고려해야한다.

• 가장 많이 받은 선물

  import java.util.*;
  
  class Solution {
      public int solution(String[] friends, String[] gifts) {
          int answer = 0;
          int num = friends.length;
          Map<String, Integer>[] m1 = new HashMap[num];
          Map<String, Integer> m2 = new HashMap<>();
          for(int i = 0; i < num; i++){
              m1[i] = new HashMap<>();
              m2.put(friends[i], i);
          }
          int[] present = new int[num];
          for(String g : gifts){
              String[] s = g.split(" ");
              int idx = m2.get(s[0]);
              m1[idx].put(s[1], m1[idx].getOrDefault(s[1], 0) + 1);
              present[idx]++;
              present[m2.get(s[1])]--;
          }
          int[] next = new int[num];
          for(int i = 0; i < num; i++){
              for(int j = i + 1; j < num; j++){
                  int give = m1[i].getOrDefault(friends[j], 0);
                  int take = m1[j].getOrDefault(friends[i], 0);
                  if(give > take){
                      next[i]++;
                  }
                  else if(give < take){
                      next[j]++;
                  }
                  else{
                      if(present[i] > present[j]){
                          next[i]++;
                      }
                      else if(present[i] < present[j]){
                          next[j]++;
                      }
                  }
              }
          }
          for(int n : next) answer = Math.max(n, answer);
          return answer;
      }
  }
  
  // 개선
  import java.util.*;
  
  class Solution {
      public int solution(String[] friends, String[] gifts) {
          int num = friends.length;
          Map<String, Integer> nameIdx = new HashMap<>();
          for(int i = 0; i < num; i++){
              nameIdx.put(friends[i], i);
          }
          int[][] giftGraph = new int[num][num];
          int[] present = new int[num];
          for(String g : gifts){
              String[] s = g.split(" ");
              int giver = nameIdx.get(s[0]);
              int receiver = nameIdx.get(s[1]);
              giftGraph[giver][receiver]++;
              present[giver]++;
              present[receiver]--;
          }
          int[] next = new int[num];
          for(int i = 0; i < num; i++){
              for(int j = i + 1; j < num; j++){
                  int give = giftGraph[i][j];
                  int take = giftGraph[j][i];
                  if(give > take){
                      next[i]++;
                  } else if(give < take){
                      next[j]++;
                  } else {
                      if(present[i] > present[j]){
                          next[i]++;
                      } else if(present[i] < present[j]){
                          next[j]++;
                      }
                  }
              }
          }
          int answer = 0;
          for(int n : next) {
              answer = Math.max(n, answer);
          }
          return answer;
      }
  }

맵 배열로 주고 받은 것을 넣어 해결하였는데 이러면 조금 무거워지기 때문에 2차원 배열 방식으로 개선했다.

• 노란불 신호등 🤔

  class Solution {
      public int solution(int[][] signals) {
          int answer = 0;
          int l = signals.length;
          int lc = 1;
          for(int i = 0; i < l; i++){
              int g = signals[i][0];
              int y = signals[i][1];
              int r = signals[i][2];
              lc = lcm(lc, g+y+r);
          }
          for(int t = 1; t<=lc; t++){
              boolean isAllYellow = true;
              for(int i = 0; i < l; i++){
                  int g = signals[i][0];
                  int y = signals[i][1];
                  int r = signals[i][2];
                  int C = g+y+r;
                  int remain = (t-1) %C;
                  if(!(g <= remain && remain < g+y)){
                      isAllYellow = false;
                      break;
                  }
              }
              if(isAllYellow){
                  return t;
              }
          }
          return -1;
      }
      
      private int lcm(int num1, int num2){
          int a = Math.max(num1, num2), b = Math.min(num1, num2);
          while(b != 0){
              int tmp = a % b;
              a = b;
              b = tmp;
          }
          return a * (num1 / a) * (num2 / a);
      }
  }

동시에 노란불이 될 수 있는 최대 시간은 최소공배수인 것은 알았는데 모두 노란색인지 체크하는 로직을 모르겠어서 다른 사람 풀이를 참고하여 풀었다.

t - 1을 하는 이유는 t % C 를 할 때 C와 t가 같으면 0이 되어 꼬여버릴 수 있고 노란불은 초록불과 노란불 시점 사이여야 한다는 것을 적용하면 해결된다.

• 중요한 단어를 스포 방지 🤔🤔🤔

  import java.util.*;
  
  class Solution {
      public int solution(String message, int[][] spoiler_ranges) {
          String[] mes = message.split(" ");
          List<int[]> wordRanges = new ArrayList<>();
          int idx = 0;
          for(String word : mes){
              int start = idx;
              int end = idx + word.length() - 1;
              wordRanges.add(new int[]{start, end});
              idx = end + 2;
          }
          boolean[] isSpoiled = new boolean[mes.length];
          for(int i = 0; i < mes.length; i++){
              int ws = wordRanges.get(i)[0];
              int we = wordRanges.get(i)[1];
              for(int[] range : spoiler_ranges){
                  if(!(we < range[0] || ws > range[1])){
                      isSpoiled[i] = true;
                      break; 
                  }
              }
          }
          Set<String> notSpoiledWords = new HashSet<>();
          for(int i = 0; i < mes.length; i++){
              if(!isSpoiled[i]){
                  notSpoiledWords.add(mes[i]);
              }
          }
          Set<String> importantWords = new HashSet<>();
          for(int i = 0; i < mes.length; i++){
              if(isSpoiled[i]){
                  String word = mes[i];
                  if(!notSpoiledWords.contains(word)){
                      importantWords.add(word); 
                  }
              }
          }
          return importantWords.size();
      }
  }

이건 진짜 거의 손도 못 댄 수준이다…이게 LV1…?

정답을 보고 로직 분석만 했다.

1. 각 단어의 시작과 끝 인덱스 배열을 만듦
2. 해당 시작과 끝이 스포일러 배열의 인덱스에 포함되는지에 따라 스포일러 임시 체크
3. 스포일러나 아닌 단어를 Set에 저장
4. 스포일러인 단어가 스포일러가 아닌 단어에 있는지 체크하여 Set에 넣어 크기를 반환