Keep Going

탐색문제 유형 중 하나인 봉우리 개수를 찾는 문제이다.

문제

N*N격자판이 주어지고 높이가 쓰여있다. 각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역이다. 봉우리 지역이 몇 개인지 알아내는 프로그램을 작성해보자. 

입력예제 |

5 3 7 2 3

3 7 1 6 1

7 2 5 3 4

4 3 6 4 1

8 7 3 5 2

출력예제 |

10

접근

1. 기준점을 정하고 네 방향을 탐색한다. 이중 for문으로 2차원 배열을 탐색한다. (if문 남발하지않고 작성)

2. 배열의 각 요소를 탐색하면서 상하좌우 크기 비교 -> 나보다 큰게 없으면 봉우리다 -> 카운팅한다.

풀이

세부적으로 풀이를 해보면,

1.

내 좌표(기준점) 에서 상하좌우 좌표를 구해야한다. 

자신과 상하좌우 숫자를 비교해야한다. 움직여야할 행과 열을 배열로 작성한다. (시계방향) 

행과 열은 세트로 움직인다. 

상, 하 → 행 이동

행 = [상, 우, 하, 좌] →  dx = [-1, 0, 1, 0] 

좌, 우 → 열 이동

열 = [상, 우, 하, 좌] →  dy = [0, 1, 0, -1] 

2.

내 좌표(기준점)은 i과 j가 이중for문을 돌면서 좌표를 구한다. 

3.

상하좌우, 4번 k for문 돌아야한다.

내 좌표의 값과 네 방향의 좌표 비교해서, 네 방향이 더 작으면 answer++한다. 

let nx = i+dx[k]; → i에 -1이나 1을 더해 행을 옮긴다 (상하이동)
let ny = j+dy[k]; → j에 -1이나 1을 더해 열을 옮긴다 (좌우이동)

상 → 행이 -1로 이동할 때 열은 0 이동 (열 이동없음)

하 → 행이 1로 이동할 때 열은 0 이동 (열 이동없음)

좌 → 열이 1 이동할 때 행은 0 이동 (행 이동없음)

우 → 열이 -1 이동할 때 열은 0 이동 (행 이동없음)

4.

flag는 봉우리인지 아닌지 체크한다.

flag가 0이면 answer 카운팅 안되고, 1이면 카운팅된다. 

코드

function solution(arr){
            let answer = 0; //카운팅해야되니까 0으로 
            let n = arr.length;
            let dx = [-1, 0, 1, 0];
            let dy = [0, 1, 0, -1];
            for(let i=0; i<n; i++){
                for(let j=0; j<n; j++){
                    let flag=1;
                    for(let k=0; k<4; k++){ // 4방향이라서 4번돌도록 맞춤
                        let nx = i+dx[k]; // 가려고하는 방향 행 좌표
                        let ny = j+dy[k]; // 가려고하는 방향 열 좌표 
                        if(nx>=0 && nx<n && ny>=0 && ny<n && arr[nx][ny] >= arr[i][j]){ 
                            // arr[nx][ny]상하좌우좌표 >= 현재지점좌표 arr[i][j]
                            // nx>=0 && nx<n && ny>=0 && ny<n는 
                            // 내 상하좌우가 네방향으로 존재하지 않는 경우도 있으니 그 경우는 제외하는 조건
                            // 현재지점 좌표보다 큰게 있으면 봉우리가 아니다. 이걸 확인하기 위해서 flag변수 작성해준 것
                            flag=0;
                            break; // k for문 멈춤
                        }  
                    }
                    if(flag) answer++; 
                    // 상하좌우 다 돌고 나와서 flag가 그대로이면 answer++ 해준다
                }
            }
            return answer;
        }

    let arr = [[5, 3, 7, 2, 3],
                [3, 7, 1, 6, 1],
                [7, 2, 5, 3, 4],
                [4, 3, 6, 4, 1],
                [8, 7, 3, 5, 2]];
    console.log(solution(arr));

문제

N*N 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가장 큰 합을 출력하세요.

입력예제 |

10 13 10 12 15

12 39 30 23 11

11 25 50 53 15

19 27 29 37 27

19 13 30 13 19

출력예제 | 

155

풀이

