Java - 신고 결과 받기, JadenCase 문자열 만들기, 카펫

Java

신고 결과 받기

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/92334
• 게시판 불량 이용자를 신고하고 처리 결괄르 메일로 발송하는 시스템을 아래처럼 개발하려고 함
  • 각 유저는 한 번에 한 명의 유저를 신고할 수 있음
    • 신고 횟수에 제한은 없으며 서로 다른 유저를 계속해서 신고할 수 있음
    • 한 유저를 여러 번 신고할 수도 있지만 동일한 유저에 대한 신고 횟수는 1회로 처리됨
  • k번 이상 신고된 유저는 게시판 이용이 정지되며 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송함
    • 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송함
• 다음은 전체 유저 목록이 ["muzi", "frodo", "apeach", "neo"]이고 k = 2(2번 이상 신고당하면 이용 정지)인 경우의 예시임

• 각 유저벌로 신고당한 횟수가 첫 번째 이미지와 같을 때 두 번째 이미지와 같이 2번 이상 신고당한 frodo와 noe의 게시판 이용이 정지됨
• 이때 각 유저별로 신고한 아이디와 정지된 아이디를 정리한 이미지가 세 번째 이미지이며 muzi는 처리 결과 메일을 2회, frodo와 apeach는 각각 처리 결과 메일을 1회씩 받게 됨
• 이용자의 ID가 담긴 문자열 배열 id_list, 각 이용자가 신고한 이용자의 ID 정보가 담긴 문자열 배열 repost, 정지 기준이 되는 신고 횟수 k가 매개변수로 주어질 때 각 유저별로 처리 결과 메일을 받는 횟수를 담아 reutrn 하는 함수를 완성하기

제한조건

• 2 <= id_list의 길이 <= 1,000
  • 1 <= id_list의 원소 길이 <= 10
  • id_list의 원소는 이용자의 id를 나타내는 문자열이며 알파벳 소문자로만 이루어져 있고 같은 아이디가 중복되지 않음
• 1 <= report의 길이 <= 200,000
  • 3 <= report의 원소 길이 <= 21
  • report의 원소는 "이용자id 신고한id"형태의 문자열이며 id는 알파벳 소문자로만 이루어져 있으며 이용자id와 신고한id는 공백(스페이스)하나로 구분되어 있음
  • 예를들어 "muzi frodo"의 경우 muzi가 frodo를 신고했다는 뜻임
  • 자기 자신을 신고하는 경우는 없음
• 1 <= k <= 200, k는 자연수임
• return 하는 배열은 id_list에 담긴 id 순서대로 각 유저가 받은 결과 메일 수를 담아야 함

입출력 예시

풀이

map활용

import java.util.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        Map<String, Set<String>> reportedMap = new HashMap<>();
        Map<String, Integer> mailCount = new HashMap<>();

        Set<String> uniqueReports = new HashSet<>(Arrays.asList(report));

        for (String rep : uniqueReports) {
            String[] split = rep.split(" ");
            String reporter = split[0];
            String reported = split[1];

            reportedMap.computeIfAbsent(reported, v -> new HashSet<>()).add(reporter);
        }

        for (Map.Entry<String, Set<String>> entry : reportedMap.entrySet()) {
            if (entry.getValue().size() >= k) {
                for (String reporter : entry.getValue()) {
                    mailCount.put(reporter, mailCount.getOrDefault(reporter, 0) + 1);
                }
            }
        }

        int[] answer = new int[id_list.length];
        for (int i = 0; i < id_list.length; i++) {
            answer[i] = mailCount.getOrDefault(id_list[i], 0);
        }

        return answer;
    }
}

 

필요한 자료구조 생성

• 해당 문제를 풀기 위해서는 신고결과를 담는 자료 구조와 메일을 보내야할 대상을 담는 자료구조 2개가 필요하다고 생각했다.
• 그리고 해당 자료구조들을 가장 효율적으로 계산할 수 있는 것은 Map 자료구조라고 생각하여 신고대상을 담는 자료구조는 Map<String, Set<String>>으로 구성하고, 메일을 보내야하는 갯수를 담는 자료구조는 Map<String, Integer>로 구성했다
• Map<String, Set<String>>으로 value를 Set 자료 구조로 정한 이유는, 유저가 여러명을 신고할 수 있으므로 신고 대상인 key값에 대해 여러 유저를 저장해야하기 때문이며, 여러번 신고해도 1번으로 카운트 되기 때문에 중복값을 허용하지 않는 Set으로 정했다. 

신고내역 가공 및 신고결과 저장

• 그 다음 신고 기록인 report에 대해 중복 신고 내역을 제거하기 위해 new HashSet<>(Arrays.asList(report))를 통해서 배열 -> List -> Set 변경하였다
• 그 다음 iterator를 통해 중복을 제거한 Set 자료구조의 요소를 split(" ")으로 분해한 다음 첫 번째 요소를 신고자, 두 번째 요소를 신고당한 대상으로 분리하여 신고 결과를 담는 자료구조인 reportedMap에 데이터를 저장한다
• 이때 key값으로 입력된 신고 당한 대상이 Map에 없으면 Set 자료구조를 생성해야하기 때문에 computeIfAbsent() 메서드를 활용하여 Set을 생성하고 신고 대상을 추가하도록 했다.
• 만약 Map의 key에 신고 당한 대상이 이미 있다면 해당 key에 대응하는 Set자료구조가 반환되어 Set에 신고자를 추가하는 구조이다.
• 해당 반복을 모두 완료하면 신고결과 Map이 채워진다

