기본 콘텐츠로 건너뛰기

코딩 테스트 - 고고학 최고의 발견

package programmers;

class 고고학_최고의_발견_Java_230731 {

// 출처 : https://velog.io/@ddongh1122/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B3%A0%EA%B3%A0%ED%95%99-%EC%B5%9C%EA%B3%A0%EC%9D%98-%EB%B0%9C%EA%B2%AC

/*
고고학자인 혜선은 오래전부터 성궤의 행방을 추적해왔습니다.
그동안 그의 연구는 주류 학자들로부터 인정받지 못했었지만,
혜선이는 포기하지 않고 조사를 계속했고 마침내 성궤의 행방을 알아내었습니다.

그러나 오래전 누군가로부터 봉인된 성궤는 특별한 잠금장치에 의해 보호되고 있었습니다.
잠금장치는 일종의 퍼즐과 연결되어 퍼즐을 해결하면 열리는 것으로 보입니다.

퍼즐은 시계들이 행렬을 이루는 구조물인데 하나의 시계에 시곗바늘은 하나씩만 있습니다.
각 시곗바늘은 시계방향으로만 돌릴 수 있고 한 번의 조작으로 90도씩 돌릴 수 있습니다.
시계들은 기계장치에 의해 연결되어 있어 어떤 시계의 시곗바늘을 돌리면
그 시계의 상하좌우로 인접한 시계들의 시곗바늘도 함께 돌아갑니다.
행렬의 모서리에 위치한 시계의 시곗바늘을 돌리는 경우에는
인접한 세 시계의 시곗바늘들이 함께 돌아가며,
꼭짓점에 위치한 시계의 시곗바늘을 돌리는 경우에는
인접한 두 시계의 시곗바늘들이 함께 돌아갑니다.

각 시계는 12, 3, 6, 9시 방향 중의 한 방향을 가리키고 있습니다.
각 시계의 시곗바늘을 적절히 조작하여
모든 시곗바늘이 12시 방향을 가리키면 퍼즐이 해결되어 성궤를 봉인하고 있는 잠금장치가 열릴 것입니다.

노후화된 퍼즐 기계장치가 걱정되었던 혜선은 가능한 최소한의 조작으로 퍼즐을 해결하려고 합니다.
시곗바늘들의 행렬 clockHands가 매개변수로 주어질 때,
퍼즐을 해결하기 위한 최소한의 조작 횟수를 return 하도록 solution 함수를 완성해주세요.

제한사항
2 ≤ clockHands의 길이 ≤ 8
clockHands 2차원 배열이며 행과 열의 크기가 동일합니다.
0 ≤ clockHands의 원소 ≤ 3
clockHands[i]의 원소들은 시곗바늘의 방향을 나타내며 0 12시 방향, 1 3시 방향, 2 6시 방향, 3 9시 방향을 나타냅니다.
해결 가능한 퍼즐만 주어집니다.

입출력 예
clockHands result
[[0,3,3,0],[3,2,2,3],[0,3,2,0],[0,3,3,3]] 3
*/
int maxInt = Integer.MAX_VALUE; // 시계의 개수 (N)의 최댓값을 저장하는 변수
int answer = Integer.MAX_VALUE; // 최소 회전 횟수를 저장하는 변수
int[][] 시계상태; // 시계들의 상태를 저장하는 2차원 배열
int[] 회전수; // 각 시계의 회전 횟수를 저장하는 배열
int[] xArr = {0, 0, 0, 1, -1}; // 회전할 때 인접한 시계의 행을 결정하는 배열
int[] yArr = {0, 1, -1, 0, 0}; // 회전할 때 인접한 시계의 열을 결정하는 배열

// 시계들의 회전 수를 결정하는 dfs 함수
public void dfs(int 입력값) {
// 모든 시계의 회전 수를 결정했을 때 (기저 조건)
if (입력값 == maxInt) {
int[][] temp = new int[maxInt][maxInt];
int[] 현재회전수 = new int[maxInt];
// 현재 시계의 회전 수를 복사
for (int i = 0; i < maxInt; i++)
현재회전수[i] = 회전수[i];
// 현재 시계 상태를 복사
for (int i = 0; i < maxInt; i++) {
for (int j = 0; j < maxInt; j++)
temp[i][j] = 시계상태[i][j];
}

int 회전횟수계산 = 0; // 회전 횟수를 계산하는 변수
// 시계 상태를 시뮬레이션하며 회전 횟수를 계산
for (int i = 0; i < maxInt; i++) {
for (int j = 0; j < maxInt; j++) {
회전횟수계산 += 현재회전수[j];
for (int k = 0; k < 5; k++) {
int X = i + xArr[k];
int Y = j + yArr[k];
// 인접한 시계의 위치가 범위를 벗어나면 건너뜀
if (X < 0 || Y < 0 || X >= maxInt || Y >= maxInt) continue;
// 인접한 시계의 상태를 업데이트
temp[X][Y] = temp[X][Y] - 현재회전수[j] >= 0 ? temp[X][Y] - 현재회전수[j] : temp[X][Y] - 현재회전수[j] + 4;
}
}

// 다음 행의 회전할 시계의 회전 수 결정
for (int j = 0; j < maxInt; j++)
현재회전수[j] = temp[i][j];
}

boolean flag = true;
// 마지막 열의 상태를 판별하여 모든 시계가 12시 방향을 가리키는지 확인
for (int i = 0; i < maxInt; i++) {
if (현재회전수[i] != 0) {
flag = false;
break;
}
}
// 모든 시계가 12시 방향을 가리키면 결과를 갱신
if (flag) answer = Math.min(answer, 회전횟수계산);
return;
}

// 회전 수 정하기 (백트래킹)
for (int i = 0; i < 4; i++) {
회전수[입력값] = i;
dfs(입력값 + 1);
}
}

public int solution(int[][] clockHands) {
// 초기화
maxInt = clockHands.length; // 시계 개수를 결정
시계상태 = new int[maxInt][maxInt]; // 시계 상태를 저장할 2차원 배열 생성
회전수 = new int[maxInt]; // 회전 수를 저장할 배열 생성
// 시계의 상태를 변경하여 12시 방향을 0으로 맞춤
for (int i = 0; i < maxInt; i++) {
for (int j = 0; j < maxInt; j++)
시계상태[i][j] = 4 - clockHands[i][j] == 4 ? 0 : 4 - clockHands[i][j];
}

// dfs 진행하여 최소 회전 횟수 계산
dfs(0);
return answer; // 최소 회전 횟수 반환
}
}

