문제

BOJ 17822: 원판 돌리기 https://www.acmicpc.net/problem/17822

풀이

중요한 조건

• 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 지운다.
  • 인접한 조건
    • i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다.
    • (i, j)와 인접한 위치는 아래와 같다.
      • (i - 1, j)
      • (i + 1, j)
      • (i, j - 1)
      • (i, j + 1)
• 인접하면서 수가 같은 것이 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

풀이 순서

• 각 원판에 들어갈 수를 Deque 자료구조를 사용해 저장한다.
  • 시계 방향과 반시계 방향으로 회전 시킬 때 구현하기 쉽기 때문이다.
  • 원판의 12시 방향을 기준으로 시계 방향으로 수를 넣도록 Deque의 Last방향에서 수를 차례로 넣는다.
• 각 원판을 HashMap 자료구조를 사용해 저장한다.
  • Index : 각 원판의 번호
  • Value : 각 원판에 있는 수를 저장한 Deque
• T의 횟수만큼 반복한다.
  • 입력받은 x의 배수인 원판을 모두 회전시킨다.
    • 회전 메소드의 설명은 아래 코드의 주석에 설명을 해놓았다.
  • 인접하면서 수가 같은 것이 있는 경우
    • 인접 위치를 탐색하며 삭제
    • 아래 코드의 주석에 설명을 해놓았다.
  • 인접하면서 수가 같은 것이 없는 경우
    • 남아 있는 값들의 평균을 구해 해결한다.
    • 이 때, 평균을 구할 때 쓸 변수들은 실수형(double)로 선언해야 한다.
• 모든 연산을 끝낸 뒤 남아있는 값들의 합을 구해 출력한다.

코드

import java.util.*;
import java.io.*;

public class Main {
    
	static int N, M, T;
	static HashMap<Integer, Deque<Integer>> map; // 원판 별 숫자를 넣을 HashMap
	static Deque<Integer>[] deq; // 각 원판의 숫자를 담을 Deque
	
