들어가며
https://www.acmicpc.net/problem/14890
문제를 간단하게 요약하자면, 행과 열이 각각 문제없이 지나갈 수 있는지 카운팅해서 그 지나갈 수 있는 길의 갯수를 출력해주면 되는 문제였다. 높이가 일정하다면 그냥 통과할 수 있는 길이지만, 3 3 2 2 3 3 같은 경우 길이가 2인 경사로를 두어서 지나갈 수도 있다.
그래서인지 문제를 처음에 읽었을 때는 완탐 문제인줄 알고 풀이에 들어갔다. 구현하면서 시간 복잡도가 무조건 터질 거 같고 계속 이게 맞나? 라는 생각으로 구현을 이어갔다.(코테에서 이러면 그냥 망할듯... 문제 잘 읽자). 너무 이상해서 문제를 다시 이해해보니, 행과 열을 건널 수 있는지 따로 확인하는 문제였다!!
본문으로
아래는 정답 코드이다. 2시간동안 디버깅해봤는데 인덱싱이나 조건 관련해서 너무너무 헷갈려서 ai에게 물어봤다...(분하다..) 특히 오르막길과 내리막길을 둘다 나누어서 할 생각을 하지 못했다... 문제 해석을 아예 잘못했다보니 너무 다른 길로 생각중이었다.
public class Main {
static int N, L, ret;
static int[][] maps;
static boolean checkLine(int[] line) {
boolean[] used = new boolean[N]; // 체크하려는 길 안에서 경사로로 사용한 길인지
for (int i = 0; i < N - 1; i++) {
int cur = line[i];
int nxt = line[i + 1];
if (cur == nxt) {
continue;
}
if (Math.abs(cur - nxt) > 1) {
return false;
}
// 내리막: cur -> nxt(cur = nxt + 1), nxt부터 L칸이 모두 nxt여야 내리막 경사로 가능
if (cur == nxt + 1) {
for (int k = i + 1; k <= i + L; k++) { // 내리막은 앞으로 진행
if (k >= N) {
return false; // 범위 넘으면 경사로 x
}
if (line[k] != nxt) { // 높이가 일정하지 않으면 경사로 X
return false;
}
if (used[k]) { // 사용한 곳이면 경사로 x
return false;
}
used[k] = true;
}
// 오르막: cur -> nxt(cur + 1 = nxt + 1), cur부터 뒤로 L칸이 모두 cur이여야 오르막 경사로 가능
} else if (cur + 1 == nxt) {
for (int k = i; k >= i - L + 1; k--) {
if (k < 0) { // 범위 체크
return false;
}
if (line[k] != cur) { // 뒤로 높이가 같아야 경사로를 놓을 수 있음.
return false;
}
if (used[k]) { // 전에 놓았던 곳인가.
return false;
}
used[k] = true;
}
}
}
return true;
}
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
maps = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer input = new StringTokenizer(bf.readLine());
for (int j = 0; j < N; j++) {
maps[i][j] = Integer.parseInt(input.nextToken());
}
}
ret = 0;
// 가로
for (int i = 0; i < N; i++) {
int[] line = new int[N];
for (int j = 0; j < N; j++) {
line[j] = maps[i][j];
}
if (checkLine(line)) {
ret++;
}
}
// 새로
for (int i = 0; i < N; i++) {
int[] line = new int[N];
for (int j = 0; j < N; j++) {
line[j] = maps[j][i];
}
if (checkLine(line)) {
ret++;
}
}
System.out.println(ret);
}
}
아래는 다른분들 풀이 보다가 너무 괜찮은 아이디어가 있어서 참고해서 다시 구현해봤다. 위의 코드는 행과 열을 둘다 체크하며 행의 인덱스를 증가시키는 로직과 열의 인덱스를 증가시키는 로직을 따로 구현했었다. 아래의 그림처럼 배열을 오른쪽으로 90도 회전한다면, 행을 검사하는 로직 하나만으로 모든 행과 열을 테스트 할 수 있다! 정말 좋은 아이디어지 않은가!
아래는 다시 제출한 코드이다
public class Main {
static int N, L, ret;
static int[][] maps, rMaps;
static void go(int[][] ways) {
for (int i = 0; i < N; i++) {
int cnt = 1;
int j;
for (j = 0; j < N - 1; j++) {
if (ways[i][j] == ways[i][j + 1]) {
cnt++;
} else if (ways[i][j] + 1 == ways[i][j + 1] && cnt >= L) {
cnt = 1;
} else if (ways[i][j] - 1 == ways[i][j + 1] && cnt >= 0) {
cnt = -L + 1;
} else {
break;
}
}
if (j == N - 1 && cnt >= 0) {
ret++;
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
maps = new int[N][N];
rMaps = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer input = new StringTokenizer(bf.readLine());
for (int j = 0; j < N; j++) {
int height = Integer.parseInt(input.nextToken());
maps[i][j] = height;
rMaps[j][i] = height;
}
}
go(maps);
go(rMaps);
System.out.println(ret);
}
}
근데 코드를 다시 자세히 보면 아래 부분이 내가 처음에 제출했던 코드와 완전 다르다. 완전 다른 아이디어길래 적용해보았다.
static void go(int[][] ways) {
for (int i = 0; i < N; i++) {
int cnt = 1;
int j;
for (j = 0; j < N - 1; j++) {
if (ways[i][j] == ways[i][j + 1]) { // 평지일때
cnt++;
} else if (ways[i][j] + 1 == ways[i][j + 1] && cnt >= L) { // 오르막일때
cnt = 1;
} else if (ways[i][j] - 1 == ways[i][j + 1] && cnt >= 0) { // 내리막일때
cnt = -L + 1;
} else {
break;
}
}
if (j == N - 1 && cnt >= 0) {
ret++;
}
}
}평지(높이가 같을때)이면 cnt를 ++하면서 지나가다가 오르막일때 그전에 같은 높이였던 블럭이 L개 이상 있었으면(cnt >= L) cnt를 1로 초기화하며 넘어간다. 아니면 바로 break이다.
내리막일때는 앞으로 L칸을 채워나가야 한다는 의미로, cnt = -L + 1를 한다. 그럼 다음 for문에서 내리막 높이와 같은 블럭들이 나오면 음수인 cnt를 ++시키며 경사로를 완성시키지 않겠는가! 조금 이해하기 어려워 예시는 다음과같다.
(L=3): 3 2 2 2
- 시작 → cnt = -2 (-3 + 1)
- 2 → cnt=-1
- 2 → cnt=0 (공사 완료)
그래서 안쪽 for문이 끝난 후 즉 길 하나를 탐색한 후에 if (j == N - 1 && cnt >= 0) 끝까지 왔고, cnt가 음수가 아니면 길에 추가한다!
마무리하며
정말 문제 이해가 어려운 빡구현 문제였다... 다 이해하고 나니 괜찮아보이지만, 코테 당일날 이런 문제가 나오면 제한시간 내에 풀어낼 수 있을까 싶다... 프로그래머스에 있는 기출들을 보면 문제들이 정말 길던데,,,, 막막하다~
기본 스킬들을 습득하고 나면 시간안에 푸는 연습을 꼭 해야할 것 같다!
계속 연습하자!!!