1. 각 행의 합, 각 열의 합 구한다. (합을 구해야할 때는 sum 변수 만들어주어야함. 여기서는 행의 합, 열의 합 필요해서 2개 선언)

2. 각 대각선의 합 구한다.

3. 비교해서 최대값을 구해서 answer에 넣는다. 

4. answer 출력

function solution(arr){
            let answer = Number.MIN_SAFE_INTEGER;
            // 1. answer는 최대값을 찾아야하니까 최소값으로 초기화 해놓는다. 
            let n = arr.length;
            let sum1 = 0;
            let sum2 = 0;
            // 행의 합은 sum1로 저장
            // 열의 합은 sum2로 저장
            // 행 탐색, 열 탐색을 이중for문으로
            for(let i = 0; i < n; i++){
                sum1 = 0;
                sum2 = 0;
                // for문이 한 번 끝날 때마다 매번 초기화를 시켜줘야한다.
                for(let j = 0; j < n; j++){
                    sum1 += arr[i][j]; // i가 돌고 j 고정(i기준 j의 모든 값 더하여 누적)
                    sum2 += arr[j][i]; // j가 돌고 i 고정(j기준 i의 모든 값 더하여 누적)
                    // 행이 돌고 열이 고정된다
                }
                answer = Math.max(answer, sum1, sum2); 
                // 최대값 구하는 메소드
            }
            
            // 이제 대각선의 합 구하는 for문 작성
            // 새로 대각선 합 구해야해서 초기화 해주어야한다.
            sum1 = 0; 
            sum2 = 0;
            for(let i = 0; i < n; i++){
                sum1 = arr[i][i]; // 똑같은 인덱스의 행과 열 
                sum2 = arr[i][n-i-1]; // sum1과 대칭인 값을 구해주어야한다.
            }
            answer = Math.max(answer, sum1, sum2);
            return answer;
    }
        

llet arr = [[10, 13, 10, 12, 15],
            [12, 39, 30, 23, 11],
            [11, 25, 50, 53, 15],
            [19, 27, 29, 37, 27],
            [19, 13, 30, 13, 19]];
        console.log(solution(arr));

행과 열을 같이 탐색해야하므로 이중for문을 사용해준다.

행 -> i / 열 -> j

function solution(arr){
        let answer;
        let n = arr.length;
        let sum1 = 0;
        let sum2 = 0;
        for(let i = 0; i < n; i++){
            sum1 = 0;
            sum2 = 0;
            for(let j = 0; j < n; j++){
                sum1 += arr[i][j];
                sum2 += arr[j][i];
            }
            answer = Math.max(sum1, sum2);
        }
        sum1 = 0;
        sum2 = 0;
        for(let i = 0; i < n; i++){
                sum1 += arr[i][i];
                sum2 += arr[i][n-i-1];
        }
        answer = Math.max(sum1, sum2);
        return answer;
    }

        let arr = [[10, 13, 10, 12, 15],
                   [12, 39, 30, 23, 11],
                   [11, 25, 50, 53, 15],
                   [19, 27, 29, 37, 27],
                   [19, 13, 30, 13, 19]];
        console.log(solution(arr));

answer에 가장 작은 정수를 써주지 않고도 작성이 가능하다.

여기서 더 알아보아야할 개념! 

for문이 돌때마다 sum 변수를 초기화해주는 것.

자바스크립트 스코프 개념 정리할 것

알게된 개념

2차원 배열

배열안에 또 다른 배열이 있는 것 

2차원 배열은  행과 열이 있다. 

행과 열이 있을때, 행부터 써준다.

arr[행][열]

문제

N(1<=N<=100)명의 학생의 국어점수가 입력되면 각 학생의 등수를 입력된 순서대로 출력하는 프로그램을 작성하세요. 같은 점수가 입력될 경우 높은 등수로 동일 처리한다. 즉 가장 높은 점수가 92점인데 92점이 3명 존재하면 1등이 3명이고 그 다음 학생은 4등이 된다.

입력예제 | 87 89 92 100 76

출력예제 | 4 3 2 1 5

풀이

이중 for문을 사용한다. 값을 두개씩 비교하면서 조건에 충족하면 answer를 ++하는 방법을 사용한다. 

이중for문 개념

for(let i = 0; i < 5; i++){
	for(let j = 0; j < arr.length; j++){
	}
}

