Dazzling 개발 노트
[백준] 17822 - 원판 돌리기 (Java) 본문
[백준] 17822 - 원판 돌리기 (Java)
문제
https://www.acmicpc.net/problem/17822
풀이/후기
내가 문제를 풀면서 찾은 포인트, 메모들
- 배열에서 양 끝 값들의 인접 처리 : 어려울 줄 알았는데 그냥 맨 끝과 1 비교하면 됨
- 인접한 항목이 존재하지 않음 판단 : before배열 만들어서 변경 전 후 비교 카운트로 해결함. 어차피 초기화하느라 배열 한 번 더 탐색해야해서 그 반복문 그대로 이용
- 평균 구할 때 double 이용 : 연산에 들어가는 숫자들도 double형태로 해야됨.
- 삭제하는 부분 DFS/BFS로 하지 않아도 됨. 유사하게 check[][]를 이용해서 풀었음
- 회전시킬 때 괜히 반복문 한 번씩 아끼려다가 arr[i] = temp 이런 짓 해서 자꾸 배열 혼선 옴. 일단은 반복문 사용하자,,
막 풀었다고 생각했는데 제출하니 메모리, 속도가 나쁘지 않았다.
그래도 다음날 최적화해서 다시 풀어봤다.
사실 최적화해도 속도는 비슷해서 소스코드 정리 정도로 다시 푼듯ㅎㅎ
일단 다시 복습했다는 것에 뿌듯함을 느꼈다!
최근에 본 코테에서 디버깅 기능이 없다보니 좀 애를 먹었다.
예전엔 맨날 sysout만 쓰느라 디버깅 바보였는데
이젠 디버깅이 너무 익숙해져 없으면 불편하다ㅠㅠ
문제 다시 풀어볼 때 디버깅을 사용하지 않고 테스트용 함수를 생성해서 테스트해 보았다.
rotateFunc(x,d,k);
testFn();
deleteFunc();
testFn();
///중략
static void testFn() {
for (int i=1; i<N+1; i++) {
for (int j=1; j<M+1; j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
}이런식으로.
확실히 필요한 부분마다 반목문 지웠다 썼다 하는 것보다 편리했다.
코드
package Samsung;
import java.io.*;
import java.util.*;
public class Problem17822_re {
static int N, M, T;
static int[][] arr; //원판을 2차원 배열 형태로 표현
static int[][] dir = {{0,1}, {0,-1}, {1,0}, {-1,0}};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer str = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(str.nextToken());
M = Integer.parseInt(str.nextToken());
T = Integer.parseInt(str.nextToken());
arr = new int[N+1][M+1];
for (int i=1; i<N+1; i++) {
str = new StringTokenizer(br.readLine(), " ");
for (int j=1; j<M+1; j++) {
arr[i][j] = Integer.parseInt(str.nextToken());
}
}
while ( T-- > 0 ) {
str = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(str.nextToken());
int d = Integer.parseInt(str.nextToken());
int k = Integer.parseInt(str.nextToken());
rotateFunc(x,d,k);
deleteFunc();
}
//결과 출력
//남은 원판 내 숫자들의 합
int result = 0;
for (int i=1; i<N+1; i++) {
for (int j=1; j<M+1; j++) {
result += arr[i][j];
}
}
System.out.println(result);
}
static void testFn() {
for (int i=1; i<N+1; i++) {
for (int j=1; j<M+1; j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
}
static void rotateFunc(int x, int d, int k) {
for (int i=1; i<N+1; i++) {
//x의 배수인 행만 회전
if (i % x != 0) {
continue;
}
//회전을 위한 임시 배열 생성
int[] temp = new int[M+1];
//임시 배열 세팅
for (int j=1; j<M+1; j++) {
temp[j] = arr[i][j];
}
int ind = k;
while(ind-- > 0) {
//시계 방향
if (d == 0) {
for (int j=2; j<M+2; j++) {
if (j == M+1) {
temp[1] = arr[i][j-1];
continue;
}
temp[j] = arr[i][j-1];
}
}
//반시계 방향
if (d == 1) {
for (int j=1; j<M+1; j++) {
if (j == M) {
temp[M] = arr[i][1];
continue;
}
temp[j] = arr[i][j+1];
}
}
//원판에 변경된 숫자 바로 적용
for (int j=1; j<M+1; j++) {
arr[i][j] = temp[j];
}
}
}
}
static void deleteFunc() {
int[][] before = new int[N+1][M+1];
boolean[][] checked = new boolean[N+1][M+1];
int sum = 0; //평균을 위한 총합
int scnt = 0; //평균을 위한 개수
for (int i=1; i<N+1; i++) {
for (int j=1; j<M+1; j++) {
sum += arr[i][j];
if (arr[i][j] != 0) scnt++;
before[i][j] = arr[i][j];
for (int k=0; k<4; k++) {
int nx = i + dir[k][0];
int ny = j + dir[k][1];
if (nx < 1 || ny < 1 || nx > N || ny > M) {
continue;
}
if (arr[i][j] == arr[nx][ny]) {
checked[i][j] = true;
checked[nx][ny] = true;
}
}
}
//양 끝 값이 같은 경우 처리
if (arr[i][1] == arr[i][M]) {
checked[i][1] = true;
checked[i][M] = true;
}
}
int cnt = 0;
for (int i=1; i<N+1; i++) {
for (int j=1; j<M+1; j++) {
if (checked[i][j]) {
arr[i][j] = 0;
}
if (before[i][j] != arr[i][j]) {
cnt++;
}
}
}
if (cnt < 1) {
avgFunc(sum, scnt);
}
}
static void avgFunc(int sum, int scnt) {
//int형끼리 나누면 int(정수)가 되므로 double(실수)로 형변환
double s = (double) sum;
double c = (double) scnt;
double avg = s / c;
for (int i=1; i<N+1; i++) {
for (int j=1; j<M+1; j++) {
if (arr[i][j] == 0) {
continue;
}
if (arr[i][j] == avg) {
continue;
}
if (arr[i][j] > avg) {
arr[i][j] -= 1;
continue;
}
if (arr[i][j] < avg) {
arr[i][j] += 1;
continue;
}
}
}
}
}Commit
참고
'Algorithm/백준' Related Articles
more
