상어초등학교

2번째 풀고 2번째 틀림.

접근 방법(생각한 부분) 자료 구조 1. 친구 리스트 저장 : Map(num, flist) (구현🔺 변수명❌) 2. 착석 정보 저장 : int[ ][ ] map//자료구조와 변수이름이 혼동스러운 점 수정하는 것이 좋을 듯! 3. 좋아하는 친구 수 저장 : int[ ][ ] friend 4. 빈칸 갯수 저장 : int[ ][ ] vacant

알고리즘 1. 좋아하는 친구 수 카운팅 ❌ 2. 빈칸 수 카운팅 🔵 3. 착석칸 선정 🔺 //1번 조건이 같으면 2번 조건 비교하면 된다! 1) 친구 리스트의 친구 가장 많은 칸 friend[x][y]가 가장 큰 좌표 r,c가 선택할 좌표가 된다! 2) 빈칸 수 가장 많은 칸 vacant[x][y] 가 가장 큰 좌표 r,c가 선택할 좌표가 된다! 4. 착석 처리 🔺 Map[r][c] = num 은 맞지만, 착석 정보에 따라서 다른 학생이 착석할 때 좋아하는 친구 수 카운팅할 때 그 친구가 현재 착석해있는지 확인할 때 2차원 배열 map에서 찾으면 시간 복잡도는 O(N^2). Map으로 좌석배치도를 구현하면 O(1) 이 걸린다. 그렇기 때문에 착석에 대한 정보를 Map으로 구현하고, 다음 학생 좌석 선택할 때에도 O(1)의 시간 복잡도로 빠르게 찾을 수 있다. 5. 착석에 따른 해당 학생 상하좌우 빈칸 수 1씩 감소 🔵 6. 만족도 계산 : for-each문으로 학생과 친구 위치 인접 조건 판단 후 점수 계산 🔵

생각하지 못한 부분

자료구조로 Map을 사용했던 것까지는 생각이 나는데 key, value가 틀렸다! Map(num, flist) ❌ => Map(num, Student) value는 좋아하는 친구들 데이터가 아니라 Student클래스다!!!!
좋아하는 친구 수 카운팅 : 1의 좌석배치도 개념의 Map의 부재 때문인지, 좌석에 좋아하는 친구가 앉아있는지 판단하는 부분에서 막혔다. 좌석배치도 = Map map<num,Student>, 착석한 정보 = int[ ][ ] classroom 라고 하자. 이 좌석배치도에 학생 student 앉아 있다면 map.contains(student) 가 참인지 확인하면 된다! map.contains(student)가 참이면 그 학생의 좌표값을 가져온다 : Student student = map.get(student); 자바 Map 컬렉션) map.contains(key) : 존재 여부 확인, map.get(key) : value를 반환 student의 x, y좌표 기준 상하좌우 탐색. 범위체크 & 착석 가능 여부 체크(classroom[nx][ny]가 0) 좋아하는 친구 수 카운팅 : friend[nx][ny] ++;
좋아하는 친구 수 최댓값, 빈칸 수 최댓값 비교해서 최댓값인 좌석(좌표)를 착석할 좌석으로 선택한다!! 최댓값 비교를 위해 좋아하는 친구수 최댓값 : int friendMax, 빈칸 수 최댓값 : int emptyMax 선택할 좌석의 x,y좌표 저장 : int choiceX, int choiceY 1) 좋아하는 친구 수 최댓값과 그 좌표 구하기 if(friendMax < friend[i][j]) friendMax = friend[i][j]; choiceX = i; choiceY = j; ⭐️ 좋아하는 친구수 최댓값(i,j) 갱신하면서 (i,j)에 대해 빈칸 수 최댓값도 vacant[i][j]로 갱신해주어야 한다. =>왜냐하면 좋아하는 친구 수가 같을 때는 빈칸 갯수로 비교해야한다. 1번 조건에 의해 좋아하는 친구 수 최댓값 뿐만 아니라 해당 좌표에 따른 빈칸 갯수 최댓값도 갱 신해주어야 1번 조건이 같을 때 2번 조건 비교 시에 갱신된 빈칸 갯수 최댓값으로 비교한다!
ex) 현재(r,c)까지 vacantMax=2이고, 좋아하는 친구 수 같을 때 비교하는 빈칸 갯수는 friend[r][c]. 선택할 좌석 : (choiceX,choiceY)
착석 처리 1) 좌석배치도 map에 (현재 학생 번호, new Student(choiceX,choiceY, friends) 추가! 2) 선택한 좌석 추가! : classroom[choiceX][choiceY] = num;

3번째 풀고도 틀렸다.

문제 해결 과정과 자료구조, 알고리즘 선택하는 과정

자료구조 선정

