지니로그

오늘의 학습 키워드

배열

알고리즘 문제

• LeetCode Medium 1282. Group the People Given the Group Size They Belong To
• https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/description/?source=submission-ac

공부한 내용

다른 풀이를 보고 분석

오늘의 회고

처음 시도

• 처음 내가 시도했던 방식은 List만을 사용해서 풀었다.
  1. groupSizes 배열 전체 요소를 하나씩 읽어서 size만큼 새로운 List에 담아서 그룹핑을 한다.
  2. 그룹 배열을 만들 때, 그룹에 담은 groupSizes 해당 요소는 0으로 만든다.
  3. 카운트 변수를 두어 size만큼 카운트가 되면 다음 요소로 넘어가도록 했다.
• 그런데 내가 어렵게 꼬아서 생각한 것 같았다. 여기까지는 좋았는데.. 왜 처음에 괜히 어렵게 재귀로 풀려고 했었는지 런타임 에러나고, 케이스마다 안되는 게 생기고 로직이 복잡해졌다.
• 그래서 다시 처음으로 돌아가 Map에 size별로 리스트를 담아서 subList로 나누기로 생각했다.

해결

• groupSizes 배열 전체를 loop 돌면서 size로 key를 size가 같은 것끼리 value에 리스트로 HashMap에 저장했다.
• HashMap에 모두 저장했으면, HashMap의 key를 꺼내서 해당 size만큼 다시 List로 분리해서 result 리스트에 추가했다.

문제 풀이

HashMap으로 푼 나의 풀이

import java.util.*;
class Solution {
    Map<Integer, List<Integer>> map;

    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();

        // grouping (key: groupSize / val: index list) 
        for (int i = 0; i < groupSizes.length; i++) {
            List<Integer> values;
            if (map.containsKey(groupSizes[i])) {
                values = map.get(groupSizes[i]);
            } else {
                values = new ArrayList<>();
            }
            values.add(i);
            map.put(groupSizes[i], values);
        }
        
        // partitioning
        for (int key : map.keySet()) {
            List<Integer> list = map.get(key);
            for (int i = 0; i < list.size(); i+= key) {
                result.add(list.subList(i, Math.min(i+key, list.size())));
            }
        }

        return result;
    }
}

처음에 List로만 풀려고 했던 내 생각과 유사한 풀이

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> result = new ArrayList<>();
        for(int i = 0; i<groupSizes.length; i++){
            if(groupSizes[i] == 0){
                continue;
            }
            int k = i;
            int z = groupSizes[i];
            int j = z;
            List<Integer> temp = new ArrayList<>();
            while(j>0){
                if(groupSizes[k]==z){
                    temp.add(k);
                    groupSizes[k]=0;
                    j--;
                }
                k++;
            }
            result.add(temp);
        }
        return result;
    }

}

이렇게도 풀 수 있구나

import java.util.ArrayList;
import java.util.List;

class Solution extends java.util.AbstractList<List<Integer>> {
  int[] gs;
  List<List<Integer>> ans;

  public List<List<Integer>> groupThePeople(int[] groupSizes) {
    this.gs = groupSizes;
    return this;
  }

  @Override
  public List<Integer> get(int index) {
    if (ans == null)
      this.size();
    return ans.get(index);
  }

  @Override
  public int size() {
    if (ans == null) {
      ans = new ArrayList<>();
      var map = new java.util.HashMap<Integer, List<Integer>>();
      for (int i = 0; i < gs.length; i++) {
        List<Integer> g = map.computeIfAbsent(gs[i], z -> new ArrayList<>());
        g.add(i);
        if (g.size() == gs[i])
          ans.add(map.remove(gs[i]));
      }
    }
    return this.ans.size();
  }
}

오늘의 학습 키워드

배열

알고리즘 문제

• LeetCode Medium  1476. Subrectangle Queries
• https://leetcode.com/problems/subrectangle-queries/description/

오늘의 회고

처음 시도

• 문제를 보니 주어진 2차원 배열의 값을 리턴해주는 메서드와 값을 업데이트해주는 메서드를 만드는 게 목표였다.
•  

해결

• 바로 클래스에 2차원 배열 변수 private 하게 만들어서 해당 변수로 사용하도록 클래스를 만들었다.
• 2차원 배열 값을 좌표를 input 받아서 반복문을 돌려 row1, row2는 세로 방향 인덱스 / col1, col2는 가로 방향 인덱스이므로 처음에 row로 반복문을 돌리고 그 안에서 col로 반복문을 돌려서 row,col 좌표에 newValue로 업데이트 해주었다.

문제 풀이

class SubrectangleQueries {
    private int[][] rectangle;

    public SubrectangleQueries(int[][] rectangle) {
        this.rectangle = rectangle;
    }
    
    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                rectangle[i][j] = newValue;
            }
        }
    }
    
    public int getValue(int row, int col) {
        return rectangle[row][col];
    }
}

/**
 * Your SubrectangleQueries object will be instantiated and called as such:
 * SubrectangleQueries obj = new SubrectangleQueries(rectangle);
 * obj.updateSubrectangle(row1,col1,row2,col2,newValue);
 * int param_2 = obj.getValue(row,col);
 */