[백준] 배열돌리기 문제들

문제1

• 1 ≤ K ≤ 1,000
• 반시계

16926번: 배열 돌리기 1

 

풀이1

• N과 M의의 작은 값은 2로 나누어 떨어짐
  • 한번 돌 때, Math.min(N, M) / 2 만큼 내부적으로 돌아감
• 1번 회전할 때마다 아래의 순서대로 동작(K번 만큼 회전)
  • 위, 오른쪽, 아래, 왼쪽 순으로 돌릴 것임
  • 사라지는 부분(첫 시작)을 tmp에 저장해 놓음
  • 현재 위치를 기준으로, 다음 위치의 값을 넣어주는 방식으로 구현
  • 다 돌리고 나서 마지막 위치에 첫 위치 값(tmp)를 저장

코드1

import java.io.*;
import java.util.*;
public class Main {
    static int N, M, K;
    static int[][] map;
    static StringBuilder sb;
    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());
        K = Integer.parseInt(st.nextToken());
        int localRotationCnt = Math.min(N, M) / 2;
        map = new int[N][M];

        for(int i = 0 ; i < N ; i ++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < M ; j ++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        rotation(localRotationCnt);
        printMap();
    }
    private static void rotation(int localRotationCnt) {
        while(K -- > 0){
            for(int k = 0 ; k < localRotationCnt ; k ++){
                int tmp = map[k][k];
                // 위
                for(int i = k ; i < M-1-k ; i ++){
                    map[k][i] = map[k][i+1];
                }
                // 오른쪽
                for(int i = k ; i < N-1-k ; i ++){
                    map[i][M-1-k] = map[i+1][M-1-k];
                }
                // 아래
                for(int i = M-1-k ; i > k ; i --){
                    map[N-1-k][i] = map[N-1-k][i-1];
                }
                // 왼쪽
                for(int i = N-1-k ; i > k ; i --){
                    map[i][k] = map[i-1][k];
                }
                map[k+1][k] = tmp;
            }
        }
    }
    private static void printMap() {
        sb = new StringBuilder();
        for(int i = 0 ; i < N ; i ++){
            for(int j = 0 ; j < M ; j ++){
                sb.append(map[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

문제2

• 1 ≤ K ≤ 10^9

16927번: 배열 돌리기 2

풀이2

• 한 바퀴를 돌아 제자리로 찾아가는 부분의 경우 돌리지 않아도 되는 점을 활용
  • K의 값이 최대 10의 9승이기 때문에 배열 1 코드로 돌리게 되면 에러가 발생!
  • 따라서, N * 2 + M * 2 - 4 라는 공식을 활용하여,
    K % N * 2 + M * 2 - 4 의 길이 만큼만 해당 테두리를 회전시켜주면 된다.
  • 또한, 해당 테두리의 회전이 끝난 뒤에는, 각 변의 길이가 2씩 줄어들기 때문에
    N과 M을 -2씩 빼줘야 한다.

코드2

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

public class Main {
    static int N, M, K, useN, useM;
    static int[][] map;
    static StringBuilder sb;

    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());
        K = Integer.parseInt(st.nextToken());
        int localRotationCnt = Math.min(N, M) / 2;
        map = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        useN = N;
        useM = M;
        for (int i = 0; i < localRotationCnt; i++) {
            int len = useN * 2 + useM * 2 - 4; // 공식
            rotation(len, i);
            useN -= 2; // 각 변의 길이가 2씩 줄어들기 때문에
            useM -= 2;
        }
        printMap();
    }

    private static void rotation(int len, int k) {
        /**
         * newK는 총 몇 바퀴를 돌아야 되는지 나타내는 수(한바퀴를 돌아 제자리로 찾아가는 것을 줄이기 위해)
         * n=5, m=4, k=7 일때
         * 첫번째 테두리는 7번 회전만 하면 되고(2*5+2*4 -4 = 14, 7mod14 == 7)
         * 두번째 테두리는 1번 회전만 하면 된다(2*3+2*2 -4 = 6, 7mod6 == 1)
         */
        int newK = K % len;

        while (newK-- > 0) {
            int tmp = map[k][k];
            // 위
            for (int i = k; i < M - 1 - k; i++) {
                map[k][i] = map[k][i + 1];
            }
            // 오른쪽
            for (int i = k; i < N - 1 - k; i++) {
                map[i][M - 1 - k] = map[i + 1][M - 1 - k];
            }
            // 아래
            for (int i = M - 1 - k; i > k; i--) {
                map[N - 1 - k][i] = map[N - 1 - k][i - 1];
            }
            // 왼쪽
            for (int i = N - 1 - k; i > k; i--) {
                map[i][k] = map[i - 1][k];
            }
            map[k + 1][k] = tmp;
        }
    }

    private static void printMap() {
        sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                sb.append(map[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

문제3

16935번: 배열 돌리기 3

풀이3

• 입력으로 들어오는 타입에 맞게 메서드를 만들어 풀이(코드 참조)

코드3

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

public class Main {
    static int N, M, R, newN;
    static int[][] map, tmp;
    static StringBuilder sb;

    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());
        R = Integer.parseInt(st.nextToken());
        newN = Math.max(N, M);
        map = new int[newN][newN];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(br.readLine());
        for(int tcase = 1 ; tcase <= R ; tcase++) {
            int type = Integer.parseInt(st.nextToken());
            if(type == 1)
                type1(); // 상하반전
            else if(type == 2)
                type2(); // 좌우반전
            else if(type == 3)
                type3(); // 오른쪽90도회전
            else if(type == 4)
                type4(); // 왼쪽90도회전
            else if(type == 5)
                type5(); // 4그룹 이동(1->2, 2->3, 3->4, 4->1)
            else if(type == 6)
                type6(); // 4그룹 이동(5와 반대방향)
        }
        printMap();
    }

    private static void type1() {
        tmp = new int[newN][newN];

        for(int i = 0 ; i < N ; i ++){
            for(int j = 0 ; j < M ; j ++){
                tmp[N-1-i][j] = map[i][j];
            }
        }

        map = tmp;
    }
    private static void type2() {
        tmp = new int[newN][newN];

        for(int i = 0 ; i < N ; i ++){
            for(int j = 0 ; j < M ; j ++){
                tmp[i][M-1-j] = map[i][j];
            }
        }

        map = tmp;
    }
    private static void type3() {
        tmp = new int[newN][newN];

        for(int i = 0 ; i < M ; i ++){
            for(int j = 0 ; j < N ; j ++){
                tmp[i][j] = map[N-1-j][i];
            }
        }
        N^=M;
        M^=N;
        N^=M;
        map = tmp;
    }
    private static void type4() {
        tmp = new int[newN][newN];

        for(int i = 0 ; i < M ; i ++){
            for(int j = 0 ; j < N ; j ++){
                tmp[i][j] = map[j][M-1-i];
            }
        }
        N^=M;
        M^=N;
        N^=M;
        map = tmp;
    }
    private static void type5() {
        tmp = new int[newN][newN];
        // 1
        for(int i = 0 ; i < N/2 ; i ++){
            for(int j = 0 ; j < M/2 ; j ++){
                tmp[i][j+M/2] = map[i][j];
            }
        }
        // 2
        for(int i = 0 ; i < N/2 ; i ++){
            for(int j = M/2 ; j < M ; j ++){
                tmp[i+N/2][j] = map[i][j];
            }
        }
        // 3
        for(int i = N/2 ; i < N ; i ++){
            for(int j = M/2 ; j < M ; j ++){
                tmp[i][j-M/2] = map[i][j];
            }
        }
        // 4
        for(int i = N/2 ; i < N ; i ++){
            for(int j = 0 ; j < M/2 ; j ++){
                tmp[i-N/2][j] = map[i][j];
            }
        }
        map = tmp;
    }
    private static void type6() {
        tmp = new int[newN][newN];
        // 1->4
        for(int i = 0 ; i < N/2 ; i ++){
            for(int j = 0 ; j < M/2 ; j ++){
                tmp[i+N/2][j] = map[i][j];
            }
        }
        // 2->1
        for(int i = 0 ; i < N/2 ; i ++){
            for(int j = M/2 ; j < M ; j ++){
                tmp[i][j-M/2] = map[i][j];
            }
        }
        // 3->2
        for(int i = N/2 ; i < N ; i ++){
            for(int j = M/2 ; j < M ; j ++){
                tmp[i-N/2][j] = map[i][j];
            }
        }
        // 4->3
        for(int i = N/2 ; i < N ; i ++){
            for(int j = 0 ; j < M/2 ; j ++){
                tmp[i][j+M/2] = map[i][j];
            }
        }
        map = tmp;
    }

    private static void printMap() {
        sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                sb.append(map[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}