SW 역량 테스트 기출 문제(이차원 배열과 연산)

[이차원 배열과 연산 - 17140]

 

 

* 로직

• R, C가 배열 A의 사이즈 범위 내에 있다면
  • 만약 A[R][C] = K라면 -> 바로 0초를 출력
  • 그렇지 않다면 -> doSolution() 진행
• R, C가 배열 A의 사이즈 범위를 벗어난다면
  • doSolution() 바로 진행
    
    
• 1초씩 늘려나가면서
  • N>=M이라면 R연산 진행
  • N<M이라면 C연산 진행
    
    
  • R 연산 진행은 다음과 같다
    • 1행부터 오른쪽으로 한 칸씩 이동하며 값을 확인한다
    • 해당 숫자에 대한 카운팅을 위해 HashMap을 사용한다
    • 각 숫자와 카운팅을 담는 클래스를 만들고, HashMap에 존재하는 정보를 list에 담는다
    • 문제 조건에 맞게 정렬을 진행하고, 1행에 대한 정보들을 보관한다(map_tmp)
    • 최대로 늘릴 수 있는 열의 길이를 갱신한다 (max)
    • 위 과정을 N행까지 반복한다
      
      
    • 과정이 끝났다면, 배열의 사이즈를 갱신한다
      • 단, 여기서 이전의 배열 사이즈보다 작다면 -> 이전의 배열 사이즈를 유지한다
      • 만약 크다면 -> 배열 사이즈를 갱신한다 (100보다 큰 경우엔 100으로 제한을 둔다)
    • 따로 보관해둔 각 행들의 정보(map_tmp)에서 하나씩 꺼내어 A 배열에 새롭게 값을 넣어준다
    • 넣어줄 때, 새로 갱신된 배열의 사이즈보다 작다면 -> 나머지 부분은 0을 넣는다
    • 사이즈보다 크다면 -> 나머지 부분은 제거한다
      
      
  • C 연산 역시 같은 맥락이다
    
    
  • 이후 A[R][C] = k가 되는 순간이 오면 해당 초를 리턴한다
  • 만약 time > 100이라면 -1을 리턴한다

 

// 이차원 배열과 연산
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;

class ArrayInfo implements Comparable<ArrayInfo>{
	public int num;
	public int count;
	
	public ArrayInfo(int num, int count) {
		super();
		this.num = num;
		this.count = count;
	}

	@Override
	public int compareTo(ArrayInfo o) {
		
		// 수의 등장 횟수를 기준으로 오름차순
		if(this.count > o.count) {
			return 1;
		}
		
		// 수의 등장 횟수가 같다면
		else if(this.count == o.count) {
			
			// 수 자체로 비교해서 오름차순
			return this.num - o.num;
		}
		
		return -1;
	}	
}

public class Problem_17140 {
	
	static int R,C;
	static int K;
	static int[][] A;
	static int N, M;
	static int answer;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;		
		
		String input = br.readLine();
		st = new StringTokenizer(input, " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		// input map. 처음에 3*3으로 시작
		N = 3;
		M = 3;
		A = new int[N+1][M+1];
		for(int i=1; i<=N; ++i) {
			input = br.readLine();
			st = new StringTokenizer(input, " ");
			for(int j=1; j<=M; ++j) {
				A[i][j] = Integer.parseInt(st.nextToken());				
			}
		}
		
		// 찾고자 하는 위치가 범위에 존재한다면
		if(R<=N && C<=M ) {
			
			// 바로 찾았다면 0초
			if(A[R][C] == K) System.out.println(0);
			
			// 아니라면 로직 진행
			else System.out.println(doSolution());
		}
		
		// 찾고자 하는 위치가 범위에 없다면 -> 바로 로직 진행
		else {
			System.out.println(doSolution());
		}		
	}

	private static int doSolution() {
		
		int time = 0;
		while(true) {					
			time++;
			if(time > 100) return -1;
			
			// N * M에서, N >= M인 경우 -> R연산 진행			
			if(N >= M) {
				doOperation(0);				
			}
			
			
			// N * M에서, N < M인 경우 -> C연산 진행
			else if(N < M){
				doOperation(1);
			}
						
			
			// A[r][c] = k라면 멈추기
			if(R<=N && C<=M) {
				if(A[R][C] == K) break;
			}		
			
		}
		
		return time;
	}