package programmers

class 고고학_최고의_발견_Kotlin_230731 {
var maxInt = Int.MAX_VALUE // 시계의 개수 (N)의 최댓값을 저장하는 변수
var answer = Int.MAX_VALUE // 최소 회전 횟수를 저장하는 변수
lateinit var 시계상태: Array<IntArray> // 시계들의 상태를 저장하는 2차원 배열
lateinit var 회전수: IntArray // 각 시계의 회전 횟수를 저장하는 배열
val xArr = intArrayOf(0, 0, 0, 1, -1) // 회전할 때 인접한 시계의 행을 결정하는 배열
val yArr = intArrayOf(0, 1, -1, 0, 0) // 회전할 때 인접한 시계의 열을 결정하는 배열

// 시계들의 회전 수를 결정하는 dfs 함수
fun dfs(입력값: Int) {
// 모든 시계의 회전 수를 결정했을 때 (기저 조건)
if (입력값 == maxInt) {
val temp = Array(maxInt) { IntArray(maxInt) }
val 현재회전수 = IntArray(maxInt)
// 현재 시계의 회전 수를 복사
for (i in 0 until maxInt)
현재회전수[i] = 회전수[i]
// 현재 시계 상태를 복사
for (i in 0 until maxInt) {
for (j in 0 until maxInt)
temp[i][j] = 시계상태[i][j]
}

var 회전횟수계산 = 0 // 회전 횟수를 계산하는 변수
// 시계 상태를 시뮬레이션하며 회전 횟수를 계산
for (i in 0 until maxInt) {
for (j in 0 until maxInt) {
회전횟수계산 += 현재회전수[j]
for (k in 0..4) {
val X = i + xArr[k]
val Y = j + yArr[k]
// 인접한 시계의 위치가 범위를 벗어나면 건너뜀
if (X < 0 || Y < 0 || X >= maxInt || Y >= maxInt) continue
// 인접한 시계의 상태를 업데이트
temp[X][Y] = if (temp[X][Y] - 현재회전수[j] >= 0) temp[X][Y] - 현재회전수[j] else temp[X][Y] - 현재회전수[j] + 4
}
}

// 다음 행의 회전할 시계의 회전 수 결정
for (j in 0 until maxInt)
현재회전수[j] = temp[i][j]
}

var flag = true
// 마지막 열의 상태를 판별하여 모든 시계가 12시 방향을 가리키는지 확인
for (i in 0 until maxInt) {
if (현재회전수[i] != 0) {
flag = false
break
}
}
// 모든 시계가 12시 방향을 가리키면 결과를 갱신
if (flag) answer = answer.coerceAtMost(회전횟수계산)
return
}

// 회전 수 정하기 (백트래킹)
for (i in 0..3) {
회전수[입력값] = i
dfs(입력값 + 1)
}
}

fun solution(clockHands: Array<IntArray>): Int {
// 초기화
maxInt = clockHands.size // 시계 개수를 결정
시계상태 = Array(maxInt) { IntArray(maxInt) } // 시계 상태를 저장할 2차원 배열 생성
회전수 = IntArray(maxInt) // 회전 수를 저장할 배열 생성
// 시계의 상태를 변경하여 12시 방향을 0으로 맞춤
for (i in 0 until maxInt) {
for (j in 0 until maxInt)
시계상태[i][j] = if (4 - clockHands[i][j] == 4) 0 else 4 - clockHands[i][j]
}

// dfs 진행하여 최소 회전 횟수 계산
dfs(0)
return answer // 최소 회전 횟수 반환
}
}


