[백준/17140] 이차원 배열과 연산 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/17140
• 분류 : Simulation
• 풀이 시간 : 40분

문제 해설

1. 배열 A = 3 x 3
2. 1초마다 연산 수행
3. if (행 길이 >= 열 길이) R정렬 수행
4. else C정렬 수행
5. 정렬 방법
   1. 0은 무시
   2. 하나의 행 또는 열에서 숫자의 등장 횟수 카운트
   3. 등장 횟수 기준 오른차순 정렬
   4. 등장 횟수가 같으면 숫자 기준 오름차순 정렬
   5. 숫자 -> 등장 횟수 순서대로 배열에 한칸씩 넣음
   6. 넣을 때 길이가 100 넘어가면 그 뒤로부터 안넣음
6. 100초 안에 A[r][c] == k 만족할 때 까지 연산 수행
7. 100초안에 만족 못하면 -1 출력

Solution

풀이 접근 방법

1. 숫자의 등장 횟수 카운트 = HashMap 이용

   • key : 등장하는 숫자
   • value : 숫자가 몇번 나왔는지
   • map.getOrDefaultValue() 사용
     • getOrDefaultValue(key 값, 해당 key값에 해당하는 value 없을 때 리턴시킬 값)

2. 등장 횟수 기준 오름차순 = Value 기준 HashMap 오름차순 정렬 = Entry List 사용

3. 0은 등장 횟수에서 제외

   • HashMap에 넣을 때 제외시킴

   • 만약 빈칸 == 0 이라 생각하고 0이 나오면 반복문 종료 해버리면

     • 두번째 행이 첫번째 행보다 길 경우, 열 정렬 때 두번째부터 값이 있는 첫번째에서 0을 만나서 종료해버림

       // 5번째 열 정렬 시 뒤에 3이 있지만 0을 만나서 3을 카운트하지 못하고 종료해버림
       2 1 1 2 0 0 
       1 1 2 1 3 1
       3 3 0 0 0 0

   • 이 처리 안해주면 "예제 4입력 4"에서 틀림

4. 행의 길이는 길어질 수도, 짧아질 수도 있다 = HashMap에 배열 값 넣고 난 후 미리 0으로 초기화

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;

public class Main_17140 {
  static int r, c, k;
  // 배열의 최대 길이가 100을 넘어가지 않게 미리 설정
  static int MAX_SIZE = 100;
  // 각 열의 길이 중 제일 큰 값 저장 변수
  static int COL_SIZE = 3;
  // 각 행의 길이 중 제일 큰 값 저장 변수
  static int ROW_SIZE = 3;
 	// A 배열
  static int[][] matrix;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    String[] info = br.readLine().split(" ");

    // r, c는 1부터 시작하여 -1
    r = Integer.valueOf(info[0]) - 1;
    c = Integer.valueOf(info[1]) - 1;
    k = Integer.valueOf(info[2]);
    // 행, 열이 100이 넘어가면 저장 안하니깐 미리 최대 길이까지 초기화시켜놓음
    matrix = new int[MAX_SIZE][MAX_SIZE];

    for (int i = 0; i < 3; i++) {
      info = br.readLine().split(" ");

      for (int j = 0; j < 3; j++) {
        matrix[i][j] = Integer.valueOf(info[j]);
      }
    }

    bw.write(solution() + "\n");
    bw.flush();
    bw.close();
  }

  static int solution() {
    int time = 0;

    while (matrix[r][c] != k) {
      if (ROW_SIZE >= COL_SIZE) {
        doRCalc();
      } else {
        doCCalc();
      }

      // 100초가 지났는데도 못찾으면 -1
      if (++time > 100)
        break;
    }

    return time > 100 ? -1 : time;
  }

  // 모든 행 정렬
  static void doRCalc() {
    // 각 행 정렬 시 열의 최대 크기가 달라짐
    int newColSize = COL_SIZE;

    for (int x = 0; x < ROW_SIZE; x++) {
      // 각 수의 등장 횟수를 저장하기 위한 Map 생성
      HashMap<Integer, Integer> dict = new HashMap<Integer, Integer>();

      for (int y = 0; y < COL_SIZE; y++) {
        // 0은 횟수 카운트에서 제외
        if (matrix[x][y] == 0)
          continue;

        dict.put(matrix[x][y], dict.getOrDefault(matrix[x][y], 0) + 1);
        
        // 행의 길이가 작아질 것을 대비하여 모두 0으로 초기화
        matrix[x][y] = 0;
      }

      // Value(등장횟수)를 기준으로 Map 정렬
      List<Entry<Integer, Integer>> dictEntry = mapSortByValue(dict);

      // Map의 크기 = 등장하는 숫자의 개수
      // Map의 크기 * 2 = 정렬된 행의 길이 = 열의 크기
      // 정렬된 행의 길이가 100보다 클 경우 방지
      int colSize = dictEntry.size() * 2 > 100 ? 100 : dictEntry.size() * 2;
      
      for (int i = 0; i < colSize; i++) {
        // 정렬된 순서대로 배열에 값 넣어줌
        Entry<Integer, Integer> value = dictEntry.remove(0);
        matrix[x][i] = value.getKey();
        matrix[x][++i] = value.getValue();
      }

      // 정렬된 행의 길이 중에서 제일 큰 값 고름
      newColSize = Math.max(newColSize, colSize);
    }

    // 열의 최대 크기 갱신
    COL_SIZE = Math.max(ROW_SIZE, newColSize);
  }

  static void doCCalc() {
    // 각 열 정렬 시 행의 최대 크기가 달라짐
    int newRowSize = ROW_SIZE;

    for (int y = 0; y < COL_SIZE; y++) {
      HashMap<Integer, Integer> dict = new HashMap<Integer, Integer>();

      for (int x = 0; x < ROW_SIZE; x++) {
        if (matrix[x][y] == 0)
          continue;

        dict.put(matrix[x][y], dict.getOrDefault(matrix[x][y], 0) + 1);
        matrix[x][y] = 0;
      }

      List<Entry<Integer, Integer>> dictEntry = mapSortByValue(dict);

      int rowSize = dictEntry.size() * 2 > 100 ? 100 : dictEntry.size() * 2;
      for (int i = 0; i < rowSize; i++) {
        Entry<Integer, Integer> value = dictEntry.remove(0);
        matrix[i][y] = value.getKey();
        matrix[++i][y] = value.getValue();
      }

      newRowSize = Math.max(newRowSize, rowSize);
    }

    // 열의 길이 = 행의 사이즈
    // 행의 최대 길이 갱신
    ROW_SIZE = Math.max(ROW_SIZE, newRowSize);
  }

  static List<Entry<Integer, Integer>> mapSortByValue(HashMap<Integer, Integer> dict) {
    // Map의 Entry를 담은 List 생성
    List<Entry<Integer, Integer>> dictEntry = new ArrayList<Entry<Integer, Integer>>(dict.entrySet());

    // Entry 정렬
    Collections.sort(dictEntry, new Comparator<Entry<Integer, Integer>>() {

      @Override
      public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
        // key : 숫자, value : 등장 횟수
        // 등장 횟수 기준 오름차순
        // 만약 횟수가 같으면
        if (Integer.compare(o1.getValue(), o2.getValue()) == 0) {
          // 숫자 기준 오름차순
          return Integer.compare(o1.getKey(), o2.getKey());
        }
        return Integer.compare(o1.getValue(), o2.getValue());
      }

    });

    return dictEntry;
  }

}