	private static void doOperation(int type) {
		
		ArrayList<LinkedList<ArrayInfo>> map_tmp = new ArrayList<>();
		int max = 0;
		
		switch (type) {
		case 0:
			
			// 모든 행에 대한 정렬 진행			
			for(int i=1; i<=N; ++i) {
				HashMap<Integer, Integer> hashMap = new HashMap<>();				
				
				for(int j=1; j<=M; ++j) {
					
					// 정렬할 때는 0은 무시
					if(A[i][j] > 0) {
						if(!hashMap.containsKey(A[i][j])) {
							hashMap.put(A[i][j], 1);
						}
						else {
							int count = hashMap.get(A[i][j]);
							hashMap.put(A[i][j], count+1);
						}
					}		
				}	
				
				// 각각의 수에 맞는 카운팅 정보를 리스트에 담기
				LinkedList<ArrayInfo> list = new LinkedList<>();
				for(int key : hashMap.keySet()) {
					list.add(new ArrayInfo(key, hashMap.get(key)));
				}
				
				// 정렬 & 저장
				Collections.sort(list);				
				map_tmp.add(list);				
				max = Math.max(max, list.size()*2);
			}
						
			// 이전의 배열 사이즈보다 작아지면 안됨 or 100을 넘어가면 안됨
			if(max < M) max = M;
			if(max > 100) max = 100;
			
			// 열의 최대 개수로 갱신
			M = max;
			A = new int[N+1][M+1];
			for(int i=1; i<=map_tmp.size(); ++i) {
				LinkedList<ArrayInfo> list = map_tmp.get(i-1);							
				
				int idx=1;
				for(int a=0; a<list.size(); ++a) {
					int num = list.get(a).num;
					int count = list.get(a).count;
					
					A[i][idx++] = num;
					A[i][idx++] = count;
					
					// 100개 이상인 경우, 초과했을 때 나머지 부분은 버리기
					if(idx > M) break;
				}
				
				// 나머지 부분 0으로 채우기
				while(idx <= M) {
					A[i][idx++] = 0;						
				}					
			}						
			
			break;

		case 1:
			// 모든 열에 대한 정렬 진행
			for(int j=1; j<=M; ++j) {
				HashMap<Integer, Integer> hashMap = new HashMap<>();						
				for(int i=1; i<=N; ++i) {
					
					// 정렬할 때는 0은 무시
					if(A[i][j] > 0) {
						if(!hashMap.containsKey(A[i][j])) {
							hashMap.put(A[i][j], 1);
						}
						else {
							int count = hashMap.get(A[i][j]);
							hashMap.put(A[i][j], count+1);
						}
					}					
				}	
				
				// 각각의 수에 맞는 카운팅 정보를 리스트에 담기
				LinkedList<ArrayInfo> list = new LinkedList<>();
				for(int key : hashMap.keySet()) {
					list.add(new ArrayInfo(key, hashMap.get(key)));
				}
				
				// 정렬 & 저장
				Collections.sort(list);				
				map_tmp.add(list);
				max = Math.max(max, list.size()*2);
			}
			
			
			if(max < N) max = N;
			if(max > 100) max = 100;
			
			N = max;
			A = new int[N+1][M+1];						
			for(int i=1; i<=map_tmp.size(); ++i) {
				LinkedList<ArrayInfo> list = map_tmp.get(i-1);
				
				int idx=1;
				for(int a=0; a<list.size(); ++a) {
					int num = list.get(a).num;
					int count = list.get(a).count;
					
					A[idx++][i] = num;
					A[idx++][i] = count;
					
					// 100개 이상인 경우, 초과했을 때 나머지 부분은 버리기
					if(idx > N) break;
				}
				
				// 나머지 부분 0으로 채우기
				while(idx <= N) {
					A[idx++][i] = 0;						
				}								
			}
			
			break;
		}		
	}

}