백준 17140 이차원 배열과 연산 - 삼성 SW 역량 테스트 기출

백준 17140 이차원 배열과 연산 - 삼성 SW 역량 테스트 기출

1. 문제 링크

https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

 

2. 문제 해결에 대한 아이디어

1. 문제에 주어진대로 충실히 구현하면 된다.

2. R 연산을 할 때는 열의 길이가 바뀌고 C 연산을 할 때는 행의 길이가 바뀐다. (길이가 줄어들 수 도 있다.)

3. 연산을 할 때, 숫자와 숫자의 등장 횟수를 따로 저장해야해서 Number 클래스를 사용했다.

4. 행의 크기는 N, 열의 크기는 M으로 작성했다.

5. 각 연산은 아래의 순서로 구현했다. (R 연산 기준)

   . 대상 행의 숫자와 숫자의 등장 횟수를 HashMap<숫자, 등장 횟수> hm 에 저장한다.

   . hm의 값을 꺼내서 ArrayList<Number> nums에 add한다.

      . add가 완료되면 등장 횟수 오름차순, 횟수가 동일하다면 수의 오름차순으로 정렬한다.

      . 이를 위해 Number 클래스에 toCompare를 구현했다.

   . 보드에 nums에 있는 값을 숫자, 등장 횟수 순으로 새로 업데이트 한다.

      . 이 때, 100 번째를 넘어가는 값뷰터는 생략하는 조건을 index 조건에 추가했다.

   . 업데이트가 완료되면, 업데이트가 완료 된 다음 열부터 100번째 열까지 0으로 초기화한다.

      . 길이가 짧아지는 경우가 있기 때문에 100번째 열까지 쭉 0으로 초기화해야한다.

   . MM(R 연산에서 변경된 열의 크기 중 최댓값)을 업데이트 한다.

   . 최종적으로 M에 MM을 대입한다.

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

public class Main {

	static class Number implements Comparable<Number> {
		int value, cnt;

		@Override
		public int compareTo(Number o) {
			if (this.cnt == o.cnt)
				return this.value - o.value;
			return this.cnt - o.cnt;
		}

		public Number(int value, int cnt) {
			super();
			this.value = value;
			this.cnt = cnt;
		}

	}

	static int R, C, K;
	static int[][] board = new int[100][100];
	static int N = 3, M = 3; // N은 행 M은 열 길이
	static HashMap<Integer, Integer> hm;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] rck = br.readLine().split(" ");
		R = Integer.parseInt(rck[0]) - 1;
		C = Integer.parseInt(rck[1]) - 1;
		K = Integer.parseInt(rck[2]);

		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				board[i][j] = Integer.parseInt(line[j]);
			}
		}
		int cnt = 0;
		while (board[R][C] != K && cnt <= 100) {
			if (N >= M) {
				fuctionR();
			} else {
				fuctionC();
			}

			++cnt;
		}

		if (cnt > 100)
			System.out.println(-1);
		else
			System.out.println(cnt);

	}

	private static void fuctionR() {
		int MM = 0;
		for (int i = 0; i < N; i++) {
			hm = new HashMap<>();
			for (int j = 0; j < M; j++) {
				if (board[i][j] == 0)
					continue;
				hm.put(board[i][j], hm.getOrDefault(board[i][j], 0) + 1);
			}
			ArrayList<Number> nums = new ArrayList<>();
			for (Integer key : hm.keySet()) {
				nums.add(new Number(key, hm.get(key)));
			}
			Collections.sort(nums);

			for (int j = 0; j < nums.size() * 2 && j < 100; j += 2) {
				board[i][j] = nums.get(j / 2).value;
				board[i][j + 1] = nums.get(j / 2).cnt;
			}

			if (nums.size() * 2 < 100) {
				for (int j = nums.size() * 2; j < 100; j++) {
					board[i][j] = 0;
				}
			}

			MM = Math.max(MM, nums.size() * 2 > 100 ? 100 : nums.size() * 2);
		}

		M = MM;
	}

	private static void fuctionC() {
		int NN = 0;
		for (int j = 0; j < M; j++) {
			hm = new HashMap<>();
			for (int i = 0; i < N; i++) {
				if (board[i][j] == 0)
					continue;
				hm.put(board[i][j], hm.getOrDefault(board[i][j], 0) + 1);
			}

			ArrayList<Number> nums = new ArrayList<>();
			for (Integer key : hm.keySet()) {
				nums.add(new Number(key, hm.get(key)));
			}
			Collections.sort(nums);

			for (int i = 0; i < nums.size() * 2 && i < 100; i += 2) {
				board[i][j] = nums.get(i / 2).value;
				board[i + 1][j] = nums.get(i / 2).cnt;
			}
			if (nums.size() * 2 < 100) {
				for (int i = nums.size() * 2; i < 100; i++) {
					board[i][j] = 0;
				}
			}

			NN = Math.max(NN, nums.size() * 2 > 100 ? 100 : nums.size() * 2);
		}
		N = NN;
	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 격자에 nums의 값을 넣을 때, nums의 인덱스 처리가 바로 떠오르지 않았다. --> i / 2  j / 2

2. 평이한 문제라고 생각한다.