학생 일단, 학생이라는 정보를 저장해야한다. 1. 학생의 만족도 계산을 위해 인접 거리를 계산할 때 학생의 (x,y) 위치 정보가 필요하다. 2. 학생마다 좋아하는 학생 4명의 번호를 저장해야한다.=>크기가 4인 정수형 배열로 만들 수 있다. 1번과 2번에 의해 학생 클래스를 생성할 때, x,y 위치 정보와 친구들 정보 int[ ] 3가지 속성값을 구현한다.
```
static class Student{
		int x;
		int y;
		int[] flist;
		
		public Student(int x, int y, int[] flist) {
			this.x = x;
			this.y = y;
			this.flist = flist;
		}
	}
```
좌석 선택 후, 좌석배치도⭐️⭐️⭐️⭐️⭐️(이것만 정확하게 파악해도 반은 맞출 수 있음.) ① 정수형 2차원 배열로 착석한 학생의 번호를 저장할 수 있다 : O(1)로 (x,y) 위치에 학생이 앉아있는지 없는지 확인할 수 있음 ② Map<Integer, Student>⭐️⭐️⭐️⭐️⭐️ Map 자료구조로 학생 착석정보를 저장하면, 학생 번호(key)로 학생 객체(value)에 접근하여 위치정보와 좋아하는 친구들 정보를 조회할 수 있다. => 이 Map 자료구조를 이용하여 좋아하는 친구가 많은 인접위치를 구할 때, 학생 객체의 flist를 조회, 순회하면서 좋아하는 친구마다 착석해있다면 그 인접한 위치에 점수를 1씩 증가시켜서 2차원 정수 배열인 nearScore을 완성할 수 있다.

알고리즘

0. 입력으로 주어지는 순서대로 좌석 선택하기 때문에 N^2명 학생 정보를 입력받을 때 1명 정보 입력받을 때마다 좌석 선택 메서드 실행한다.

for(int i=0; i<N2; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int num = Integer.valueOf(st.nextToken());
			int s1 = Integer.valueOf(st.nextToken());
			int s2 = Integer.valueOf(st.nextToken());
			int s3 = Integer.valueOf(st.nextToken());
			int s4 = Integer.valueOf(st.nextToken());
			
			findSeat(num, new int[] {s1,s2,s3,s4});
		}

findSeat 메서드 : 문제에서 주어진 그대로 구현하면 된다.

비어있는 칸 중 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리 정한다. => 어떻게 풀 수 있다? 현재 좌석선택하려는 학생 s이고 s의 선호 학생 flist = {2,5,1,7}라고 하자. 그러면 s는 아래 그림처럼 flist가 많은 위치를 선택해야한다. flist 순회하면서 각 원소의 인접위치에 점수를 매겨서 가장 높은 점수인 칸을 선택할 수 있다. 아래에서는 (1,1)에서의 점수값이 4가 되어 (1,1) 칸을 선택할 수 있게 된다. =>학생마다 flist에 따른 nearScore가 다르기 때문에 다른 학생 정보 입력받아서 findSeat 실행할 땐 초기화해주어야한다.⭐️
=>2차원 정수 배열 nearScore[ ][ ]에 [x][y] 위치에서 좋아하는 학생 flist 인접 위치에 점수를 1씩 증가시켜서 nearScore 배열을 완성한다. => nearScore 배열값 중 최댓값 갖는 [i][j] 위치를 선택한다. 배열값(점수값)을 계속해서 최댓값 비교& 갱신해야한다. [i][j]를 선택할 때, [i][j] 위치에서의 빈칸 갯수도 최댓값도 갱신해줘야한다. 이후에 비교하는 칸의 점수(인접한 좋아하는 학생 수)가 같을 때, 빈칸 갯수로 비교해야하기 때문이다.

2. 1을 만족하는 칸이 여러개일 때, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 처음에 좌석을 선택하는 학생은 flist가 착석하지 않았기 때문에 1번의 점수를 매길 수 없어서 모든 칸의 점수가 0으로 동일하다. 이렇게 동일한 점수값이 있을 때, 빈칸 갯수가 더 많은 칸으로 선택하려면 빈칸 갯수를 카운팅해야한다. => findeSeat 메서드를 실행하지 않아도 빈칸 갯수를 구할 수 있다. fillNearEmptySeat() : 각 칸마다 빈칸 갯수를 저장하는 nearEmptySeatCnt 배열을 완성한다. ① 일단 기본적으로 모든 칸의 빈칸 갯수를 4로 시작 ② 0번행이거나 0번 열이거나 N-1행이거나 N-1 열일 때 1씩 감소 => 0번 행, 0번 열, N-1행, N-1열은 빈칸 갯수가 3이 되고, 각 꼭짓점은 2번의 조건이 2번 해당되어 2가 된다. 나머지 칸들은 2번 조건에 해당되지 않아 빈칸 갯수가 4로 남아있다.

3. 조건1과 조건2마저도 같을 때, 행값과 열값을 비교하지 않았는데도 어떻게 정답이 나오는걸까? => 2중 for문이 행이 작은 것부터 증가하는 순, 열이 작은 것부터 증가하는 순으로 반복문이 구현되기 때문에 따로 구현하지 않아도 반복문 그 자체로 행이 작은 칸, 열이 작은 칸이 선택되는 것이다!!! 대박적..ㅠㅠㅜㅜㅜ => ① classroom[choiceX][choiceY] ② map.put(num, new Student(choiceX,choiceY, friends));//friends는 현재 findSeat메서드 호출, 실행될 때 받은 매개변수 4. 좌석 선택함에 따라 빈칸 갯수 1감소 업데이트 : 예상 좌석배치도 그림처럼, 학생 s가 좌석을 선택(choiceX,choiceY) 하면 인접해있는 4개의 좌표들은 0갯수가 하나씩 감소하는 것이기 때문에 (choiceX,choiceY) 를 기준으로 상하좌우 인접한 칸들에 대해 EmptySeatCnt 배열 값을 감소시킨다.

4번째 trial 틀린 이유

좌석 선택할 때, 그 자리에 학생이 앉아있는지 검사해줘야한다 : if(classroom[i][j] != 0) continue;

PreviousAlphabet Next스타트와 링크

Last updated 3 years ago

Was this helpful?