https://www.acmicpc.net/problem/17140
문제
아이디어
구현하는 부분을 총 3군데로 나눠야 겠다고 생각했다.
- 입력부분 + count(초)세는 부분
- 입력부분은 BufferReader 와 StringTokenizer로 해결하자
- count 부분은 while문을 써서 map[r][c] =k 인 지 확인 하고, 100초 초과시 종료.
- row 연산
- col 연산
제약사항(내가 생각하는)
- 100초 초과시 -1 반환 / 100초 이하 시 초 반환
- 연산으로 하고 크기가 100 넘어가는건 자르기
- 빈도수가 클수록 뒤로, 같은 빈도수 일때 숫자 크기로 정렬
- 0은 무시
- 열과 행의 크기는 유동적이고, 열과 행의 크기에 따라 연사는 하는 방식이 달라짐.
- 연산은 모든 행/ 모든 열에서 이뤄짐.
그런데 row 연산과 col의 연산은 동일하니(가로로하나 세로로하나 의 차이 정도) 둘 중 하나만 다른 하나도 그대로 적용하면 되니 별 문제가 없다고 생각을 했다.
고민 리스트
1. 어떤 자료구조를 사용하지?
1-1. ArrayList
제약사항 5번 처럼 열과 행의 크기가 항상 바뀌니까 처음엔 ArrayList를 생각했는데..
Row 계산을 할때 얼마나 늘어날지 미리 알고 선언을 해주어야 한다는 단점이 있어서 PASS했다.
1-2. int [][]
1번에서 ArrayList가 안되니 배열로 돌아왔고, 행 계산 할때, 열 계산할때 둘다 동일한 배열을 사용하니 static으로 선언을 하고, 크기를 101만큼 줘야 겠다 생각했다.
-> int 형 배열은 초기화 했을때 0으로 채워지고, 100까지 넣어야하니 101개의 크기라 생각했다.
2. map을 쓸건데 정렬을 어떻게 하지?
2-1. Comparator & Comparable
자바에서의 방법을 사용하려니 답이 나오지 않았음... 사용하고 싶으면 내가 hashmap을 상속 받아 새로운 class를 만드는 방식인데 굳이...? 라는 생각에 PASS
2-2. Map.EntrySet
List<Map.EntrySet>을 사용하면 내가 원하는 대로
Comparator의 Compare를 오버라이드 해서 빈도수 대로 정렬 -> 숫자 크기대로 정렬 이 가능하길래 오버라이드해서 빈도수 대로 정렬 -> 숫자 크기대로 정렬하는 방식을 선택했다.
풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ17140 {
static int [][] map =new int[101][101]; //100번째를 초과하는 줄은 무시하므로.
static int r,c,k,count=0;
static int max_r=3, max_c=3; //가로 세로 제한 처음엔 3*3 으로 고정 값이니
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
r = Integer.parseInt(st.nextToken())-1; // 인덱스가 1부터 시작하므로 -1
c = Integer.parseInt(st.nextToken())-1; // 인덱스가 1부터 시작하므로 -1
k = Integer.parseInt(st.nextToken());
for (int i = 0; i < 3; i++) {
st = new StringTokenizer(br.readLine()," ");
map[i][0]=Integer.parseInt(st.nextToken());
map[i][1]=Integer.parseInt(st.nextToken());
map[i][2]=Integer.parseInt(st.nextToken());
}
// 입력 끝!
// 초 찾기
while(map[r][c]!=k){ //만약 값이 맞으면 탈출
count++;
if(max_r>=max_c)//가로가 세로보다 같거나 긴경우
map=R_cal();
else //세로가 긴경우
map=C_cal();
if(count>100)break; //100회가 넘으면
}
if(count<=100) //100회 미만이면
System.out.println(count);
else
System.out.println(-1);
}
static int[][] R_cal(){
int[][] arr = new int[101][101]; //값을 집어 넣기 위한 임시 저장소
for (int i=0; i<101; i++) {
if(i==max_r) break; //최대 가로 수면 탈출
Map<Integer,Integer> temp = new TreeMap<>(); // 빈도수 세기 위한 map
for (int j =0; j<101; j++) {
int val = map[i][j];
temp.put(val,temp.getOrDefault(val,0)+1); // 만약 아무것도 없으면 0을 가져오기
}
List<Map.Entry<Integer,Integer>> entryList = new LinkedList<>(temp.entrySet());
entryList.sort(new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
if(o1.getValue()==o2.getValue()) //만약 빈도수가 동일하면
return o1.getKey()-o2.getKey(); //나온 숫자 오름 차순
else
return o1.getValue()- o2.getValue(); //빈도수로 오름 차순
}
});
int idx =0; //정렬한거 집어 넣는거
for (Map.Entry<Integer, Integer> entry : entryList) {
if(idx>=100)break; // 100을 초과 하면 pass
if(entry.getKey()==0) continue; //idx가 0이 존재하면 pass
arr[i][idx++] = entry.getKey();
arr[i][idx++] = entry.getValue();
}
if(idx >max_c) max_c =idx; //정렬후에 idx가 현 map의 최대 열 보다 크면 변환
}
return arr;
}
//로직은 동일 -> 열대로 정렬
static int[][] C_cal(){
int[][] arr = new int[101][101];
for (int i=0; i<101; i++) {//세로 대로 진행해야 하므로
if(i==max_c) break;
Map<Integer,Integer> temp = new TreeMap<>();
for (int j =0; j<101; j++) {
int val = map[j][i];
temp.put(val,temp.getOrDefault(val,0)+1); // 만약 아무것도 없으면 0을 가져오기
}
List<Map.Entry<Integer,Integer>> entryList = new LinkedList<>(temp.entrySet());
entryList.sort(new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
if(o1.getValue()==o2.getValue())
return o1.getKey()-o2.getKey();
else
return o1.getValue()- o2.getValue();
}
});
int idx =0;
for (Map.Entry<Integer, Integer> entry : entryList) {
if(idx>=100)break;
if(entry.getKey()==0) continue;
arr[idx++][i] = entry.getKey();
arr[idx++][i] = entry.getValue();
}
if(idx >max_r) max_r =idx;
}
return arr;
}
}
열심히 하자..!