강의로 돌아가기
반례 및 힌트
[0, 1, 3, 0],
[1, 2, 0, 0],
[3, 0, 2, 2],
[0, 2, 0, 0]
답 : 8
힌트 :
n = 8 일때 시계를 회전시켜보는 모든 경우의 수는 464 이지만
greedy하게 접근해본다면 48 로 한정할 수 있습니다.
+ :
맨 윗줄의 시계를 어떻게 회전시킬지 미리 정해놓으면,
그 아랫줄의 시계는 몇번 회전시킬지 바로 윗칸의 값만 보고 판단하면 됩니다.
그렇게 맨 아랫줄까지 회전을 시켜보고, 모든 칸을 0으로 만들었을 경우에만 최솟값을 구하면 정답이 됩니다.
즉 맨 윗줄을 회전시켜보는 경우의 수 4n 만 따져보면 됩니다.
이 경우 탐색횟수는 4n x n2 회, n = 8일 때 222 회가 됩니다.
10번 테스트케이스에서 90ms 소요됐습니다.
나중에 누가 더 좋은 풀이를 가져오겠지요..
-
2차원 동전 뒤집기하고 접근법이 비슷하군요. SQL문제도 비슷한 테이블로 몇문제씩 내던데. 첫행에 모든 경우의 수를 생성하고 다음행부터 제거하는 방식으로 하는 거네요
Jang Sungil―2022.12.27 11:38
-
와우.. 정말 좋은 풀이라고 생각됩니다. 한 수 배워갑니다.
전현서―2023.07.18 16:59
2x.webp)
2 개의 답변
천재적인 아이디어입니다.. 덕분에 풀었습니다.
근데 저와 실행 시간이 차이가 좀 많이 나네요.
저는 아래와 같이 풀었습니다. 방식은 같지만 비트마스킹을 활용하였습니다.
탐색 부분에서는 충분히 빠르다고 생각하는데 차이가 많이 나는 것을 보아 제 코드에 문제가 있거나 아니면 작성자님은 pruning이나 early return이 따로 있다고 생각이 듭니다.
혹시 그런 부분이 있다면 알려주시면 공부가 될 것 같습니다.
class Solution {
public int solution(int[][] clockHands) {
int min = 200;
int n = clockHands.length;
// 첫 줄 회전 조합을 비트마스크로 완전탐색 (2비트 * n칸 → 4^n)
Outter : for (int spins = 0; spins < (1 << n * 2); spins++) {
int[][] spinMap = new int[n][n]; // 각 칸이 누적 몇 번 회전했는지 기록
int sum = 0; // 전체 회전 횟수 누적합
// 첫 번째 줄 회전 조합 적용
for (int col = 0; col < n; col++) {
int spin = spins >> (col * 2) & 3; // 각 칸의 회전 횟수 추출 (2비트)
spinning(0, col, spin, spinMap); // 회전 영향 적용
sum += spin;
}
// 아래 줄은 위 칸을 12시로 맞추기 위해 필요한 회전 횟수를 유도
for (int row = 1; row < n; row++) {
for (int col = 0; col < n; col++) {
int upperState = (clockHands[row - 1][col] + spinMap[row - 1][col]) % 4;
int spin = (4 - upperState) % 4; // 위 칸을 12시로 맞추기 위한 회전 횟수
spinning(row, col, spin, spinMap);
sum += spin;
}
}
// 마지막 줄이 모두 12시 방향(0)이 되어야 유효한 케이스
for (int col = 0; col < n; col++) {
if ((clockHands[n - 1][col] + spinMap[n - 1][col]) % 4 != 0) continue Outter;
}
min = Math.min(min, sum); // 최소 회전 횟수 갱신
}
return min;
}
// (row, col) 위치의 시계를 spin번 돌릴 때, 자신과 상하좌우 시계에 영향 반영
public void spinning(int row, int col, int spin, int[][] spinMap) {
int n = spinMap.length;
int[] dx = {0, -1, 1, 0, 0};
int[] dy = {0, 0, 0, -1, 1};
for (int i = 0; i < 5; i++) {
int nx = row + dx[i];
int ny = col + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
spinMap[nx][ny] = (spinMap[nx][ny] + spin) % 4;
}
}
}
}
테스트 1 〉 통과 (0.12ms, 75.3MB)
테스트 2 〉 통과 (0.08ms, 78.8MB)
테스트 3 〉 통과 (1.49ms, 73.5MB)
테스트 4 〉 통과 (107.77ms, 126MB)
테스트 5 〉 통과 (61.85ms, 122MB)
테스트 6 〉 통과 (315.23ms, 369MB)
테스트 7 〉 통과 (297.48ms, 372MB)
테스트 8 〉 통과 (281.65ms, 363MB)
테스트 9 〉 통과 (306.07ms, 359MB)
테스트 10 〉 통과 (287.73ms, 365MB)
-
탐색횟수만큼 실행될 spinning 메서드의 dx랑 dy가 내부에 선언되어 있어서 매번 메모리 할당/해제 하느라 시간이 오래 걸렸나 보네요. 전역변수로 바꾸니 테스트케이스 10번도 100ms로 줄었습니다.
김영찬―2025.12.03 17:09
-
저는 회전횟수까지 비트마스크로 풀었는데...3년 지나고 보니까 주석도 없어서 무슨 의도로 썼는지 이해하는데 한참걸렸네요 ㅋㅋ
김영찬―2025.12.03 17:10
예전 코드긴 하지만 다른 사람의 코드에서 작성자님의 코드를 찾았습니다.
저도 처음엔 그와 비슷하게 풀었습니다.
결국엔 정확도 테스트를 통과하지 못해서 버렸지만요..
혹시 이 코드에서 문제점을 발견하신다면 피드백 주시면 감사하겠습니다..!
class Solution {
public int solution(int[][] clockHands) {
int min = 200;
int n = clockHands.length;
Outter : for (int spins = 0; spins < (1 << n * 2); spins++) {
int[][] cur = new int[n][n];
int sum = 0;
for (int col = 0; col < n; col++) {
int spin = spins >> col * 2 & 3;
cur[0][col] = (clockHands[0][col] + spin) % 4;
sum += spin;
}
int beforeSpins = spins;
for (int row = 1; row < n; row++) {
int nowSpins = 0;
for (int col = 0; col < n; col++) {
int topSpin = beforeSpins >> col * 2 & 3;
int leftSpin = (col == 0) ? 0 : (nowSpins >> (col - 1) * 2) & 3;
int spin = (4 - cur[row - 1][col]) % 4;
cur[row][col] = (clockHands[row][col] + topSpin + leftSpin + spin) % 4;
if (col > 0) cur[row][col - 1] = (cur[row][col - 1] + spin) % 4;
nowSpins |= spin << col * 2;
sum += spin;
}
beforeSpins = nowSpins;
}
for (int col = 0; col < n; col++) {
if (cur[n - 1][col] != 0) continue Outter;
}
min = Math.min(min, sum);
}
return min;
}
}
답변 쓰기