문제 탐색하기
입력 자료 정리
- n은 지도의 세로/가로 길이다.
- k은 경사로의 길이다
- 이어서 들어오는 nxn의 값은 각 지점의 높이다
해결방법 추론
- 입력 최대 크기도 작고, 조건도 까다롭기 때문에 복잡한 구현문제라고 생각했다
- 문제는 이해했는데, 처음에 잘못된 선택을 해서 시간을 많이 소요한 문제다
- 선택지는 두가지였다. 첫번째는 경사로를 미리 설치하고 탐색하는 것이고
두번째는 탐색하면서 경사로를 설치하는 조건이면 확인 후 설치하는 것이다 - 처음에는 첫번째 선택지로 구현하였다
- 먼저 세로줄과 가로줄을 따로 탐색하고, 두 지점간에 차이가 1인 경우 경사로를 설치하기로 결정했다
그리고 경사로를 설치하면 다른 방향에서 해당 지점에 다시 경사로를 설치할 때, 설치하지 못하도록 방문배열을 활용했다 - 하지만 해당 방법의 경우 다음 문제가 존재한다. 설치 경사로가 좌 -> 우인지 우 <- 좌인지도 구분해야한다
이 문제를 겪고 나니 해당 방법으로 해결하기에는 코드가 너무 난잡해져서 다른 방법을 고민했다 - 두번째 선택한 방법은 탐색하면서 필요할 때만 경사로를 설치하는 것이다
- 해당 경우는 앞선 경우와 다르게 4가지 메소드를 2가지 메소드로만 구현해도 되었기에 조금 편하게 구현할 수 있었다
- 이번에는 탐색하면서 만약 차이가 1이 되는 지점이 생긴다면 현재지점이 큰지 다음 지점이 큰지 구분해서
경사로를 설치하도록 설계했다 - 해당 경우에는 반드시 한 방향으로만 설치하도록 설계하였고, 똑같이 방문배열을 통해 같은 방향에서 중복으로 설치하지 못하도록 설계했다
- 이렇게 설계한 결과 드디어 모든 예제를 통과할 수 있었다
시간복잡도 계산
- 시간복잡도는 n^2만큼 탐색하면서 k길이의 경사로를 놓는 연산을 합해서
O(n^2 x k)의 시간복잡도가 발생한다 - 따라서 구현문제로 풀어도 시간제한안에 문제를 해결할 수 있다
코드 설계하기
입력값 상태 관리
- 모든 크기 입력값은 int형 변수로 관리하며, 각 지점의 높이는 int형 2차원 배열에 보관했다
크기는 n x n이다 - 정답을 출력하기 위해 ans를 0으로 초기화하였다
구현 코드 설계
세로줄 가로줄 구분
- 세로줄과 가로줄을 구분하기 위해 둘을 다른 메소드로 구분하였고, 각각 n만큼 탐색했다
- 조건에 맞는 경우 ans를 증가시킨다
- 각 메소드에서는 경사로의 방문상태를 체크하는 n크기의 1차원 방문배열을 선언한다
- 아래 공통 부분은 고정/변동 인덱스의 위치만 서로 다를 뿐이지 로직은 똑같다
(공통) 차이 계산 및 검증
- 처음에는 차이를 절댓값으로 계산했으나 현재와 다음 지점 중 더 큰 지점을 확인하기 위해,
절댓값을 사용하지 않고 차이를 변수에 담았다 - 만약 차이가 1보다 크거나 -1보다 작은 경우 조건을 만족하지 못하므로 false를 리턴한다
(공통) 다음 지점이 더 큰 경우
- 다음 지점이 큰경우 차이는 -1이다.
- 해당 경우, k만큼 탐색하면서 경사로를 설치한다
- i-j가 0보다 작거나 해당 인덱스의 경사로를 이미 설치한 경우 false를 리턴한다
- 이어서 처음 지점 i와 i-j 지점의 높이가 같지 않으면 false를 리턴한다
- 모든 조건을 만족하는 경우 경사로 배열의 i-j인덱스 값을 true로 설정한다
(공통) 현재 지점이 더 큰 경우
- 해당 경우는 위와 같이 진행하는데, i+j인 경우로 변경해서 진행한다
- 또한 0보다 작은 경우가 아닌 n이상인 경우 false를 리턴하도록 한다
- 모든 조건을 만족하면 true를 리턴한다
출력값 설계
- 완성한 ans를 출력하면 정답이 된다!
정답 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[][] arr = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
if(checkHor(n,arr,i,k)){
ans++;
}
}
for (int i = 0; i < n; i++) {
if(checkVer(n,arr,i,k)){
ans++;
}
}
bw.write(ans+"");
br.close();
bw.close();
}
private static boolean checkVer(int n, int[][] arr, int vertical, int k){
boolean[] cline = new boolean[n];
for (int i = 0; i < n - 1; i++) {
int diff = arr[vertical][i] - arr[vertical][i+1];
if(diff > 1 || diff < -1){
return false;
}else if(diff == -1){
for (int j = 0; j < k; j++) {
if(i - j < 0 || cline[i-j]){
return false;
}
if(arr[vertical][i] != arr[vertical][i-j]){
return false;
}
cline[i-j] = true;
}
}else if(diff == 1){
for (int j = 1; j <= k; j++) {
if(i+j >= n || cline[i+j]){
return false;
}
if(arr[vertical][i] - 1 != arr[vertical][i+j]){
return false;
}
cline[i+j] = true;
}
}
}
return true;
}
private static boolean checkHor(int n, int[][] arr, int horizontal, int k) {
boolean[] cline = new boolean[n];
for (int i = 0; i < n - 1; i++) {
int diff = arr[i][horizontal] - arr[i+1][horizontal];
if(diff > 1 || diff < -1){
return false;
}else if(diff == -1){
for (int j = 0; j < k; j++) {
if(i- j < 0 || cline[i-j]){
return false;
}
if(arr[i][horizontal] != arr[i-j][horizontal]){
return false;
}
cline[i-j] = true;
}
}else if(diff == 1){
for (int j = 1; j <= k; j++) {
if(i+j >= n || cline[i+j]){
return false;
}
if(arr[i][horizontal] - 1 != arr[i+j][horizontal]){
return false;
}
cline[i+j] = true;
}
}
}
return true;
}
}문제 링크
Software Developer