i = 0 일 때, j가 0부터 arr.length 까지 돈다. 

i = 1 일 때, j가 0부터 arr.length 까지 돈다.

i = 2 일 때, j가 0부터 arr.length 까지 돈다.

i = 3 일 때, j가 0부터 arr.length 까지 돈다.

i = 4 일 때, j가 0부터 arr.length 까지 돈다.

처음에 푼 방법1

function solution(arr){
	let answer = [];
    
    let count = 1;
    for(let i = 0; i < arr.length; i++){
    	for(let j = 0; j < arr.length; j++){
        	if(arr[j] > arr[i]) {
            	count++; 
            } else count = 0;
            answer.push(count);
            }
            return answer;
     	}
}
        
let arr = [87, 89, 92, 100, 76];
console.log(solution(arr));

처음에 푼 방법2

const solution = (arr) => {
  let answer = [];

  for (let i = 0; i < arr.length; i++) {
    let count = 0;
    for (let j = 0; j < arr.length; j++) {
      if (arr[i] < arr[j]) count++;
    }
    answer.push(count + 1);
  }
  return answer;
}

const arr = [87, 89, 92, 92, 76];
console.log(solution(arr));

현재값arr[i]이 arr[j]보다 작으면 카운팅,

내 값에서 +1한 값을 answer배열에 누적한다. 

다른 풀이

1로 초기화된 1차원 배열을 answer에 미리 만들어놓는다.

let n = arr.length;
let answer = Array.from({length:n}, ()=>1);
// Array.from으로 배열의 모든 요소를 1로 바꿔주었다. 
// [1, 1, 1, 1, 1]

function solution(arr){
	let n = arr.length;
	let answer = Array.from({length:n}, ()=>1);
		for(let i = 0; i < n; i++){
			for(let j = 0; j < n; j++){
				if(arr[j] > arr[i]) answer[i]++;
                // answer의 i번째 값을 ++ 해준다.
                // answer는 배열이니까 answer배열의 i번째에 넣어서 ++ 해줘야한다.
            }
         }
         return answer;
        
}
        
let arr = [87, 89, 92, 100, 76];
console.log(solution(arr));

사용한 개념

Array.from

배열값을 변경하여 새로운 배열 생성

유사배열객체arrayLike나 반복 가능한 객체를 얕게 복사해서 새로운 Array 객체를 만든다. 

배열값 각각에 원하는 연산을 수행해서 새로운 배열 생성하기

console.log(Array.from('foo'));
// expected output: Array ["f", "o", "o"]

console.log(Array.from([1, 2, 3], x => x + x));
// expected output: Array [2, 4, 6]
// 콜백함수로 화살표 함수 사용

1. 문제

OX문제 시험에서 연속적으로 답을 맞히는 경우에는 가산점을 주기로 했다. 앞의 문제에 대해서는 답을 틀리다가 답이 맞는 처음 문제는 1점으로 계산한다. 또한, 연속으로 문제의 답이 맞는 경우에서 두 번째 문제는 2점, 세 번째 문제는 3점, ..., K번째 문제는 K점으로 계산한다. 틀린 문제는 0점으로 계산한다. 답이 맞은 문제의 경우에는 1로 표시하고, 틀린 경우에는 0으로 표시한다. 채점 결과가 주어졌을 때, 총 점수를 계산하는 프로그램을 작성하세요.

입력 예제 | 1 0 1 1 1 0 0 1 1 0

출력 예제 | 10

2. 문제풀이과정

1. 배열 탐색(for 반복문) 

2. 하나씩 돌면서 점수를 누적해주는데, 가산점을 같이 더하면서 계산해주어야 한다. 

[시도 1]

function solution(arr){
	let answer = 0;
    for(let i=0; i<arr.length; i++){
    	if(A[i] === 1){
        	answer += 1;
        } else answer += 0;
     }
     return answer;
}

let A = [1, 0, 1, 1, 1, 0, 0, 1, 1, 0];
console.log(solution(A));

처음에 이렇게 작성했는데, 가산점 계산이 안되어서 6이 나왔다. 

가산점 계산을 하려면 뭔가 요소가 더 필요한 것 같은데 뭘까 고민하다가

[시도 2]

