활주로 건설(경사로 문제)

문제 이해 : 생각하고 싶은 대로 생각하지 말고, 문제에서 주어진 대로 생각하라. 지나갈 수 있는 길이 되는 경우 1. 모든 칸의 높이가 모두 같은 경우 2. 경사로를 놓아서 "지나갈 수 있는 길"을 만들 수 있다. => 오해 : 경사로를 놓아서 모든 칸의 높이를 같게 만드는 것이 아니라, 문제에서 주어진대로, 경사로를 놓는다면(경사로 놓는 조건 만족한다면) "지나갈 수 있는 길"이라고 한다.

아래 그림처럼 경사로를 놓기만 한다면, 한칸의 높이가 다르다고 하더라도, "경사로를 놓음"으로써 "지나갈 수 있는 길" 이 되는 것이다.

경사로 문제와 똑같은, 아니 그냥 경사로 문제였다.

이문제에서 중요한 핵심

1. 문제 정확하게 이해

2. 정확한 이해를 바탕으로 로직 설계

맞은 부분

1. 경사로가 오르막일 때, 내리막일 때, i번째 칸과 높이(배열값) 1차이가 나는 인덱스(i+1 또는 i-1)에서부터 i+1과 동일한 칸이 K개 나와야하기 때문에 N개 행(열)에 대해 반복하는 반복문과 그 밑에 K에 대한 반복문 구조✅

2. 배열 범위 초과 , 중복 처리 제외✅

정답 코드와 다른 부분

1. 내리막 길 : k 반복문 틀린 이유 경사로 길이 K=2이고, 3 2 2 에서 높이차이가 발생하는 3의 인덱스 i를 5라고 하면, i+1=6이다. i+1를 포함해서 K개 비교를 반복해야하는데, k<K로 해버리면 현재 k=i+1 = 6인데 K=2로 조건을 만족하지 않게 된다. => 인덱스 값 자체로 반복 조건 거는 것이 아니라, 차이가 발생하는 값의 인덱스부터 K개, 갯수로 반복 조건 구성해야한다! i=5라고 하면, i=7까지 비교를 해야하는 것이다. 그렇기 때문에 i+K까지 비교하는 것으로 나타낼 수 있다!

	내 코드	정답
k 반복문	for(int k=i+1;k<K;k++)	for(intk=i+1;k<=i+K;k++)

2. 오르막길 : 내코드N-1부터 시작하는 반복문에서 i번째와 i-1번째를 비교

	내 코드	정답
값 비교	for(int i=N-1;i>=1;i--) if(arr[i]-arr[i-1] == 1) i번째와 i-1번째를 비교!	for(int i=0;i<N-1;i++){ if(arr[i]+1 == arr[i+1]) i번째와 i+1번째를 비교! =>1번 내리막길과 동일한 for문 사용 가능!
k 반복문	for(int k=i-1;k-1>=0;k--)	for(int k=k;j>=i+1-K;k--)

3. 높이 같을 때⭐️⭐️⭐️⭐️⭐️

내 코드	정답
별개의 N-1 for문으로 같은지 비교해서 카운팅+1 증가	전체 하나의 for문에서 continue처리 solve()함수의 디폴트 리턴값은 true =>메인에서 solve() 리턴값 true이면 활주로 조건 만족처리되어 1 증가한다!

4. 1,2,3번 경우 연결 관계

내 코드	정답
3개의 반복문	N 반복문 내에 if-else문으로 1,2, 구현 N 반복문 내에 배열 값 같은 경우 continue문으로 3 구현

백트랙킹⭐️⭐️⭐️⭐️⭐️ 각 칸의 차이가 1보다 크면 경사로를 놓지 못하기 때문에, 이에 따라 활주로 건설도 못한다! 그러므로 false를 리턴하면 된다!

if(Math.abs(arr[i]-arr[i+1]) > 1) return false;

알고리즘, 코드 설계

💡문제 정확하게 이해하고, 알고리즘을 설계해야 한다. 높이 차이가 1인 경우, 경사로 조건 불만족 => 정답에 해당❌ 바로 false리턴. 높이 차이가 1인 경우, 경사로를 놓을 수 있다. 하지만 경사로를 놓는 조건에 충족하지 못하면 높이 차이가 그대로 1이고, 이에 따라 활주로도 건설하지 못하기 때문에 전체 정답으로 카운팅하지 않는다. => i, i+1 번째와 높이 비교하고, 높이가 다르면 그 때의 i+1부터 비교를 반복되도록 했는데, 이 때는 추가적인 비교는 전혀 불필요한 연산이다. 문제를 제대로 정확하게 이해하지 않았다고 할 수 있겠다.

💡정답 소스의 코드 설계(feat.디폴트:true 리턴하는 함수) 하나의 for문에서 오르막, 내리막인 경우, 높이 같은 경우를 모두 처리하며, 디폴트로 true를 리턴하고, 경사로 만족 조건에 해당되지 않는 것들은 false 리턴 처리한다. 상당히 매우 깔끔하다... 경사로를 놓는 조건이 ① 범위체크, ② 중복 체크, ③ 연속된 동일한 높이 체크 로 체크할 조건들이 많다. 그렇기 때문에 이 3가지 조건을 AND로 다 만족하면 true를 리턴해도 되지만, 3가지 조건을 OR로 연결해서 false처리하는 것이 더 간편할 것 같다. 또한 문제를 정확하게 이해하고 로직을 설계한다면, 높이가 같은 경우, 전체 N for문에서 값이 같은 경우, 그냥 continue처리만으로 true를 리턴해서 정답에 카운팅할 수 있다.⭐️⭐️⭐️⭐️⭐️

💡리팩토링 : 3항 연산자를 이용하여 10줄짜리 코드를 3줄로 줄일 수 있다. 반복되는 중복을 피하자!

if(dir == 0) {//idx번째 가로행 
		for(int j=0;j<N;j++) {
			arr[j] = Map[idx][j];
		}
}
    else if(dir == 1) {//idx번째 세로행 
			for(int i=0;i<N;i++) {
				arr[i] = Map[i][idx];
		}
}

for(int i=0;i<N;i++) {
  arr[i] = (dir==0)?Map[idx][i]:Map[i][idx];
}

문제 알고리즘 정리

1. 2N개의 행, 열 순회

2. 차이가 "1" 발생할 때 경사로 놓는 조건 검사 : solve()함수는 경사로 놓을 수 있으면 true, 없으면 false를 리턴.(+ 조건 검사할 때, 경사로 없이 활주로 만족하는 경우도 함께 true를 리턴할 수 있음)

3. 조건 만족(리턴값 true)하면 정답에 카운팅