신고 결과를 분석하여 mailCount를 채우기

• 신고 결과 Map이 전부 채워졌다면 reportedMap.entrySet()으로 <Key, Value>가 하나로 묶여있는 Set<Entry> 구조로 반환하여 이를 순회하여 하나씩 꺼낸다.
• 그 다음 해당 entry의 value의 사이즈가 게시판 이용 정지 기준인 k를 넘어가게 된다면 entry.getValue()로 해당 entry에 대응되는 신고자들을 하나씩 뽑아서 mailCount에 저장한다
• 이때 신고자를 key값으로하고 getOrdefault()메서드를 활용하여 최초 신고대상이라면 값을 1로 저장하고 이미 신고당한 대상이라면 기존 값에 1을 추가한다
• 모든 entry를 순회하게 되면 메일을 보내야할 대상과 횟수가 담인 mailCount가 완성된다

결과 반환 배열 채우기

• 그 다음 결과를 담기 위해 회원의 갯수만큼 int[]배열을 생성하고 반복문을 통해서 배열의 값을 채운다
• 이때 mailCount.getOrDefault()를 통해서 유저가 신고한 내역이 없다면 0으로 값을 채우고, 내역이 있다면 해당 값을 꺼내서 배열에 채워서 문제를 해결한다

최적화 버전

import java.util.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        int n = id_list.length;

        Map<String, Integer> idIndexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            idIndexMap.put(id_list[i], i);
        }

        Map<String, Set<String>> reportedMap = new HashMap<>();
        Set<String> uniqueReports = new HashSet<>(Arrays.asList(report));

        for (String rep : uniqueReports) {
            String[] split = rep.split(" ");
            String reporter = split[0];
            String reported = split[1];

            reportedMap.computeIfAbsent(reported, v -> new HashSet<>()).add(reporter);
        }

        int[] mailCount = new int[n];

        for (Map.Entry<String, Set<String>> entry : reportedMap.entrySet()) {
            if (entry.getValue().size() >= k) {
                for (String reporter : entry.getValue()) {
                    int idx = idIndexMap.get(reporter);
                    mailCount[idx]++;
                }
            }
        }

        return mailCount;
    }
}

• 기존 방식은 메일 발송 대상을 Map<String, Integer>로 저장한 뒤 다시 id_list를 전부 순회하면서 getOrDefault()로 값을 꺼내야 했다.
• 하지만 회원 ID(String)와 인덱스를 미리 매핑한 Map<String, Integer>를 만들어두면,별도로 Map을 순회할 필요 없이, 신고 처리 중에 해당 유저의 인덱스를 직접 참조할 수 있기 때문에 int[] 배열에 직접 카운팅할 수 있게 된다
• 이렇게 하면 Map을 하나 생성하는 대신 int[] 하나로 해결할 수 있어 더 간단하며 더 빠른 연산을 할 수 있게 된다
• 이러한 최적화를 바로 생각하기에는 무리가 있어 알고리즘 공부와 사례들 통해 공부가 좀 더 필요하다고 생각했다.

---

JadenCase 문자열 만들기

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/12951
• JadenCase란 모든 단어의 첫 문자가 대문자이고 그 외의 알파벳은 소문자인 문자열을 뜻함
• 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면됨
• 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수를 완성

제한조건

• s는 길이 1이상 200 이하인 문자열
• s는 알파벳과 숫자, 공백 문자(" ")로 이루어져 있으며 숫자는 단어의 첫 문자로만 나옴
• 공백문자가 연속해서 나올 수 있으며 숫자로만 이루어진 단어는 없음

입출력 예시

풀이

toCharArray() 활용

class Solution {
    public String solution(String s) {
        StringBuilder answer = new StringBuilder();
        boolean flag = true;

        for (char c : s.toCharArray()) {
            if (flag) {
                answer.append(Character.toUpperCase(c));
            } else {
                answer.append(Character.toLowerCase(c));
            }
            flag = (c == ' ');
        }

        return answer.toString();
    }
}

