9월 2주차 문제 [ 1단계 ]

[Tokwasp]

📢 이번 주 알고리즘 스터디 문제

이번 주에는 총 6문제를 풉니다.
(정답률은 프로그래머스 기준)

---

📌 문제 목록 [ 1단계 ]

번호	문제	정답률	링크
1	택배 상자 꺼내기	36%	🔗 바로가기
2	신고 결과 받기	41%	🔗 바로가기

---

🗓️ 발표

• 시간: 금요일 오전 10시
• 방식: 각자 풀이 공유 + 코드 리뷰

---

🚨 벌금 규칙

• 문제를 풀지 않은 경우 → 💸 1만 원

---

🔥 이번 주도 화이팅입니다!

[pia01190]

📌 신고 결과 받기

• 유저 id와 유저 id가 신고한 id들을 저장하기 위해 Map<String, Set<String>> 사용
• 각 유저는 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리 -> Set<String> 사용

import java.util.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        
        // 유저 id와 유저 id가 신고한 id 저장
        Map<String, Set<String>> map = new HashMap<>();
        for (String id : id_list) {
            map.put(id, new HashSet<>());
        }
        
        for (String r : report) {
            String[] reports = r.split(" ");
            String reporter = reports[0];
            String reported = reports[1];
    
            map.get(reporter).add(reported);
        }
        
        // 유저 id와 신고당한 횟수 저장
        Map<String, Integer> idMap = new HashMap<>();
        for (String id : id_list) {
            idMap.put(id, 0);
        }
        
        for (Set<String> reportedSet : map.values()) {
            for (String reported : reportedSet) {
                idMap.put(reported, idMap.get(reported) + 1);
            }
        }
        
        // 정지된 id 리스트
        List<String> reportedList = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : idMap.entrySet()) {
            if (entry.getValue() >= k) {
                reportedList.add(entry.getKey());
            }
        }
        
        // 유저 id와 메일 받은 횟수 저장
        int[] answer = new int[id_list.length];
        for (int i = 0; i < id_list.length; i++) {
            String id = id_list[i];
            int count = 0;
            
            for (String reported : map.get(id)) {
                if (reportedList.contains(reported)) {
                    count++;
                }
            }
            
            answer[i] = count;
        }
        
        return answer;
    }
}

📌 택배 상자 꺼내기

• 박스 배치
  • 짝수 행: 왼쪽 → 오른쪽 순서로 번호 넣기
  • 홀수 행: 오른쪽 → 왼쪽 순서로 번호 넣기
  • boxNum > n 이면 break

class Solution {
    public int solution(int n, int w, int num) {
        int height = (n + w - 1) / w;
        int[][] box = new int[height][w];
        int boxNum = 1;
        int row = 0;
        int col = 0;
        
        // box 배열에 boxNum 넣기
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < w; j++) {
                if (boxNum > n) {
                    break;
                }
                
                if (i % 2 == 0) {
                    box[i][j] = boxNum++;
                } else {
                    box[i][w - 1 - j] = boxNum++;
                }
            }
        }
        
        // num 상자가 위치한 좌표 구하기
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < w; j++) {
                if (box[i][j] == num) {
                    row = i;
                    col = j;
                    break;
                }
            }
        }
        
        // 꺼내야 하는 상자의 총 개수 구하기
        int count = 0;
        for(int i = row; i < height; i++) {
            if(box[i][col] != 0) {
                count++;
            }
        }
        
        return count;
    }
}

[Tokwasp]

[ ⚡ 택배 상자 꺼내기 ]

1. 박스 위치 탐색

• 박스의 행(row), 열(column) 좌표를 파악

2. 규칙성 분석

• 박스가 쌓이는 패턴 관찰
• 홀수 증가 규칙 확인: 1, 3, 5, 7 ...

3. 박스 개수 계산

• 현재 위치에서 올라 가며 박스 개수 계산