function solution(arr){
	let answer = 0;
    let count;
    for(let i=0; i<arr.length; i++){
    	if(A[i] === 1){
        	answer += 1;
            count = answer++;
        } else answer += 0;
     }
     return count;
}

let A = [1, 0, 1, 1, 1, 0, 0, 1, 1, 0];
console.log(solution(A));

count 변수를 하나 더 만들어줘서 answer+1값이 count에 누적되도록 했다. 

그렇지만 아직 계산이 정확히 되지 않았다. 

[시도 3]

function solution(arr){
	let answer = 0;
    let count = 0;
    	for(let i=0; i<arr.length; i++){
        	if(arr[i] === 1){
            	count++; // count = count + 1
                answer+=count; // answer = answer + count // answer에 count누적
            } else count=0; // 0이 들어올 경우 count 초기화 
         }
    return answer;
}

let A = [1, 0, 1, 1, 1, 0, 0, 1, 1, 0];
console.log(solution(A));

answer와 count에 모두 누적을 해줘야하니까 0으로 설정해준다. 

count에 값을 먼저 더하고, answer에 count를 더해서 누적해준다. 

0점일 경우는 count를 다시 0으로 만든다. 

for of 문(배열의 값을 기반으로 반복)을 써도 가능하다! 

function solution(arr){
	let answer = 0;
    let count = 0;
    	for(x of arr){
        	if(x === 1){
            	count++; // count = count + 1
                answer+=count; // answer = answer + count
            } else count=0;
         }
    return answer;
}

let A = [1, 0, 1, 1, 1, 0, 0, 1, 1, 0];
console.log(solution(A));

1. 문제

총 N번의 게임을 하여 A가 이기면 A를 출력하고, B가 이기면 B를 출력합니다.

비길 경우에는 D를 출력합니다. 두 사람의 각 회의 가위, 바위, 보 정보가 주어지면

각 회를 누가 이겼는지 출력하는 프로그램을 작성하세요.

가위, 바위, 보의 정보는 1:가위, 2:바위, 3:보로 정하겠습니다.

입력예제 | 

A 2 3 3 1 3

B 1 1 2 2 3

출력예제 | ABABD

2. 문제풀이

for문으로 A와 B의 배열을 하나씩 돌면서,

조건문으로 A가 이기는 상황을 만들고 A를 answer에 넣어주고, 그 외 상황은 B가 answer에 들어가도록 한다. 

function solution(A, B){
	let answet = "";
    for(let i=0; i<A.length; i++){
		if(A[i] === B[i]) answer = "D";
        // 여기서 부터 A가 이기는 상황 기준으로 써주기
        else if (A[i] === 1 && B[i] === 3) answer += "A";
        else if (A[i] === 2 && B[i] === 1) answer += "A";
        else if (A[i] === 3 && B[i] === 2) answer += "A";
        else answer += "B";
     }
     return answer;
}



let A = [2, 3, 3, 1, 3];
let B = [1, 1, 2, 2, 3];
console.log(solution(A, B));

분류를 해야할 때는 기준을 잘 잡아야한다. 여기서는 A가 이기는 것에 기준을 두고 그 외에는 모두 B가 출력되도록 했다.

3. 사용개념

논리 연산자 && 사용해서 양쪽 모두 참이어야 true가 반환된다. 하나라도 거짓이면 else if / else로 넘어간다.

1. 문제

선생님이 N(1<=N<=1000)명의 학생을 일렬로 세웠습니다. 일렬로 서 있는 학생의 키가 앞에서부터 순서대로 주어질 때, 맨 앞에 서 있는 선생님이 볼 수 있는 학생의 수를 구하는 프로그램을 작성하세요. (앞에 서 있는 사람들보다 크면 보이고, 작거나 같으면 보이지 않습니다.)

입력예제 | 130 135 148 140 145 150 150 153

출력예제 | 5

2. 문제풀이

배열을 돌면서(for문) 조건에 충족하면(if문) answer에 누적해서 리턴한다.

max 바꾸면서 비교하는건 최대값 구하는 거랑 같다.

function solution(arr){
    let answer = 1;
    // 첫번째 사람은 무조건 보이니까 카운팅 1부터
    let max = arr[0]; // max는 첫번째 사람의 키로 초기화
    for(let i=1; i < arr.length; i++){
        if(arr[i] > max) {
            max = arr[i];
            answer++;
    } 
    return answer;
    }
}
let arr = [130, 135, 148, 140, 145, 150, 150, 153];
console.log(solution(arr));

