[Algorithm] 자물쇠와 열쇠

프로그래머스 문제

https://programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

풀이

1. 키를 자물쇠 범위 안에 맞추지 않아도 일부만 맞아서 채워져도 된다.

 자물쇠의 범위를 늘린다. 상하좌우를 늘림. (자물쇠만큼 늘려줬다.)

 

2. 키를 돌려가면서 맞추고자 했다. (하나의 공간에서 4개 경우의 수)

 키 돌리는 메서드 작성 turn90

 

3. 자물쇠 범위에 키를 더하고, 체크해서 안에 합이 1로만 이루어진 경우 통과 true

class Solution {
    
    public static int[][] turn90 (int[][] a) {
        int n = a.length;
        int m = a[0].length;
        int[][] result = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                result[j][n-1-j] = a[i][j];
            }
        }
        return result;
    }
    
    public static boolean check (int[][] newLock, int n, int m) {
        // 가운데 값 체크
        int sum = 0;
        boolean answer = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sum += newLock[m+i][m+j];
            }
        }
        if (sum == (n * n)) {
            answer = true;
        }
        return answer;
    }
    
    public boolean solution(int[][] key, int[][] lock) {
        boolean answer = true;
        
        int m = key.length;
        int n = lock.length;
        
        int size = n + (m * 2);
        int[][] newLock = new int[size][size];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                newLock[m+i][m+j] = lock[i][j];
            }
        }
        
        int[][] tmp = new int[size][size];
        for (int a = 0; a < 4; a++) {
            key = turn90(key);
            // 키의 왼쪽 윗 칸이 0,0 -> n+m, n+m까지 가면서 turn90 3회 확인, turn 1회 하면서 다음칸으로
            for (int i = 0; i <= n+m; i++) {
                for (int j = 0; j <= n+m; j++) {
                    // i + n까지 확인
                    for (int x = i; x < i + n; x++) {
                        for (int y = j; y < j + n; y++) {
                            tmp[x][y] = newLock[x][y] + key[x-i][y-j];
                            if (check(tmp, n, m)) return true;
                        }
                    }
                }
            }
        }
        
        
        return answer;
    }
}

안된다. 문제를 찾자.

 

1. 체크하는 메서드에서 합으로 결산을 내는 것이 문제인가 싶어서 체크할 때 1이 아닌 수를 만나면 false를 리턴하도록 했다. (아직 해결 안됨)

public static boolean check (int[][] newLock, int n, int m) {
	// 가운데 값 체크
	int sum = 0;
	boolean answer = true;
	for (int i = 0; i < n; i++) {
  		for (int j = 0; j < n; j++) {
  			if (newLock[m+i][m+j] != 1) answer = false;
  		}
 	}
 	return answer;
}

2. 기준을 바꿔서, 기존에 키와 맞출 공간의 왼쪽 위 칸을 기준으로 잡았는데, 기준점은 이동하기 때문에 내부에서 키와 맞춰보는 이중 for문은 0 ~ m-1로 맞춰서 식을 바꿈.

for (int i = 0; i < n+m; i++) {
	for (int j = 0; j < n+m; j++) {
		// i + n까지 확인
		for (int x = 0; x < m; x++) {
			for (int y = 0; y < m; y++) {
				tmp[i+x][j+y] = newLock[i+x][j+y] + key[x][y];
				if (check(tmp, n, m)) return true;
			}
		}
	}
}

런타임 에러는 해결되었으나, 아직 실패하는 테스트 케이스 존재함.

 

3. 기본 값 answer 이 true로 되어있는 문제 false로 변경, 아직 해결 안됨

4. 생각해보니 tmp를 배열을 넘기는데, for 문이 도는 동안 누적됨. 처음 키에서 true를 찾지 못하면 계속 false로 남게 됨. tmp를 초기화 해줘야 함. 근데 생각해보니 tmp를 초기화하면 배열을 계속 생성하게 된다. 그래서 newLock에서 더했다가 빼주는 것이 효율적으로 보임.

5. 그리고 체크하는 if 문이 더하기가 끝나고 난 다음 체크하도록 변경함.

6. turn90 메서드에서 오타.... i를 빼줘야 하는데 j를 빼줌.

 

최종 소스 코드

class Solution {
    
    public static int[][] turn90 (int[][] a) {
        int n = a.length;
        int m = a[0].length;
        int[][] result = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                result[j][n-1-i] = a[i][j];
            }
        }
        return result;
    }
    
    public static boolean check (int[][] newLock, int n, int m) {
        // 가운데 값 체크
        for (int i = m; i < m + n; i++) {
            for (int j = m; j < m + n; j++) {
                if (newLock[i][j] != 1) return false;
            }
        }
        return true;
    }
    
    public boolean solution(int[][] key, int[][] lock) {
        
        int m = key.length;
        int n = lock.length;
        
        int size = n + (m * 2);
        int[][] newLock = new int[size][size];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                newLock[m+i][m+j] = lock[i][j];
            }
        }
        
        
        for (int a = 0; a < 4; a++) {
            key = turn90(key);
            // 키당 newLock은 size가 m + n + m 으로 구성됨.
            for (int i = 0; i < m + n; i++) {
                for (int j = 0; j < m + n; j++) {
                    // i + n까지 확인
                    for (int x = 0; x < m; x++) {
                        for (int y = 0; y < m; y++) {
                            newLock[i+x][j+y] += key[x][y];
                        }
                    }
                    // 체크
                    if (check(newLock, n, m)) return true;
                    
                    // 아니면 다시 빼줌
                    for (int x = 0; x < m; x++) {
                        for (int y = 0; y < m; y++) {
                            newLock[i+x][j+y] -= key[x][y];
                        }
                    }
                }
            }
        }
        return false;
    }
}

로직이 삽입되어야 하는 곳을 정확히 봐야 한다.

오타를 줄여야 한다. (i, j가 헷갈리면 차라리 확실한 변수를 사용하자)