알고리즘

[자바]Programmers - 2024 KAKAO BLIND RECRUITMENT 가장 많이 받은 선물

Z00_HWAN_99 2024. 6. 30. 20:17
728x90
반응형

이번에 풀게 된 문제는 "프로그래머스"라는 사이트에서 2024 KAKAO BLIND RECRUITMENT 가장 많이 받은 선물 문제입니다.
Lv. 2에 정답률은 24%로써 접근은 쉬웠으나 막상 짜보니 조금은 헤맸던 문제입니다.
그러면 제가 풀었던 문제에 대해 설명부터 하며 글 시작해보겠습니다.
 
문제 설명
선물을 직접 전하기 힘들 때 카카오톡 선물하기 기능을 이용해 축하 선물을 보낼 수 있습니다. 당신의 친구들이 이번 달까지 선물을 주고받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하려고 합니다.

  • 두 사람이 선물을 주고받은 기록이 있다면, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다.
    • 예를 들어 A가 B에게 선물을 5번 줬고, B가 A에게 선물을 3번 줬다면 다음 달엔 A가 B에게 선물을 하나 받습니다.
  • 두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물 지수가 더 작은 사람에게 선물을 하나 받습니다.
    • 선물 지수는 이번 달까지 자신이 친구들에게 준 선물의 수에서 받은 선물의 수를 뺀 값입니다.
    • 예를 들어 A가 친구들에게 준 선물이 3개고 받은 선물이 10개라면 A의 선물 지수는 -7입니다. B가 친구들에게 준 선물이 3개고 받은 선물이 2개라면 B의 선물 지수는 1입니다. 만약 A와 B가 선물을 주고받은 적이 없거나 정확히 같은 수로 선물을 주고받았다면, 다음 달엔 B가 A에게 선물을 하나 받습니다.
    • 만약 두 사람의 선물 지수도 같다면 다음 달에 선물을 주고받지 않습니다.

위에서 설명한 규칙대로 다음 달에 선물을 주고받을 때, 당신은 선물을 가장 많이 받을 친구가 받을 선물의 수를 알고 싶습니다.

친구들의 이름을 담은 1차원 문자열 배열 friends 이번 달까지 친구들이 주고받은 선물 기록을 담은 1차원 문자열 배열 gifts가 매개변수로 주어집니다. 이때, 다음달에 가장 많은 선물을 받는 친구가 받을 선물의 수를 return 하도록 solution 함수를 완성해 주세요.


제한사항

  • 2 ≤ friends의 길이 = 친구들의 수 ≤ 50
    • friends의 원소는 친구의 이름을 의미하는 알파벳 소문자로 이루어진 길이가 10 이하인 문자열입니다.
    • 이름이 같은 친구는 없습니다.
  • 1 ≤ gifts의 길이 ≤ 10,000
    • gifts의 원소는 "A B"형태의 문자열입니다. A는 선물을 준 친구의 이름을 B는 선물을 받은 친구의 이름을 의미하며 공백 하나로 구분됩니다.
    • A와 B는 friends의 원소이며 A와 B가 같은 이름인 경우는 존재하지 않습니다.

입출력 예

friends gift result
["muzi", "ryan", "frodo", "neo"] ["muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi", "frodo muzi", "frodo ryan", "neo muzi"] 2
["joy", "brad", "alessandro", "conan", "david"] ["alessandro brad", "alessandro joy", "alessandro conan", "david alessandro", "alessandro david"] 4
["a", "b", "c"] ["a b", "b a", "c a", "a c", "a c", "c a"] 0

 
풀이
저는 우선 이 문제를 접했을 때, 바로 다차원 배열을 생각했습니다. 그리하여 선물을 주는 사람과 받는 사람을 2차원 배열로 나누어 각자의 값을 비교하기로 했습니다. 처음에 풀었을 경우에는 100점 만점에 25점이 떠서 조금 많이 헤맸던 것 같습니다. 하지만 같이 공부하시는 분께서 오류 포인트를 바로잡아 주셔서 리팩토링에 있어 좀 더 쉽게 해결할 수 있었던 것 같습니다.
 
잘못된 코드

import java.util.Arrays;
import java.util.StringTokenizer;

public class 가장많이받은선물 {

  public static void main(String[] args) {
    String[] friends = {"muzi", "ryan", "frodo", "neo"};
    String[] gifts = {"muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi",
        "frodo muzi", "frodo ryan", "neo muzi"};
    System.out.println(solution(friends, gifts));
  }

