프로그래머스 - 자물쇠와 열쇠 (java)

1. 문제

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

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

문제 설명

제한 사항

입출력 예

---

2. 어떻게 풀까?

• lock을 가만히 두고 key를 끝에서 1 x 1에서 n x n까지 이동시키면서 홈에 맞는지 확인한다.
• 맞지 않는다면 key를 90도 회전한다.
• key를 4번 회전시켜도 그대로라면 false를 리턴한다.

시작 지점, lock이 전부 채워지지 않았으므로 x

오른쪽으로 한칸 옮겼을 때, 역시 맞지 않음

오른쪽 끝으로 갔을때, 역시 맞지 않음!!

90도 회전 한번 하고, 오른쪽으로 세 칸, 아래로 세칸 이동시키면 홈에 딱 맞는다. 그러므로 true 리턴

• 위와 같이 생각했는데, 코드로 어떻게 구현해야 할지 감이 안 와서 고민하다가 결국 다른 사람이 푼 코드를 참고했다.
• 코드를 보니, 반대로 생각했다. key는 가만히 두고, lock을 움직이면서 key와 맞는지 체크한다.
• 코드로 구현하기 위해서 key에 padding을 했다.

이런식으로 (lock의 길이 -1) 만큼 상하좌우로 padding한 key의 모습이다.

그리고 lock을 처음 위치에서 오른쪽으로 한 칸, 아래로 한 칸 이동했을때 홈이 딱 맞게된다. 

---

3. 코드

테스트 코드

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

  @Test
  public void test1() {
    int[][] key = {
        {0, 0, 0},
        {1, 0, 0},
        {0, 1, 1}
    };
    int[][] lock = {
        {1, 1, 1},
        {1, 1, 0},
        {1, 0, 1}
    };
    assertThat(new Solution().solution(key, lock), is(true));
  }
}

실제 코드

public class Solution {

  public boolean solution(int[][] key, int[][] lock) {
    int padSize = lock.length - 1;

    for (int i = 0; i < 4; i++) {
      key = rotate(key);
      int[][] paddedKey = pad(key, padSize);
      for (int j = 0; j < paddedKey.length - padSize; j++) {
        for (int k = 0; k < paddedKey.length - padSize; k++) {
          if (isValid(lock, paddedKey, j, k)) {
            return true;
          }
        }
      }
    }

    return false;
  }

  private boolean isValid(int[][] lock, int[][] paddedKey, int j, int k) {
    for (int l = 0; l < lock.length; l++) {
      for (int m = 0; m < lock.length; m++) {
        if (lock[l][m] + paddedKey[j + l][k + m] != 1) {
          return false;
        }
      }
    }
    return true;
  }

  private int[][] pad(int[][] key, int padSize) {
    int[][] result = new int[key.length + padSize * 2][key.length + padSize * 2];

    for (int i = 0; i < key.length; i++) {
      for (int j = 0; j < key.length; j++) {
        result[padSize + i][padSize + j] = key[i][j];
      }
    }
    return result;
  }

  private int[][] rotate(int[][] key) {
    int[][] result = new int[key.length][key.length];
    for (int i = 0; i < key.length; i++) {
      for (int j = 0; j < key.length; j++) {
        result[i][j] = key[key.length - 1 - j][i];
      }
    }
    return result;
  }

  private int[][] copy(int[][] key) {
    int[][] result = new int[key.length][key.length];
    for (int i = 0; i < key.length; i++) {
      for (int j = 0; j < key.length; j++) {
        result[i][j] = key[i][j];
      }
    }
    return result;
  }
}

• rotate() 에서 key를 오른쪽 90도로 회전한다.
• pad()에서 lock의 length - 1 만큼 상하좌우로 추가하여 padding 해준다.
• pad된 key의 0부터 끝까지 가는 게 아니라 key까지만 이동한다. 더 이동하면 lock이 pad범위를 벗어나기 때문

---

4. 느낀 점

• 문제를 처음 보고, 어렵지만 할 수 있겠다고 생각했다. 실제로 문제 해결 방법은 맞다고 생각한다.
• 근데 이것을 코드로 구현하는 과정이 너무 어렵다.. 이걸 잘해야 level 3 문제들을 풀 수 있을 듯.