내 풀이
오답 풀이
요구사항을 하나하나 조건문으로 쳐내며 전부 구현했다.
다음 칸보다 이전 칸이 더 높을 때, 다음 칸의 개수를 세는 메소드를 구현했는데 그 부분에서 탐색 인덱스 오류를 방지하기 위해 y + 1 < N도 조건으로 걸어 탐색을 진행했다.
그 결과 채점 진행도 85%에서 멈추고 시간초과 오류가 생겼다. 아마 이 부분에서 무한루프가 돈 거 같다.
오답 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, L;
static int[][] map;
static int dNum, rNum, low, downRes, rightRes;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
map = new int[N][N];
downRes = 0;
rightRes = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
search();
int result = downRes + rightRes;
System.out.println(result);
}
static void search() {
for (int start = 0; start < N; start++) {
if (down(start)) {
downRes++;
}
if (right(start)) {
rightRes++;
}
}
}
static boolean down(int start) {
int cnt = 1;
int y = 1;
dNum = map[0][start];
while (y < N) {
if (dNum != map[y][start]) {
if (Math.abs(map[y][start] - dNum) == 1) {
if (dNum > map[y][start] && y + 1 < N) {
low = map[y][start];
int lowCnt = downLowCnt(start, y + 1, low);
if (lowCnt >= L && y+lowCnt-1 < N) {
cnt = lowCnt - L;
y += lowCnt;
dNum = map[y-1][start];
} else return false;
} else if (dNum < map[y][start]) {
if (cnt >= L) {
cnt = 1;
y += 1;
dNum = map[y-1][start];
} else return false;
} else return false;
} else return false;
} else {
cnt++;
y++;
}
}
return true;
}
static int downLowCnt(int i, int y, int low) {
int lowCnt = 1;
while (low == map[y][i]) {
lowCnt++;
y++;
if (y >= N)
break;
}
return lowCnt;
}
static boolean right(int start) {
int cnt = 1;
int x = 1;
rNum = map[start][0];
while (x < N) {
if (rNum != map[start][x]) {
if (Math.abs(map[start][x] - rNum) == 1) {
if (rNum > map[start][x] && x + 1 < N) {
low = map[start][x];
int lowCnt = rightLowCnt(start, x + 1, low);
if (lowCnt >= L && x+lowCnt-1 < N) {
cnt = lowCnt - L;
x += lowCnt;
rNum = map[start][x-1];
} else return false;
} else if (rNum < map[start][x]) {
if (cnt >= L) {
cnt = 1;
x += 1;
rNum = map[start][x-1];
} else return false;
} else return false;
} else return false;
} else {
cnt++;
x++;
}
}
return true;
}
static int rightLowCnt(int i, int x, int low) {
int lowCnt = 1;
while (low == map[i][x]) {
lowCnt++;
x++;
if (x >= N)
break;
}
return lowCnt;
}
}
정답 풀이
다음 과정을 거치며 시간초과 문제를 해결했다.
-
시간초과가 될 리가 없는 N의 최대 크기와 O(N^2)의 시간복잡도인데 자꾸 시간초과 오류가 생기길래 혹시나 해서 BufferedWriter까지 사용해 시도해봤지만 오류가 해결되지 않았다.
-
뭔가 로직에 오류가 있음을 예상하고 탐색이 더 진행될 필요가 없어지면 더이상 진행되지 않고 빨리 return문을 통해 빠져나가도록 여기저기 추가해보며 로직을 정리해보았지만 '틀렸습니다' 오류가 떴다.
-
조건문 중 y + 1 < N을 삭제하고 다음 칸보다 이전 칸이 더 높을 때, 다음 칸의 개수를 세는 메소드를 진행할 때 y가 N보다 크거나 같은 채로 넘어왔으면 바로 1인 lowCnt를 반환하도록 코드를 수정했더니 정답이 되었다.
구현문제 풀 때
1. 의사코드 꼼꼼하게 작성하기
2. 오류난다고 마음대로 이상한 조건 추가하지 않기,,
정답 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, L;
static int[][] map;
static int dNum, rNum, low, downRes, rightRes;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
map = new int[N][N];
downRes = 0;
rightRes = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
search();
int result = downRes + rightRes;
bw.write(Integer.toString(result));
bw.flush();
bw.close();
}
static void search() {
for (int start = 0; start < N; start++) {
if (down(start)) {
downRes++;
}
if (right(start)) {
rightRes++;
}
}
}
static boolean down(int start) {
int cnt = 1;
int y = 1;
dNum = map[0][start];
while (y < N) {
if (dNum != map[y][start]) {
if (Math.abs(map[y][start] - dNum) == 1) {
if (dNum > map[y][start]) {
low = map[y][start];
int lowCnt = downLowCnt(start, y + 1, low);
if (lowCnt >= L && y + lowCnt - 1 < N) {
cnt = lowCnt - L;
y += lowCnt;
dNum = map[y - 1][start];
} else return false;
} else {
if (cnt >= L) {
cnt = 1;
y += 1;
dNum = map[y - 1][start];
} else return false;
}
} else return false;
} else {
cnt++;
y++;
}
}
return true;
}
static int downLowCnt(int i, int y, int low) {
int lowCnt = 1;
if (y >= N)
return lowCnt;
while (low == map[y][i]) {
lowCnt++;
y++;
if (y >= N)
break;
}
return lowCnt;
}
static boolean right(int start) {
int cnt = 1;
int x = 1;
rNum = map[start][0];
while (x < N) {
if (rNum != map[start][x]) {
if (Math.abs(map[start][x] - rNum) == 1) {
if (rNum > map[start][x]) {
low = map[start][x];
int lowCnt = rightLowCnt(start, x + 1, low);
if (lowCnt >= L && x + lowCnt - 1 < N) {
cnt = lowCnt - L;
x += lowCnt;
rNum = map[start][x - 1];
} else return false;
} else {
if (cnt >= L) {
cnt = 1;
x += 1;
rNum = map[start][x - 1];
} else return false;
}
} else return false;
} else {
cnt++;
x++;
}
}
return true;
}
static int rightLowCnt(int i, int x, int low) {
int lowCnt = 1;
if (x >= N)
return lowCnt;
while (low == map[i][x]) {
lowCnt++;
x++;
if (x >= N)
break;
}
return lowCnt;
}
}
짱이 되고싶은 개발 기록