  public static int solution(String[] friends, String[] gifts) {
    int answer = 0;
    StringTokenizer st;
    int[][] giftMatrix = new int[friends.length][friends.length];
    int[][] giftScore = new int[friends.length][friends.length];
    int[] willGivenGift = new int[friends.length];

    for (String gift : gifts) {
      st = new StringTokenizer(gift);
      String from = st.nextToken();
      String to = st.nextToken();
      int indexOfFrom = Arrays.asList(friends).indexOf(from);
      int indexOfTo = Arrays.asList(friends).indexOf(to);
      giftMatrix[indexOfFrom][indexOfTo] += 1;
      giftScore[indexOfFrom][indexOfTo] += 1;
      giftScore[indexOfTo][indexOfFrom] -= 1;
    }

    for (int i = 0; i < friends.length; i++) {
      for (int j = 0; j < friends.length; j++) {
        if (i == j) continue;
        if (giftMatrix[i][j] > 0) {
          if (giftMatrix[i][j] > giftMatrix[j][i]) {
            willGivenGift[i] += 1;
          } else if (giftMatrix[i][j] == giftMatrix[j][i]) {//이게 두번 검증되므로 틀리는겨ㅜㅜ
            if (giftScore[i][j] > giftScore[j][i])
              willGivenGift[i] += 1;
          }
        } else if (giftMatrix[i][j] == 0) {
          if (giftMatrix[j][i] == 0) {
            if (giftScore[i][j] > giftScore[j][i])
              willGivenGift[i] += 1;
          }
        }
        if (answer < willGivenGift[i]){
          answer = willGivenGift[i];
        }
      }
    }

    return answer;
  }
}

 
수정한 코드(그래도 틀린 코드)

import java.util.Arrays;
import java.util.StringTokenizer;

public class 가장많이받은선물 {

  public static void main(String[] args) {
    String[] friends = {"muzi", "ryan", "frodo", "neo"};
    String[] gifts = {"muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi",
        "frodo muzi", "frodo ryan", "neo muzi"};
    System.out.println(solution(friends, gifts));
  }

  public static int solution(String[] friends, String[] gifts) {
    int answer = 0;
    StringTokenizer st;
    int[][] giftMatrix = new int[friends.length][friends.length];
    int[][] giftScore = new int[friends.length][friends.length];
    int[] willGivenGift = new int[friends.length];

    for (String gift : gifts) {
      st = new StringTokenizer(gift);
      String from = st.nextToken();
      String to = st.nextToken();
      int indexOfFrom = Arrays.asList(friends).indexOf(from);
      int indexOfTo = Arrays.asList(friends).indexOf(to);
      giftMatrix[indexOfFrom][indexOfTo] += 1;
      giftScore[indexOfFrom][indexOfTo] += 1;
      giftScore[indexOfTo][indexOfFrom] -= 1;
    }

    for (int i = 0; i < friends.length; i++) {
      for (int j = 0; j < friends.length; j++) {
        if (i == j) continue;
        if (giftMatrix[i][j] > giftMatrix[j][i]) {
          willGivenGift[i] += 1;
        } else if (giftMatrix[i][j] == giftMatrix[j][i]) {
          if (giftScore[i][j] > giftScore[j][i]) {
            willGivenGift[i] += 1;
          }
        }
      }
    }

    for (int i = 0; i < friends.length; i++) {
      if (answer < willGivenGift[i]) {
        answer = willGivenGift[i];
      }
    }
    return answer;
  }
}

 최종 수정 코드(맞음)

import java.util.Arrays;
import java.util.StringTokenizer;

public class 가장많이받은선물 {

  public static void main(String[] args) {
    String[] friends = {"muzi", "ryan", "frodo", "neo"};
    String[] gifts = {"muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi", "frodo muzi", "frodo ryan", "neo muzi"};
    System.out.println(solution(friends, gifts));
  }