package programmers

class 고고학_최고의_발견_Kotlin2_230731 {
fun solution(clockHands: Array<IntArray>): Int {
var answer: Int = Int.MAX_VALUE
val length = clockHands.size

// 시계를 회전하는 함수
fun rotate(x: Int, y: Int, 각도: Int) {
// 시계의 방향을 각도만큼 회전시킴 (0~3: 90, 180, 270, 360)
clockHands[x][y] = (clockHands[x][y] + 각도) % 4
// 상하좌우의 인접한 시계도 함께 회전
if (x > 0) clockHands[x - 1][y] = (clockHands[x - 1][y] + 각도) % 4
if (x < length - 1) clockHands[x + 1][y] = (clockHands[x + 1][y] + 각도) % 4
if (y > 0) clockHands[x][y - 1] = (clockHands[x][y - 1] + 각도) % 4
if (y < length - 1) clockHands[x][y + 1] = (clockHands[x][y + 1] + 각도) % 4
}

// DFS로 시계들의 상태를 탐색하며 최소 회전 횟수를 찾는 함수
fun dfs(x: Int, y: Int, count: Int) {
// 모든 시계의 상태를 탐색했을 때 (기저 조건)
if (x == length) {
// 마지막 시계가 12시 방향을 가리키면 최소 회전 횟수 갱신
if (clockHands[length - 1][length - 1] == 0) answer = minOf(answer, count)
return
} else if (x == 0) {
// 첫 번째 행의 시계들을 모든 회전 수(각도)에 대해 탐색
for (각도 in 0..3) {
// 각도가 1 이상이면 해당 시계를 회전시키고 다음 행으로 이동하여 탐색
if (각도 >= 1) rotate(x, y, 1)
dfs(x + (y + 1) / length, (y + 1) % length, count + 각도)
}
// 회전 수에 따라 원래 상태로 되돌려줌
rotate(x, y, 1)
} else {
// 마지막 행이 아닌 경우, 이전 행과의 시계 상태를 비교하여 일치하지 않으면 탐색 종료
if (x == length - 1 && y > 0 && clockHands[x - 1][y] != clockHands[x][y - 1]) return
// 이전 행과의 시계 상태를 맞추기 위한 회전 수(각도) 계산
val 각도 = (4 - clockHands[x - 1][y]) % 4
// 해당 시계를 회전시키고 다음 행으로 이동하여 탐색
rotate(x, y, 각도)
dfs(x + (y + 1) / length, (y + 1) % length, count + 각도)
// 회전 수에 따라 원래 상태로 되돌려줌
rotate(x, y, 4 - 각도)
}
}

// DFS 호출을 통해 최소 회전 횟수를 찾음
dfs(0, 0, 0)
return answer
}
}


댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ * https://joker1209.tistory.co

개발 공부 - json JSONObject 사용 시 백슬래시(\), 원화 표시(\) 제거 및 치환

import org.json.simple.JSONObject; String dataString = new String(authData.toJSONString()); dataString = dataString.replaceAll("\\\\", ""); String 으로 안 바뀌는 가 싶어서 String 으로 변환 해 주고 작업 하였다. 사실 toJSONString 해도 정상 동작 해야 하는데 이유를 잘 모르겠음. 그리고 나서 다시 이클립스 구동 하니 toString 도 먹은 걸로 봐서 이상하다고 생각! String dataString = authData.toString(); dataString = dataString.replaceAll("\\\\", ""); 어쨌든 백 슬래시 제거를 해줘야 하는데 \\ 도 아니고 \\\\를 해야 변환이 가능했다는 결말이었습니다. 참고 : https://stackoverflow.com/questions/15450519/why-does-string-replace-not-work/15450539 test =test.replace("KP", "");  replace 후에 담아 주지 않으면 적용이 안 됩니다!

개발 공부 - OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다.

여러 가지 요인이 있지만 PC 이름 변경시 OracleXETNSListener 서비스 시작이 불가능합니다. 고치는 법은 C:\oraclexe\app\oracle\product\11.2.0\server\network\ADMIN 와 같은 설치 경로에서 listener.ora와 tnsnames.ora 의 pc명을 바꾼 PC명으로 바꿔주면 됩니다. 그래도 안 된다면 cmd 창에서 services.msc 를 입력 후 OracleXETNSListener 서비스를 시작 시키면 됩니다. 오류명: OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다. 일부 서비스는 다른 서비스 또는 프로그램에서 사용되지 않으면 자동으로 중지됩니다. 참고한 사이트들 1. http://blog.naver.com/visioner7/120165951652 2. http://database.sarang.net/?inc=read&aid=6819&criteria=oracle&subcrit=&id=&limit=20&keyword=ora-12560&page=5 이런 걸 보면 오라클은 앙칼진 시골 아가씨야