public class TakeOutDeliveryBox {
    public int solution(int boxCount, int colLength, int target) {
        // 박스 인덱스 찾기
        int targetRow = (target - 1) / colLength;

        int remain = (target - 1) % colLength;
        int targetCol = targetRow % 2 == 0 ? remain : colLength - 1 - remain;

        // 다음 층으로 올라가기 위해서 번호를 얼만큼 더해야 하는가?
        List<Integer> sumList = new ArrayList<>();
        int initNum = 1;
        sumList.add(initNum);

        for (int i = 1; i < colLength; i++) {
            initNum += 2;
            sumList.add(initNum);
        }

        // 박스 치우기
        int row = targetRow;
        int count = 0;

        while (target <= boxCount) {
            if (row % 2 == 1) {
                target += sumList.get(targetCol);
            } else {
                target += sumList.get(colLength - 1 - targetCol);
            }
            row++;
            count++;
        }

        return count;
    }
}

---

[ 정석 풀이 ]

• 문제는 올라 가지만 X축 대칭으로 내려 가는 방법
• 최대 100개의 상자 이고, 열의 크기를 알기 때문에 row 확인 가능

class Solution {
    public int solution(int boxCount, int colLength, int target) {
        int rowSize = (int) (100 / colLength) + 1;
        int[][] boxArr = new int[rowSize][colLength];
        
        // 입력 받기
        for(int row = 0; row < boxArr.length; row++){
            int boxNum = (row + 1) * colLength;
            
            if(row % 2 == 0){
                boxNum = boxNum - colLength + 1;
                
                for(int col = 0; col< boxArr[0].length; col++){
                    boxArr[row][col] = boxNum++;
                } 
                
            } 
            
            if(row % 2 == 1){
               for(int col = 0; col< boxArr[0].length; col++){
                    boxArr[row][col] = boxNum--;
                } 
            }
        }
        
        // target 박스 위치 찾기
        int startRow = 0;
        int startCol = 0;
        for(int row = 0; row < boxArr.length; row++){
            for(int col = 0; col < boxArr[0].length; col++){
                if(boxArr[row][col] == target){
                    startRow = row;
                    startCol = col;
                }
            }
        }
        
        // 위로 올라가며 박스 세기
        int count = 0;
        for(int row = startRow; row < boxArr.length; row++){
            if(boxArr[row][startCol] <= boxCount){
                count++;
            }
         }
        return count;
    }
}

---

📩 신고 결과 받기

[ 신고 대상과 신고한 사람들 ]

 Map<String, Set<String>> reportMap;

• Key: 신고당한 유저 ID
• Value: 해당 유저를 신고한 유저들의 Set
• Set을 사용 이유: 동일 유저의 신고는 불가능

Map<String, Integer> userIndexMap;

• 정지 대상인 경우 신고 회원에게 메일 전송

---

class Solution {
    public int[] solution(String[] idList, String[] reports, int limit) {
        Set<String> idSet = new HashSet<>();
        Map<String, Set<String>> reportMap = new HashMap<>();
        Map<String, Integer> indexMap = new HashMap<>();
        
        // 이름자 id 정리
        for(int i = 0; i < idList.length; i++){
            String id = idList[i];
            idSet.add(id);
            reportMap.put(id, new HashSet<>());
            indexMap.put(id, i);
        }
        
        // 신고 하기
        for(int i = 0; i < reports.length; i++){
            String[] reportArr = reports[i].split(" ");
            String person = reportArr[0];
            String target = reportArr[1];
            
            // 이름 명단에 없으면 패스
            if(!idSet.contains(person) || !idSet.contains(target)) continue;
            
            // 신고 안한 사람이면 추가
            Set<String> reporterSet = reportMap.get(target);
            reporterSet.add(person);
        }
        
        int[] mailArr = new int[idList.length];
        
        // 메일 전송
        for(int i = 0; i < idList.length; i++){
            String id = idList[i];
            
            Set<String> reporterSet = reportMap.get(id);
            
            // 메일 전송 대상
            if(reporterSet.size() >= limit){
                for(String reporter : reporterSet){
                    int index = indexMap.get(reporter);
                    mailArr[index] += 1;
                }
            }
        }
        return mailArr;
    }
}

[dbrkdgus00]

신고 결과 받기

해결방법

• 신고 내역 정리
  유저가 누구를 신고했는지 Map과 Set을 활용해 중복 없이 저장.