• 처음에는 s.split(" ", -1)을 통해 문제를 풀다가 코드가 너무 이상해져서 효율적인 코드를 찾아봤는데 위와 같은 방식을 발견하여 풀이를 해보고자 한다.
• 우선 반복문 내부에서 문자열을 생성해야하므로 성능이 좋은 StringBuilder를 생성하고 boolean 타입 변수를 선언하여 반복문에서 꺼낼 문자가 단어의 시작인지를 확인하도록 했다.
• 그 다문 문자열 s를 split()이 아니라 toCharArray()를 활용하여 문자 배열로 변경하고 flag가 true이면 첫 문자이므로 Character.toUpperCase(c)를 통해 대문자로 변환한 다음 StringBuilder에 추가한다.
• 이때 숫자를 처리해야 할 것 같지만 숫자는어차피 대문자로 변환하든 소문자를 변환하든 의미가 없기 때문에 첫 문자는 무조건 대문자로변환해도 상관이 없다.
• 만약 flag가 false이면 else문으로 이동하여 이후에 반환되는 문자열은 모두 Character.toLowerCase(c)로 소문자로 변환하여 StringBuilder에 추가한다.
• 바로 반복문을 끝내는 것이 아니라 c가 ' ' 빈 공백 문자이면 flag를 true로 만들어서 다음 문자가 첫 문자임을 알리도록 조건을 추가해주면 이문제가 성능도 챙기고 가독성도 좋게 문제를 해결할 수 있다.

다른 풀이

class Solution {
  public String solution(String s) {
        String answer = "";
        String[] sp = s.toLowerCase().split("");
        boolean flag = true;

        for(String ss : sp) {
            answer += flag ? ss.toUpperCase() : ss;
            flag = ss.equals(" ") ? true : false;
        }

        return answer;
  }
}

• 내가 실패했던 split("")으로 문제를 아주 깔끔하게 해결한 케이스가 있어 가져왔다.
• 물론 문자열을 직접 다루었기 때문에 성능면에서는 당연히 문자 배열로 변환하고 StringBuilder를 활용하는 것이 좋다
• 우선 전달받은 문자열을 모두 s.toLowerCase()를 통해 소문자로 변환한 다음 split("")으로 잘라서 String[]에 저장한다.
• 이 행위 하나로 이후에는 문자의 시작인지 확인하고 시작 문자라면 대문자로 변환하고 문자열에 추가만 하면 되기 때문에 조건문이 매우 깔끔해진다.(이 아이디어를 생각해내지 못했다)
• 이후에는 각 단어에서 꺼낸 문자가 " " 공백 문자열이라면 flag를 true로 바꾸고 공백 문자열이 아니면 이어진 문자이므로 false로 변경하여 문제를 해결한다.

---

카펫

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/42842
• 카펫의 갈색 격자의 수가 brown, 노란색 격자의 수가 yellow로 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아return하는 함수를 완성
• 카펫의 테두리 1줄은 brown이고, 중앙에는 yellow임

제한사항

• 갈색 격자의 수 brown은 8이상 5,000 이하인 자연수임
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수임
• 카펫의 가로 길이는 세로 길이와 같거나 세로 길이보다 김

입출력 예

 

 

풀이

완전탐색 풀이

class Solution {
    public int[] solution(int brown, int yellow) {
        
        int x = 0;
        int y = 3;
        int totalSize = brown + yellow;
        
     while (y <= totalSize) {
            if (totalSize % y == 0) {
                x = totalSize / y;  
                if ((x - 2) * (y - 2) == yellow) {
                    break;
                }

            }
            y++;  
          
        }         
        return new int[] {x, y};
    }
}

• 대표적인 완전탐색 문제라고 하며 수학적인 규칙으로 문제를 간단히 풀 수 있다고 한다.
• 우선 주어진 brown과 yellow를 덧셈 연산하면 카펫(사각형)의 전체 사이즈를 구할 수 있다.
• 카펫의 테두리 1줄을 제외하고 내부 공간을 만들려면 세로가 최소한 3이 되어야하기 때문에 y(사각형의 높이)는 최소 3이 되어야 하기 때문에 y의 값을 3으로 두고 y가 totalSize가 될 때까지 y의 값을 1씩 증가시키며 반복문을 돌린다.
• x(가로의 길이)를 구하기 위해 totalSize % y의 나머지가 0이라면 totalSize / y를 통해 x의 길이를 구한다.
  • totalSize를 y로 나누었을 때 나머지가 남는 수는 내부 조건의 로직을 계산할 필요가 없음
• 그 다음 주어진 yellow가 (x - 2) * (y - 2)와 같다면 즉시 반복문을 멈추고 바로 x, y의 값을 배열에 반환하여 문제를 해결한다.
  • x와 y의 값을 -2 연산을 한 이유는 카펫 테두리의 1줄만 갈색이기 때문에 가로길이의 양끝과, 세로길이의 양끝을 제거해야 노란색의 영역이 된다.
  • 반복문을 통해 구한 x와 y의 값을 토대로 공식을 통해 yellow의 값과 맞는지 비교하면 x와 y가 제대로 구해졌는지 알 수 있다

다른 풀이

근의 공식 풀이

class Solution {
    public int[] solution(int brown, int red) {
        int a = (brown + 4) / 2;                 // x + y
        int b = red + 2 * a - 4;                 // x * y
        int sqrt = (int) Math.sqrt(a * a - 4 * b);

        int x = (a + sqrt) / 2;
        int y = (a - sqrt) / 2;

        return new int[]{x, y};
    }
}

• 해당 문제는 근의 공식으로도 문제를 풀 수 있다고 한다.
• 이 문제를 보고 알맞은 수학 공식을 떠올린다면 위 처럼 공식을 적용하여 코테 문제를 풀면 깔끔하게 할결할 수 있다