17140 이차원 배열과 연산 - 삼성 sw 역량 기출

이차원 배열과 연산

크기가 3X3인 배열에 1초가 지날때마다 연산이 적용된다.

• R 연산 : 모든 행에 대해서 정렬을 수행한다. (행의 개수 >= 열의 개수)

• C 연산 : 모든 열에 대해서 정렬을 수행한다. (열의 개수 > 행의개수)

정렬 기준

1. 수의 등장 횟수가 커지는 순

2. 등장 횟수가 같은 수가 여러가지면 수가 커지는 순

• 예제

  [3,1,1] 에는 3이 1번, 1가 2번 등장

  정렬된 결과는 [3,1,1,2]

  이 배열을 다시 정렬하면 3이 1번, 2가 1번, 1이 2번 등장

  결과는 [2,1,3,1,1,2]

행 이나 열의 크기가 100을 넘어가는 경우 처음 100개만 사용

[r][c] == k가 되기 위한 최소 시간을 구하라

100 초과이면 -1을 출력한다.

---

풀이

1. 100 이상이면 버리기 때문에 100 X 100 배열을 생성 후 입력한다.

2. 번호와 등장횟수를 저장하는 객체를 만든다. - Count
   • Comparable을 통해 정렬 기준에 맞춰 정렬할 수 있도록 구현한다.
3. 행 정렬 메소드와 열 정렬 메소드를 각각 구현한다.
   • 행/열 최대 크기를 저장하는 변수를 0으로 초기화 한다. - rMax, cMax
   • Count리스트를 생성하여 숫자와 등장횟수를 저장한다. - numberList
   • 리스트를 정렬한다.
   • map에 리스트를 규칙에 맞게 삽입한다.
4. while루프를 통해 조건에 맞는결과나 100번 반복한다
   • 루프마다 time을 누적해준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main이차원배열과연산 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st1 = new StringTokenizer(br.readLine());

		int r = Integer.parseInt(st1.nextToken());
		int c = Integer.parseInt(st1.nextToken());
		int k = Integer.parseInt(st1.nextToken());

		map = new int[101][101];

		for(int i = 0; i < 3; i++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine());
			for(int j = 0; j < 3; j++) {
				map[i][j] = Integer.parseInt(st2.nextToken());
			}
		}

		int time = 0;
		rMax = 3;
		cMax = 3;
		while(true) {
			if(map[r-1][c-1] == k)break;
			if(time == 101)break;


			if(cMax >= rMax) {
				rCal();
			}else {
				cCal();
			}

			time++;

		}
		if(time == 101) {
			System.out.println(-1);
		}else {
			System.out.println(time);
		}

	}

	static int[][] map;
	static int rMax;	// 열
	static int cMax;	// 행


	static void rCal() {
		rMax = 0;
		for(int i = 0; i < 101; i++) {
			List<Count> numberList = new ArrayList<>();
			for(int j = 0; j < 101; j++) {

				boolean chk = false;
				for(int k = 0; k < numberList.size(); k++) {
					if(numberList.get(k).number == map[i][j]) {
						numberList.get(k).count++;
						chk = true;
						break;
					}
				}
				if(!chk && map[i][j] != 0) {
					numberList.add(new Count(map[i][j], 1));
				}
			}		
			//정렬
			Collections.sort(numberList);

			for(int k = 0; k < 101; k++) {
				map[i][k] = 0;
			}
			if(rMax < numberList.size()*2) {
				rMax = numberList.size()*2;
			}

			for(int j = 0; j < numberList.size()*2; j+=2) {
				if(j >= 101)break;
				map[i][j] = numberList.get(j/2).number;
				map[i][j+1] = numberList.get(j/2).count;
			}

		}

	}

	static void cCal() {
		cMax = 0;
		for(int j = 0; j < 101; j++) {
			List<Count> numberList = new ArrayList<>();
			for(int i = 0; i < 101; i++) {
				boolean chk = false;
				for(int k = 0; k < numberList.size(); k++) {
					if(numberList.get(k).number == map[i][j]) {
						numberList.get(k).count++;
						chk = true;
						break;
					}
				}
				if(!chk && map[i][j] != 0) {
					numberList.add(new Count(map[i][j], 1));
				}
			}
			Collections.sort(numberList);
			for(int k = 0; k < 101; k++) {
				map[k][j] = 0;
			}
			if(cMax < numberList.size()*2) {
				cMax = numberList.size()*2;
			}
			for(int i = 0; i < numberList.size()*2; i+=2) {
				if(i >= 101) break;
				map[i][j] = numberList.get(i/2).number;
				map[i+1][j] = numberList.get(i/2).count;
			}
		}
	}



}

class Count implements Comparable<Count>{
	int number;
	int count;

	Count(int number, int count) {
		this.number = number;
		this.count = count;
	}

	@Override
	public int compareTo(Count o) {
		if(o.count > this.count) {
			return -1;
		}else if(o.count == this.count){
			if(o.number > this.number) {
				return -1;
			}else {
				return 1;
			}
		}else {
			return 1;
		}
	}
}