	// 인접 수를 탐색할 배열
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 0};
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    	N = Integer.parseInt(st.nextToken()); // 원판 갯수 
    	M = Integer.parseInt(st.nextToken()); // 각 원판에 적힌 숫자 갯수
    	T = Integer.parseInt(st.nextToken()); // 회전 횟수
    	
    	map = new HashMap<>(); // 원판 별 숫자를 넣을 HashMap
    	for(int i=1; i<=N; i++) {
    		Deque<Integer> deq = new ArrayDeque<>();
    		st = new StringTokenizer(br.readLine(), " ");
    		for(int j=0; j<M; j++) {
    			deq.addLast(Integer.parseInt(st.nextToken())); // 원판의 12시 방향을 기준으로 시계 방향으로 수를 넣도록 Deque의 Last방향에서 수를 차례로 넣음
    		}
    		map.put(i, deq); // map에 원판 번호를 인덱스로 하여 덱을 넣음
    	}
    	
    	// 회전 횟수 만큼 반복
    	for(int i=0; i<T; i++) {
    		st = new StringTokenizer(br.readLine(), " ");
    		int x = Integer.parseInt(st.nextToken()); // 번호가 x의 배수인 원판을
    		int d = Integer.parseInt(st.nextToken()); // 0: 시계 방향, 1: 반시계 방향
    		int k = Integer.parseInt(st.nextToken()); // k칸 회전
    		
    		// 회전
    		int multiple = 1; // x의 배수를 탐색할 때 쓸 인덱스
    		while(true) {
    			int plateNum = x * multiple;
    			
    			if(plateNum > N) break; // 원판 번호가 범위를 넘어가면 탈출
    			
    			// 회전 횟수 만큼 회전
    			for(int j=1; j<=k; j++) {
    				rotate(plateNum, d);
    			}
    			
    			multiple++;
    		}
    		
    		// 삭제 연산 시작
    		
    		// map에 있는 값들을 2중 배열로 옮김
    		int[][] plate = new int[N+1][M];
    		for(int n=1; n<=N; n++) {
    			Deque<Integer> deq = map.get(n);
    			Iterator<Integer> iter = deq.iterator();
    			for(int m=0; m<M; m++) {
    				plate[n][m] = iter.next();
    			}
    		}
    		
    		
    		boolean isInDelete = false; // 인접한 값에 같은 수가 있는지 확인하는 변수
    		// 삭제할 것 표시
    		boolean[][] boolPlate = new boolean[N+1][M];
    		
    		for(int plateIdx=1; plateIdx<=N; plateIdx++) {
    			for(int idx=0; idx<M; idx++) {
    				// 현재 위치를 기준으로 인접한 값을 탐색
    				for(int t=0; t<4; t++) {
    					int nx = plateIdx + dx[t];
    					int ny = idx + dy[t];
    					
    					if(nx < 1 || nx > N) continue;
    					
    					if(ny < 0) {
    						ny = M-1;
    					} else if(ny >= M) {
    						ny = 0;
    					}
    					
    					// 현재 위치에 있는 값과 탐색한 값이 같다면 true 표시
    					if(plate[plateIdx][idx] != 0 && plate[plateIdx][idx] == plate[nx][ny]) {
    						isInDelete = true;
    						
    						boolPlate[plateIdx][idx] = true;
    						boolPlate[nx][ny] = true;
    					}
    				}
    				
    			}
    		}
    		
    		// true인 값 0으로 바꿈 -> 삭제를 의미함
    		for(int plateIdx = 1; plateIdx<=N; plateIdx++) {
    			for(int idx=0; idx<M; idx++) {
    				if(boolPlate[plateIdx][idx]) {
    					plate[plateIdx][idx] = 0;
    				}
    			}
    		}
    		
    		
    		// 인접하면서 같은 수가 없는 경우
    		if(!isInDelete) {
    			double sum = 0;
        		double cnt = 0;
        		for(int plateIdx = 1; plateIdx<=N; plateIdx++) {
        			for(int idx=0; idx<M; idx++) {
        				if(plate[plateIdx][idx] != 0) {
        					sum += plate[plateIdx][idx];
        					cnt++;
        				}
        			}
        		}
        		
        		double avr = sum / cnt; // 평균 구함
        		
        		for(int plateIdx = 1; plateIdx<=N; plateIdx++) {
        			for(int idx=0; idx<M; idx++) {
        				if(plate[plateIdx][idx] != 0) {
        					if(plate[plateIdx][idx] > avr) {
        						plate[plateIdx][idx]--;
        					} else if(plate[plateIdx][idx] < avr) {
        						plate[plateIdx][idx]++;
        					}
        					
        				}
        			}
        		}
    		}
    		
    		
    		// 삭제 된 결과를 새롭게 map에 넣음
    		for(int t=1; t<=N; t++) {
    			Deque<Integer> deq = new ArrayDeque<>();
    			
    			for(int idx=0; idx<M; idx++) {
    				deq.addLast(plate[t][idx]);
    			}
    			
    			map.remove(t);
    			map.put(t, deq);
    		}
    		
    	}
    	
    	// 남은 숫자들 다 더함
    	int ans = 0;
    	for(int i=1; i<=N; i++) {
    		Deque<Integer> deq = map.get(i);
    		
    		while(!deq.isEmpty()) {
    			int num = deq.poll();
    			ans += num;
    			
    		}
    	}
    	
    	System.out.println(ans);
    }
    
    // 회전시키는 메소드
    static void rotate(int plateNum, int dir) {
    	/*
    	 * plateNum : 원판 번호
    	 * dir : 회전 방향
    	 */
    	
    	Deque<Integer> deq = map.get(plateNum);
    	
    	// 시계 방향
    	if(dir == 0) {
    		// 원판의 12시 방향을 기준으로 시계방향 순으로 수를 넣어놨으므로
    		// Last에 있는 수를 빼서 First에 넣음
    		int num = deq.pollLast();
    		
    		deq.addFirst(num);
    	} 
    	// 반시계 방향
    	else {
    		// 원판의 12시 방향을 기준으로 시계방향 순으로 수를 넣어놨으므로
    		// First에 있는 수를 빼서 Last에 넣음
    		int num = deq.pollFirst();
    		
    		deq.addLast(num);
    	}
    	
    	// map에 있던 원본을 지우고 새로운 덱을 넣음
    	map.remove(plateNum);
    	map.put(plateNum, deq);
    }
      
}

정리

• 문제 조건 중 인접하면서 수가 같은 것이 없는 경우 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다. 라는 조건을 제대로 해석하지 못해 시간 낭비를 했다.
• 삭제 연산 부분을 메소드로 만들면 더 깔끔했을 것 같다.