처음에 이렇게 작성했는데 제대로 값이 나오지 않았다. 

조건 arr[i]가 max보다 크면 answer++ 카운팅 먼저해주고 max값을 바꿔줘야한다. 

function solution(arr){
    let answer = 1;
    // 첫번째 사람은 무조건 보이니까 카운팅 1부터
    let max = arr[0]; // max는 첫번째 사람의 키로 초기화
    for(let i=1; i < arr.length; i++){
        if(arr[i] > max) {
        	answer++;
            max = arr[i];
    } 
    return answer;
    }
}
let arr = [130, 135, 148, 140, 145, 150, 150, 153];
console.log(solution(arr));

1. 문제

N(1<=N<=100)개의 정수를 입력받아, 자신의 바로 앞 수보다 큰 수만 출력하는 프로그램을 작성하세요.(첫 번째 수는 무조건 출력한다)

입력예제 | 7 3 9 5 6 12

출력예제 | 7 9 6 12

2. 문제풀이

1차원 배열 탐색하는 기본적인 문제

배열을 돌면서(for문) 조건에 충족하는 값들만(if문) answer에 넣어서 리턴한다. 

function solution(arr){
	let answet = [];
    answer.push(arr[0]); // 첫번째 수는 무조건 출력해야하므로 미리 써주고
    for(let i = 1; i < arr.length; i++){
    // 0번은 입력해줬으니까 1번부터 돈다
    	if(arr[i] > arr[i-1]) answer.push(arr[i]);
        // 자신의 바로 앞수보다 커야하니까 자신(i)와 자신바로앞(i-1)을 비교해서 자신(i)가 크면 조건 충족
    }
    return answer;
}

let arr = [7, 3, 9, 5, 6, 12];
console.log(solution(arr));
        
        

1차원 배열 탐색하는 기본적인 문제

1. 문제

N개의 문자열이 입력되면 중복된 문자열은 제거하고 출력하는 프로그램을 작성하세요. 출력하는 문자열은 원래의 입력순서를 유지합니다.

입력예제 | 

good

time

good

time

student

출력예제 |

good

time

student

2. 문제풀이

중복 문자 제거가 String.indexOf()를 사용했다면,

중복 단어 제거는 Array.indexOf()를 사용하는 문제이다.

function solution(str){
	let answer = [];
    for(let i =; i < str.length; i++){
    	if(str.indexOf(str[i] === i) answer += str[i];
    }
    return answer;
}

let str = ["good", "time", "good", "time", "student"];
console.log(solution(str));

처음에는 이렇게만 해서 값은 제대로 나왔지만 배열로 나오지 않았다.

Array.filter() 메소드 사용해서 조건을 만족하는 요소들만 받아서 새로운 배열을 만들어야한다. 

filter() 메소드는 콜백함수를 인자로 받는데, 콜백함수는 인자로 value, index, array 순서대로 받는다.

function solution(str){
	let answer;
    anwser = str.filter((value, i) => { 
    // filter의 콜백함수는 매개변수로 값, 인덱스, 배열 순서대로 받는다. 따로 변수지정을 안해줘도 된다. 
    	if(str.indexOf(value) === i) return value;
        // 값의 첫번째 인덱스 번호가 실제 인덱스 번호와 같은지 확인하고 맞으면 값 리턴한다.
    });
    return answer;
}

let str = ["good", "time", "good", "time", "student"];
console.log(solution(str));

3. 사용한 개념

String.indexOf()

문자열에서 주어진 값과 일치하는 첫 번째 인덱스를 반환

Array.indexOf()

배열에서 주어진 값과 일치하는 첫 번째 인덱스를 반환

Array.filter(값, 인덱스, 원래배열)

콜백함수의 조건을 만족하는 요소만 받아서 새로운 배열을 만든다.

배열 내 각 요소에 콜백함수를 호출에서 리턴값이 true인 애들로 새로운 배열 만든다. false이면 버린다. 

// 패턴
let result = students.filter((student) => student.enrolled);
// 화살표 함수로 배열 student중에 등록된 애들만 뽑아서 새로운 배열을 만든다.