Algorithm/개념 & 문법
[Algorithm] 구현
ajeong7038
2024. 1. 12. 03:04
`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다
✨ 개념
- 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
- 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
예시
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 문자열 처리 관련 문제
- 적절한 라이브러리를 사용해야 하는 문제
✨ 문제
17276번: 배열 돌리기
각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다.
www.acmicpc.net
- 왼쪽 입력, 오른쪽 출력
✨ 접근
- 2차원 배열로 접근 (좌표)
- 가장 가운데 고정
ex) 5 X 5인 경우 (2, 2) 고정 => 5/2
- 가운데서 n줄 떨어져 있는 줄은 n칸 이동
-> 두 줄 떨어져 있으면 옆옆칸으로 이동, 한 줄 떨어져 있으면 옆칸 이동
-> n은 최대 배열의 크기/2만큼 => ex, 5/2만큼
=> 인 줄 알았으나 `이동` 규칙에 따라 이동하면 됐었다.
- 어느 방향으로 돌리는지 먼저 파악하기
이동
1. 주 대각선
2. 가운데 열
3. 부 대각선 (오른쪽 위에서 왼쪽 아래)
4. 가운데 행
✨ 구현
- 한 번에 구현하려고 하니까 복잡해져서 하나씩 기능을 구현했다
1. n*n 배열, 45도 각도 고정
package Algorithm_study.week2;
import java.io.*;
import java.util.StringTokenizer;
/**
* 배열 돌리기.java
*/
public class BOJ_17276 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine()); // 테스트 케이스의 수 (몇 번 반복할 건지)
StringTokenizer st = new StringTokenizer(bf.readLine());
int arrSize = Integer.parseInt(st.nextToken()); // 배열 크기
int degree = Integer.parseInt(st.nextToken()); // 각도
int[][] arr = new int[arrSize+1][arrSize+1]; // 2차원 배열
// 테스트 케이스 반복
for (int i=0; i<T; i++) {
// 테이스 케이스마다 중간값이 다르므로 지역변수로 설정
// n * n 배열이므로 중간 좌표의 x값 == y값 (하나만 설정)
int middle = (arrSize+1)/2; // 중간 좌표 값
int[][] newArr = new int[arrSize+1][arrSize+1]; //arr.clone(); // 값 변경 후의 2차원 배열 (결과)
// 초기 배열 세팅 (1부터 5까지, 0은 사용 X)
for (int j=1; j<=arrSize; j++) {
for (int k=1; k<=arrSize; k++) {
// ex) (1, 1) -> 1 / (5, 5) -> 25
arr[j][k] = (j-1) * arrSize + k;
newArr[j][k] = (j-1) * arrSize + k;
}
}
// 배열 원소 순회
for (int j=1; j<=arrSize; j++) {
for (int k=1; k<=arrSize; k++) {
// 주 대각선 => 열만 변화
// 주 대각선 확인 : 만약 (x, y)에서 x == y이면
if (j == k) {
// X의 주 대각선을 가운데 열로 옮긴다 (1번 조건)
newArr[j][middle] = arr[j][k];
}
// 가운데 열 => 열만 변화
// ex) (1, 3) -> (1, 5) / (2, 3) -> (2, 4) ... (5, 3) -> (5, 1)
if (k == middle) {
// X의 가운데 열을 부 대각선으로 옮긴다 (2번 조건)
newArr[j][arrSize-j+1] = arr[j][k];
}
// 부 대각선 => 행만 변화
// (1, 5), (2, 4), (3, 3), (4, 2), (5, 1)
if (j == (arrSize - k + 1)) {
// X의 부 대각선을 가운데 행으로 옮긴다 (3번 조건)
newArr[middle][k] = arr[j][k];
}
// 가운데 행 => 행만 변화
if (j == middle) {
newArr[k][k] = arr[j][k];
}
}
}
// 출력
for (int j=1; j<=arrSize; j++) {
for (int k=1; k<=arrSize; k++) {
System.out.print(newArr[j][k] + " ");
}
System.out.println();
}
}
}
}
- "동시에 돌림"을 어떻게 구현하는지가 관건이다... (막혔다)
=> 새로운 2차원 배열으로 옮겨서 추가할 것
=> 헷갈려서 배열을 얕은 복사했다가 newArr 값만 바뀌어야 할 것을 기존 arr 값까지 전부 바꿔버렸다... 주의할 것
- 초기 배열 세팅할 때 이중 for문에 arr와 함께 newArr 값도 세팅해줬는데 깊은 복사를 할 수 있는 메소드가 있지 않을까 싶다
2. n*n 배열, 각도 방향 추가
- arrSize, degree, arr 배열이 main에 있다는 것을 깨닫고 테스트 케이스마다 새롭게 반복되도록 수정했다.
arrSize = 5
degree = 45
arrSize = 1
degree = 2
arrSize = 6
degree = 7
arrSize = 11
degree = 12
- 배열이 점점 커지길래 이상해서 arrSize와 degree 찍어봤더니 뭔가 잘못됐다는 걸 깨달았다.
- 원하는 것은 5 45 5 -45 ... 인데 배열 내 수를 arrSize와 degree로 인식하고 있었다
- 잘은 모르겠다만 `StringTokenizer` 부분에서 개행문자까지 읽어오며 발생하는 문제인 것 같다
- bf.readLine() -> bf.readLine().trim(); 으로 수정했다
-> 어림도 없지!
- 엥 멍청인가...? 애초부터 입력에 배열을 줬다... 그것도 안 보고 세팅부터 해 버렸다... (문제 좀 잘 보자...)
package Algorithm_study.week2;
import java.io.*;
import java.util.StringTokenizer;
/**
* 배열 돌리기.java
*/
public class BOJ_17276 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 수 (몇 번 반복할 건지)
// 테스트 케이스 반복
for (int i=0; i<T; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
// 테스트 케이스마다 값이 다르므로 지역변수로 설정
int arrSize = Integer.parseInt(st.nextToken()); // 배열 크기
int degree = Integer.parseInt(st.nextToken()); // 각도
int[][] arr = new int[arrSize+1][arrSize+1]; // 2차원 배열
System.out.println("arrSize = " + arrSize);
System.out.println("degree = " + degree);
// n * n 배열이므로 중간 좌표의 x값 == y값 (하나만 설정)
int middle = (arrSize+1)/2; // 중간 좌표 값
int[][] newArr = new int[arrSize+1][arrSize+1]; // 값 변경 후의 2차원 배열 (결과)
// 초기 배열 세팅 (1부터 5까지, 0은 사용 X)
for (int j=1; j<=arrSize; j++) {
st = new StringTokenizer(br.readLine());
for (int k=1; k<=arrSize; k++) {
arr[j][k] = Integer.parseInt(st.nextToken());
newArr[j][k] = (j-1) * arrSize + k;
}
}
// 각도 확인 (음수인지 양수인지)
if (degree > 0) {
clockwise(arrSize, arr, newArr, middle);
}
else {
counterclockwise(arrSize, arr, newArr, middle);
}
// 출력
for (int j=1; j<=arrSize; j++) {
for (int k=1; k<=arrSize; k++) {
System.out.print(newArr[j][k] + " ");
}
System.out.println();
}
}
br.close();
}
// 시계 방향 배열 순회
public static void clockwise(int arrSize, int[][] arr, int[][] newArr, int middle) {
// 배열 원소 순회
for (int j=1; j<=arrSize; j++) {
for (int k=1; k<=arrSize; k++) {
// 주 대각선 => 열만 변화
// 주 대각선 확인 : 만약 (x, y)에서 x == y이면
if (j == k) {
// X의 주 대각선을 가운데 열로 옮긴다 (1번 조건)
newArr[j][middle] = arr[j][k];
}
// 가운데 열 => 열만 변화
// ex) (1, 3) -> (1, 5) / (2, 3) -> (2, 4) ... (5, 3) -> (5, 1)
if (k == middle) {
// X의 가운데 열을 부 대각선으로 옮긴다 (2번 조건)
newArr[j][arrSize-j+1] = arr[j][k];
}
// 부 대각선 => 행만 변화
// (1, 5), (2, 4), (3, 3), (4, 2), (5, 1)
if (j == (arrSize - k + 1)) {
// X의 부 대각선을 가운데 행으로 옮긴다 (3번 조건)
newArr[middle][k] = arr[j][k];
}
// 가운데 행 => 행만 변화
if (j == middle) {
// X의 가운데 행을 주 대각선으로 옮긴다
newArr[k][k] = arr[j][k];
}
}
}
}
// 반시계 방향 배열 순회
public static void counterclockwise(int arrSize, int[][] arr, int[][] newArr, int middle) {
// 배열 원소 순회
for (int j=1; j<=arrSize; j++) {
for (int k=1; k<=arrSize; k++) {
// 주 대각선
// 주 대각선 확인 : 만약 (x, y)에서 x == y이면
if (j == k) {
// X의 주 대각선을 가운데 행으로 옮긴다 (3번 조건)
newArr[middle][k] = arr[j][k];
}
// 가운데 열
// (1, 3) -> (1, 1) / (2, 3) -> (2, 2)
if (k == middle) {
// X의 가운데 열을 주 대각선으로 옮긴다 (1번 조건)
newArr[j][j] = arr[j][k];
}
// 부 대각선
// (1, 5), (2, 4), (3, 3), (4, 2), (5, 1)
if (k == (arrSize - j + 1)) {
// X의 부 대각선을 가운데 열로 옮긴다 (1번 조건)
newArr[j][middle] = arr[j][k];
}
// 가운데 행
// (3,1) -> (5,1) / (3, 2) -> (4, 2) ...
if (j == middle) {
// X의 가운데 열을 부 대각선으로 옮긴다
newArr[arrSize-k+1][k] = arr[j][k];
}
}
}
}
}
- 방향 추가인데... 점점 길어지는데...
- "동시에 돌림" 을 구현하기 위해 며칠을 고민했다.
-> 새 배열을 만들기로 했는데 자꾸 이미 옮겼던 숫자가 다시 옮겨지는 등의 문제가 발생했다.
- clone()으로 깊은 복사를 해도 마찬가지. 알고 보니 2차원 배열은 clone()로 복사해도 얕은 복사가 되더라...
✨ 2차원 배열의 깊은 복사
// 얕은 복사
int[][] arr2 = arr1;
int[][] arr3 = new int[3][2];
int[][] arr4 = new int[3][2];
// 깊은 복사 (for문 + clone 사용)
for(int i = 0; i < arr1.length; i++) {
arr3[i] = arr1[i].clone();
}
// 깊은 복사 (2중 for문 사용)
for(int i = 0; i < arr1.length; i++) {
for(int j = 0; j < 2; j++) {
arr4[i][j] = arr1[i][j];
}
}
// 출처 : https://hanyeop.tistory.com/366package Algorithm_study.week2;
import java.io.*;
import java.util.StringTokenizer;
/**
* 배열 돌리기.java
*/
public class BOJ_17276 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 수 (몇 번 반복할 건지)
// 테스트 케이스 반복
for (int i=0; i<T; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
// 테스트 케이스마다 값이 다르므로 지역변수로 설정
int arrSize = Integer.parseInt(st.nextToken()); // 배열 크기
int degree = Integer.parseInt(st.nextToken()); // 각도
int[][] arr = new int[arrSize+1][arrSize+1]; // 2차원 배열
int rotate = Math.abs(degree) / 45; // 회전 수
// n * n 배열이므로 중간 좌표의 x값 == y값 (하나만 설정)
int middle = (arrSize+1)/2; // 중간 좌표 값
// 각도 확인 (음수인지 양수인지) && rotate
if (degree > 0) {
// 반복
for (int k=0; k<rotate; k++) {
// 깊은 복사 -> 바뀐 arr 값이 또 바뀌지 않도록 newArr 생성
int newArr[][] = new int[arrSize+1][arrSize+1];
// 2차원 배열은 clone()으로 깊은 복사가 안 됨.
// 한 행마다 clone() 하거나 이중 포문으로 직접 값을 대입하는 수밖에 없다. 또는 arraycopy() 사용
for (int a = 1; a<=arrSize; a++) {
for (int b = 1; b<=arrSize; b++) {
newArr[a][b] = arr[a][b];
}
}
for (int j = 1; j <= arrSize; j++) {
if (k == 0) {
st = new StringTokenizer(br.readLine());
}
// 한 줄씩 넣어주기 -> 확인해서 arr 배열에 넣기 (결괏값)
// k : 여러 번 반복하는지 확인
clockwise(j, arrSize, st, arr, newArr, middle, k);
}
}
}
else {
for (int k=0; k<rotate; k++) {
// 깊은 복사 -> 바뀐 arr 값이 또 바뀌지 않도록 newArr 생성
int newArr[][] = new int[arrSize+1][arrSize+1];
// 2차원 배열 깊은 복사
for (int a = 0; a<arr.length; a++) {
newArr[i] = arr[i].clone();
}
for (int j = 1; j <= arrSize; j++) {
if (k == 0) {
st = new StringTokenizer(br.readLine());
}
counterclockwise(j, arrSize, st, arr, newArr, middle, k);
}
}
}
// 출력
for (int j=1; j<=arrSize; j++) {
for (int k=1; k<=arrSize; k++) {
System.out.print(arr[j][k] + " ");
}
System.out.println();
}
}
br.close();
}
// 시계 방향 배열 순회
// r : 여러 번 반복 확인
public static void clockwise(int j, int arrSize, StringTokenizer st, int[][] arr, int[][] newArr, int middle, int r) {
// 배열 원소 순회
for (int k = 1; k <= arrSize; k++) {
int num;
if (r == 0) {
num = Integer.parseInt(st.nextToken());
}
else {
num = newArr[j][k]; // 5번 반복
}
// 주 대각선 => 열만 변화
// 주 대각선 확인 : 만약 (x, y)에서 x == y이면
if (j == k) {
// X의 주 대각선을 가운데 열로 옮긴다 (1번 조건)
arr[j][middle] = num;
}
// 가운데 열 => 열만 변화
// ex) (1, 3) -> (1, 5) / (2, 3) -> (2, 4) ... (5, 3) -> (5, 1)
else if (k == middle) {
// X의 가운데 열을 부 대각선으로 옮긴다 (2번 조건)
arr[j][arrSize - j + 1] = num;
}
// 부 대각선 => 행만 변화
// (1, 5), (2, 4), (3, 3), (4, 2), (5, 1)
else if (j == (arrSize - k + 1)) {
// X의 부 대각선을 가운데 행으로 옮긴다 (3번 조건)
arr[middle][k] = num;
}
// 가운데 행 => 행만 변화
else if (j == middle) {
// X의 가운데 행을 주 대각선으로 옮긴다
arr[k][k] = num;
}
else {
arr[j][k] = num;
}
}
}
// 반시계 방향 배열 순회
public static void counterclockwise(int j, int arrSize, StringTokenizer st, int[][] arr, int[][] newArr, int middle, int r) {
// 배열 원소 순회
for (int k = 1; k <= arrSize; k++) {
int num;
if (r == 0) {
num = Integer.parseInt(st.nextToken());
}
else {
num = newArr[j][k];
}
// 주 대각선
// 주 대각선 확인 : 만약 (x, y)에서 x == y이면
if (j == k) {
// X의 주 대각선을 가운데 행으로 옮긴다 (3번 조건)
arr[middle][k] = num;
}
// 가운데 열
// (1, 3) -> (1, 1) / (2, 3) -> (2, 2)
else if (k == middle) {
// X의 가운데 열을 주 대각선으로 옮긴다 (1번 조건)
arr[j][j] = num;
}
// 부 대각선
// (1, 5), (2, 4), (3, 3), (4, 2), (5, 1)
else if (k == (arrSize - j + 1)) {
// X의 부 대각선을 가운데 열로 옮긴다 (1번 조건)
arr[j][middle] = num;
}
// 가운데 행
// (3,1) -> (5,1) / (3, 2) -> (4, 2) ...
else if (j == middle) {
// X의 가운데 열을 부 대각선으로 옮긴다
arr[arrSize - k + 1][k] = num;
}
else {
arr[j][k] = num;
}
}
}
}
- 이게 뭐지 싶은 긴... (답 아님)
- 어찌저찌 나오긴 했는데 보기도 힘든 코드(주석 때문에 길어졌다고 하고 싶다...) + 효율 따위는 생각도 안 한 코드 + StringTokenizer 잘못 써서 마지막에 두 번 엔터 쳐야 답 나옴 (틀림)
- 결론 : 접근은 비슷했다. 한 1%? 음! 다시 공부하자!