  public static int solution(String[] friends, String[] gifts) {

    int answer = 0;
    StringTokenizer st;
    int[][] giftMatrix = new int[friends.length][friends.length];
    int[] giftScore = new int[friends.length];
    int[] willGivenGift = new int[friends.length];

    for (String gift : gifts) {
      st = new StringTokenizer(gift);
      String from = st.nextToken();
      String to = st.nextToken();
      int indexOfFrom = Arrays.asList(friends).indexOf(from);
      int indexOfTo = Arrays.asList(friends).indexOf(to);
      giftMatrix[indexOfFrom][indexOfTo] += 1;
      giftScore[indexOfFrom] += 1;
      giftScore[indexOfTo] -= 1;
    }

    for (int i = 0; i < friends.length; i++) {
      for (int j = 0; j < friends.length; j++) {
        if (i == j) continue;
        if (giftMatrix[i][j] > giftMatrix[j][i]) {
          willGivenGift[i] += 1;
        } else if (giftMatrix[i][j] == giftMatrix[j][i]) {
          if (giftScore[i] > giftScore[j]) {
            willGivenGift[i] += 1;
          }
        }
      }
    }

    for (int i = 0; i < friends.length; i++) {
      if (answer < willGivenGift[i]) {
        answer = willGivenGift[i];
      }
    }
    return answer;

  }
}
  1. 우선 저는 각자의 인원들이 서로 주고 받은 것을 기록하기 위한 giftMatrix와 선물지수를 저장해줄 giftScore, 그리고 받게 될 선물의 갯수를 저장해주는 willGivenGift를 2차원 배열로 인원수에 맞게 선언해주었습니다.
  2. 그 다음, String[] 배열의 friends를 읽어와 StringTokenizer로 공백을 기준으로 split 해주고, giftMatrix와 giftScore에 +1씩을 해주며 주어진 입력 값에 대해 정리를 했습니다.
  3. 그 다음 for문은 통해 값을 비교하며, A와 B 관계에서 A라는 사람이 준 선물이 B라는 사람이 준 선물보다 많다면 A에게 +1을, 만약 같다면 giftScore을 비교하여 willGivenGift에 값을 저장해주었습니다.
  4. 하지만, 값이 계속 다르게 나오거나 두배가 찍혀서 나왔었습니다. 그렇고 계속 머리가 아파오던 와중에, else if (giftMatrix[i][j] == giftMatrix[j][i]) 라는 문장에서 값이 두번 검증되어 결과값이 다르게 나오는 거 같다라는 피드백을 받았고 수정을 하였습니다.
  5. 알고보니 두번 검증되는 것은 물론이거니와 한번 검증한 내용이 그 다음의 if문에서 또 반복으로 검증되고 있는 문제점을 찾았습니다. 그리하여 복잡한 for문 구조를 보다 간단하게 개선하였습니다.
  6. 그리하여 맞은 줄 알았던 것이 틀려 다시 수정하였습니다. 이중으로 검증 되는 것 때문이 아니었습니다. 제가 첫번째와 두번째 코드를 보면 giftScore을 2차원 배열로 생성을 해놓은 것을 알 수 있습니다.
  7. 이렇게 되면 검증하는 단계에서 오류가 생기게 됩니다. 예를 들어서, A와 B라는 사람 사이의 선물을 주려고 할 때, 두 사람이 주고 받은 선물이 같다면 선물지수를 확인하게 되는데요. 이 때 2차원 배열로 생성되었던 giftScore에서 A 한 사람의 선물지수와 B 한 사람의 선물 지수를 비교하는 것이 아닌, A가 B에게 혹은 B가 A에게 주었던 결과를 토대로 생성된 선물지수를 비교하게 되므로 오류가 발생할 수 밖에 없었습니다.
  8. 그 결과, 저는 최종적으로 giftScore을 2차원 배열이 아닌 1차원 배열로 수정을 하고 각각의 사람마다 갖고 있는 인덱스를 위치값으로 생각하고 다시 수정하였습니다. 예를 들어 1번 사람이 2번 사람에게 선물을 주었다면, giftScore에서 1번 사람이 갖고 있는 배열의 값에 +1을 해주고 2번 사람이 갖고 있는 배열의 값에 -1을 해주어 for문에서 검증해주었습니다.😭

이렇게 거의 몇번의 수정하는 과정과 많은 시간이 걸려 문제를 완성할 수 있었습니다. 막상 코테를 풀어보며 막막하고 빨간줄이 뜨거나 원하는 결과값이 나오지 않으면 화도 나고 조금은 자괴감도 들긴 하지만, 완성하고 나서의 성취감과 뿌듯함을 느끼며 그것만큼의 도파민도 또한 어디가서 찾지 못할 것 같습니다. 이상으로 글 마치겠습니다. 감사합니다.

 

https://github.com/bottomsUp-99?tab=repositories

 

bottomsUp-99 - Overview

Backend Developer. bottomsUp-99 has 10 repositories available. Follow their code on GitHub.

github.com

 

728x90
반응형