[백준 17140]이차원 배열과 연산/삼성 sw역량 테스트 기출(java)

문제보러가기

17140번: 이차원 배열과 연산

이문제는 주어진 조건으로 행,열 각각 정렬을 할 수 있는지 말그대로 이차원 배열의 연산을 진행할 수 있는지를 묻는 문제였던거같다. 바보같이 package를 지우지 않는 실수를... 런타임에러가 나길래 배열만 뜯어보고 있었다.. 하하...

 

 

 

문제풀이

-rCnt , cCnt를 갱신하며 rSort를 진행할지 cSort를 진행할지 체크한다

-각 행마다, 혹은 각 열마다 HashMap을 통해 숫자를 key로 나타난갯수를 value로 카운트해준다

-각 행마다, 혹은 각 열마다 주어진 조건으로 sorting함수를 쓰고 map을 갱신해준다.

-333 같은 경우 31로 길이가 짧아지게 된다. 이를 대비해서 HashMap에 값을 넣고 정렬이 된 후에 해당 행(열)은 0으로 초기화 해준다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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;
import java.util.StringTokenizer;

public class Main {

	static int[][] map;//갱신,정렬할 맵

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st; 
		st = new StringTokenizer(br.readLine());
		int r = Integer.parseInt(st.nextToken()) - 1;
		int c = Integer.parseInt(st.nextToken()) - 1;
		int k = Integer.parseInt(st.nextToken());

		map = new int[101][101];//최대 100행(열)이므로 101로 설정

		for (int i = 0; i < 3; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
        //처음 rCnt,cCnt,time초기화
		int rCnt = 3;
		int cCnt = 3;
		int time = 0;
		while (true) {
        	//타임이 100이 넘거나, 주어진 값을 찾으면 break
			if (map[r][c] == k || time==101)
				break;
			//rSort를 할지 cSort를 할지 체크
			if (rCnt >= cCnt)
				cCnt = rSort(rCnt,cCnt);
			else
				rCnt = cSort(rCnt,cCnt);
			
			time++;
		}
        
		if(time==101) time = -1;
		System.out.println(time);

	}
	//행으로 정렬
	public static int rSort(int row, int col) {
		int cCnt=0;
		HashMap<Integer, Integer> h;
        //값이 있는 곳까지만 확인하기 위해 row,col까지 확인
		for (int i = 0; i < row; i++) {
			h = new HashMap<>();
			for (int j = 0; j < col; j++) {
				if (map[i][j] == 0)
					continue;
				h.put(map[i][j], h.getOrDefault(map[i][j], 0) + 1);
				map[i][j]=0;
			}
			List<Entry<Integer, Integer>> listEntries = new ArrayList<Entry<Integer, Integer>>(h.entrySet());
			Collections.sort(listEntries,new MapSorting());
            //key,value쌍 두개의 값이 들어가야 하므로 size*2만큼 반복
			int size =listEntries.size()*2;
            //행이 100이 넘어갈경우 뒤에 숫자를 자르는 조건
			if(size>100) size=100;
			for(int k=0;k<size;k+=2){
				map[i][k] = listEntries.get(k/2).getKey();
				map[i][k+1] = listEntries.get(k/2).getValue();
			}
            //행마다 가장 긴 길이를 cCnt로 갱신
			cCnt= Math.max(cCnt, listEntries.size()*2);
		}
		return cCnt;
		
	}
	//열로 정렬
	public static int cSort(int row, int col) {
		HashMap<Integer, Integer> h;
		int rCnt=0;
		for (int i = 0; i < col; i++) {
			h = new HashMap<>();
			for (int j = 0; j < row; j++) {
				if (map[j][i] == 0)
					continue;
				h.put(map[j][i], h.getOrDefault(map[j][i], 0) + 1);
				map[j][i]=0;

			}
			List<Entry<Integer, Integer>> listEntries = new ArrayList<Entry<Integer, Integer>>(h.entrySet());
			Collections.sort(listEntries,new MapSorting());
			int size =listEntries.size()*2;
			if(size>100) size=100;
			for(int k=0;k<size;k+=2){
				map[k][i] = listEntries.get(k/2).getKey();
				map[k+1][i] = listEntries.get(k/2).getValue();
			}
			rCnt = Math.max(rCnt, listEntries.size()*2);
		}
		return rCnt;
	}
	

}
//해당 조건에 맞춰 정렬해주는 클래스
class MapSorting implements Comparator<Entry<Integer, Integer>>{
	public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2) {
		// 등장 갯수가 같을경우 숫자의 오름차순으로
		if(obj1.getValue()==obj2.getValue()){
			return obj1.getKey().compareTo(obj2.getKey());
		}
        // 등장 갯수의 오름차순 -기본정렬
		return obj1.getValue().compareTo(obj2.getValue());
	}
}