• 정지여부 판단
  신고당한 유저의 신고자 수가 k 이상이면 정지 대상 처리.

• 메일 발송 처리
  정지된 유저를 신고한 유저에게 메일 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> idIndexMap = new HashMap<>();
        for (int i = 0; i < id_list.length; i++) {
            idIndexMap.put(id_list[i], i);
        }
        
        // 각 유저가 신고당한 사람 -> 신고한 사람 목록 저장할 Map
        Map<String, Set<String>> reportedBy = new HashMap<>(); // 중복 방지를 위해 Set
        // 일단 모든 유저에 대한 빈 Set 만듬
        for (String id : id_list) {
            reportedBy.put(id, new HashSet<>());
        }
        
        // 신고 기록 하나씩 처리
        for (String rep : report) {
            // 공백으로 나눠야 [신고자, 신고당한자] 순서
            String[] split = rep.split(" ");
            String reporter = split[0]; // 신고한 사람
            String reported = split[1]; // 신고당한 사람
            
            // 신고 당한 사람의 Set에 신고자 추가
            reportedBy.get(reported).add(reporter);
        }
        
        // 이제 각 유저가 신고당한 횟수를 체크해서 정지 여부 판단
        for (String reportedUser : reportedBy.keySet()) {
            Set<String> reporters = reportedBy.get(reportedUser);
            
            // 만약 신고당한 횟수가 k 이상이면 정지
            if (reporters.size() >= k) {
                // 이 유저를 신고 했던 사람들은 메일 1통씩 받음
                for (String reporter : reporters) {
                    // 메일 받을 사람의 인덱스를 찾음
                    int idx = idIndexMap.get(reporter);
                    
                    // 결과 배열에서 메일 수 + 1
                    answer[idx]++;
                }
            }
        }
        return answer;
    }
}

택배 상자 꺼내기

해결방법

• 2차원 배열에 상자들을 실제로 배치
  상자를 번호 순서대로 하나씩 지그재그로 넣는다.

• 내가 꺼내려는 상자의 위치(row, col)를 찾는다.
  배열을 처음부터 끝까지 돌면서, 번호가 num인 상자의 줄과 칸을 찾는다.

• 그 위층들에 같은 위치(col)에 상자가 있는지 확인
  num이 있는 위치보다 위에 있는 줄들을 하나씩 올라가면서
  그 칸에 상자가 있으면 꺼내야 하므로, 개수를 1씩 늘린다.

• 자기 자신도 무조건 꺼내야 하므로 count는 1부터 시작

class Solution {
    public int solution(int n, int w, int num) {
        // 상자를 배치할 2차원 배열 만듬
        // 몇 층이 필요한지 먼저 계산 (올림 처리)
        int h = (n + w - 1) / w;
        
        // 상자 배치 배열 만듬 : h행w열
        int[][] map = new int[h][w];
        
        int box = 1;                // 상자 번호는 1부터 시작
        boolean leftToRight = true; // 줄 방향 : 처음엔 왼 -> 오
        
        // 상자들을 한 줄씩 지그재그로 넣기
        for (int i = 0; i < h; i++) {
            if (leftToRight) {
                for (int j = 0; j < w && box <= n; j++) {
                    map[i][j] = box;
                    box++;
                }
            } else {
                for (int j = w - 1; j >= 0 && box <= n; j--) {
                    map[i][j] = box;
                    box++;
                }
            }
            // 다음 줄은 방향 반대로
            leftToRight = !leftToRight;
        }
        // 꺼내려는 상자 num의 위치(row, col) 찾기
        int targetRow = -1;
        int targetCol = -1;
        
        for (int i = 0; i < h; i ++) {
            for (int j = 0; j < w; j++) {
                if (map[i][j] == num) {
                    targetRow = i;
                    targetCol = j;
                }
            }
        }
        
        // 위로 올라가며 같은 col 에 상자가 있으면 count++
        int count = 1;
        
        for (int i = targetRow + 1; i < h; i++) {
            if (map[i][targetCol] != 0) {
                count++;
            }
        }
        return count;
    }
}