탐색 문제풀이
큰 수 출력하기
N(1<=N<=100)개의 정수를 입력받아, 자신의 바로 앞 수보다 큰 수만 출력하는 프로그램을 작성하세요.(첫 번째 수는 무조건 출력한다) 첫 줄에 자연수 N이 주어지고, 그 다음 줄에 N개의 정수가 입력된다. 자신의 바로 앞 수보다 큰 수만 한 줄로 출력한다.
- 입력예제
6
7 3 9 5 6 12
- 출력예제
7 9 6 12
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const input1 = parseInt(input[0]);
const input2 = input[1].split(" ").map(Number);
//solution함수 안에 답안을 작성하세요.
function solution(input1, input2) {
let answer = String(input2[0]) + " ";
for (i = 1; i < input1; i++) {
if (input2[i] > input2[i - 1]) answer += String(input2[i]) + " ";
}
console.log(answer);
}
solution(input1, input2);
- 풀이 해설
String(number)를 사용할 때 첫 문자가 S임을 명심! (일종의 생성자임)
보이는 학생
선생님이 N(1<=N<=1000)명의 학생을 일렬로 세웠습니다. 일렬로 서 있는 학생의 키가 앞에서부터 순서대로 주어질 때, 맨 앞에 서 있는 선생님이 볼 수 있는 학생의 수를 구하는 프로그램을 작성하세요. (앞에 서 있는 사람들보다 크면 보이고, 작거나 같으면 보이지 않습니다.) 첫 줄에 정수 N이 입력된다. 그 다음줄에 N명의 학생의 키가 앞에서부터 순서대로 주어진다. 선생님이 볼 수 있는 최대학생수를 출력한다.
- 입력예제
8
130 135 148 140 145 150 150 153
- 출력예제
5
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const input1 = parseInt(input[0]);
const input2 = input[1].split(" ").map(Number);
//solution함수 안에 답안을 작성하세요.
function solution(input1, input2) {
let answer = 1;
let max = 0;
for (i = 1; i < input1; i++) {
if (input2[i] > max) {
max = input2[i];
answer++;
}
}
console.log(answer);
}
solution(input1, input2);
- 풀이 해설
최댓값이 갱신될 때마다 answer를 증가시킨다.
가위 바위 보
A와 B가 N번 가위바위보 합니다. 가위, 바위, 보의 정보는 1:가위, 2:바위, 3:보로 정하겠습니다.
첫 번째 줄에 게임 횟수인 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에는 A가 낸 가위, 바위, 보 정보가 N개 주어집니다.
세 번째 줄에는 B가 낸 가위, 바위, 보 정보가 N개 주어집니다.
A가 이기면 A, B가 이기면 B, 비기면 D가 출력됩니다.
- 입력예제
5
2 3 3 1 3
1 1 2 2 3
- 출력예제
A
B
A
B
D
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const input1 = parseInt(input[0]);
const input2 = input[1].split(" ").map(Number);
const input3 = input[2].split(" ").map(Number);
//solution함수 안에 답안을 작성하세요.
function solution(input1, input2, input3) {
let answer;
let aLst = input2;
let bLst = input3;
for (i = 0; i < input1; i++) {
if (aLst[i] == bLst[i]) answer = "D";
else if (aLst[i] == bLst[i] + 1 || (aLst[i] == 1 && bLst[i] == 3))
answer = "A";
else answer = "B";
console.log(answer);
}
}
solution(input1, input2, input3);
- 풀이 해설
if문과 불리언을 활용할 수 있는지를 묻는 문제. 가위바위보의 규칙을 if문을 3번 쓰거나 불리언으로 정의할 수 있다.
점수계산
맞춘 문제는 1, 틀린 문제는 0으로 표시한다. 문제를 맞추면 1점을 준다. 연속으로 맞추면 1점씩 가산한다. K문제를 연속으로 맞추면 K점을 준다.
가령 아래의 입력예제를 연산하면 1 + 1 + (1+1) + (1+1+1) + 1 + (1+1) = 10점이다.
- 입력예제
10
1 0 1 1 1 0 0 1 1 0
- 출력예제
10
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const input1 = parseInt(input[0]);
const input2 = input[1].split(" ").map(Number);
//solution함수 안에 답안을 작성하세요.
function solution(input1, input2) {
let answer;
let score = input2[0];
let adder = 0;
for (i = 1; i < input1; i++) {
if (input2[i] === 1) {
score++;
if (input2[i - 1]) {
adder++;
score += adder;
} else adder = 0;
}
}
answer = score;
console.log(answer);
}
solution(input1, input2);
- 풀이 해설
변수 adder를 선언하여 가산점을 계산. adder를 0으로 초기화하는 방법에 대해 다양한 방식이 있을 수 있다.
등수구하기
N(1<=N<=100)명의 학생의 국어점수가 입력되면 각 학생의 등수를 입력된 순서대로 출력하는 프로그램을 작성하세요. 첫 줄에 N(3<=N<=1000)이 입력되고, 두 번째 줄에 국어점수를 의미하는 N개의 정수가 입력된다. 같은 점수가 입력될 경우 높은 등수로 동일 처리한다. 즉 가장 높은 점수가 92점인데 92점이 3명 존재하면 1등이 3명이고 그 다음 학생은 4등이 된다.
- 입력예제
5
87 89 92 100 76
- 출력예제
4 3 2 1 5
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const input1 = parseInt(input[0]);
const input2 = input[1].split(" ").map(Number);
//solution함수 안에 답안을 작성하세요.
function solution(input1, input2) {
let answer = "";
let rank = input2.slice();
rank.sort((a, b) => b - a);
for (score of input2) {
answer += String(rank.indexOf(score) + 1) + " ";
}
console.log(answer);
}
solution(input1, input2);
- 풀이 해설
ArrayProto.sort(callback(){})을 참고하자.
본 문제의 경우 기존 배열과 새로운 배열을 '얕은 복사' 해야한다. [JavaScript] 깊은 복사, 얕은 복사
격자판 최대합
N*N의 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가 장 큰 합을 출력합
니다.
- 입력예제
5
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
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const { arrayBuffer } = require("stream/consumers");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\r\n");
const input1 = parseInt(input[0]);
const input2 = [];
for (i = 0; i < input1; i++) {
input2[i] = input[i + 1].split(" ").map(Number);
}
//solution함수 안에 답안을 작성하세요.
function solution(input1, input2) {
let answer;
let n = input1;
let mt = input2;
let max = 0;
let dia1 = 0;
let dia2 = 0;
for (i = 0; i < n; i++) {
let sum_row = 0;
let sum_col = 0;
for (j = 0; j < n; j++) {
sum_row += mt[i][j];
sum_col += mt[j][i];
}
if (sum_row > max) max = sum_row;
if (sum_col > max) max = sum_col;
dia1 += mt[i][i];
dia2 += mt[4 - i][i];
}
if (dia1 > max) max = dia1;
if (dia2 > max) max = dia2;
answer = max;
console.log(answer);
}
solution(input1, input2);
- 풀이 해설
이중포문을 이용하여 합을 구하는 행렬 문제이다. 행렬을 입력받을 때부터 어떻게 split을 할지 고민하여 행렬을 제작하자. 일반적으로 행렬은 mt[행][열]의 구조를 띄게 된다.
if문이 사용된 부분은 Math.max()메서드를 이용하여 max = Math.max(max, sumRow, sumCol);로 표현할 수 있다.
봉우리
N*N 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요. 격자의 가장자리는 0으로 초기화 되었다고 가정한다. 만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다.
0 0 0 0 0 0 0
0 5 3 7 2 3 0
0 3 7 1 6 1 0
0 7 2 5 3 4 0
0 4 3 6 4 1 0
0 8 7 3 5 2 0
0 0 0 0 0 0 0
- 입력예제
5
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
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const input1 = parseInt(input[0]);
const input2 = [];
for (i = 0; i < input1; i++) {
input2[i] = input[i + 1].split(" ").map(Number);
}
//solution함수 안에 답안을 작성하세요.
function solution(input1, input2) {
let answer;
let dx = [0, 0, -1, 1];
let dy = [1, -1, 0, 0];
let counter = 25;
for (let y = 0; y < input1; y++) {
for (let x = 0; x < input1; x++) {
for (let i = 0; i < 4; i++) {
if (
x + dx[i] < 0 ||
x + dx[i] >= input1 ||
y + dy[i] < 0 ||
y + dy[i] >= input1
)
continue;
if (input2[x + dx[i]][y + dy[i]] >= input2[x][y]) {
counter--;
break;
}
}
}
}
answer = counter;
console.log(answer);
}
solution(input1, input2);
- 풀이 해설
행렬의 벡터값 dx, dy을 활용한 구현 문제이다. 좌표가 (0,0)인 (x, y)의 상, 하, 좌, 우의 각 좌표 (dx, dy)는 (0,-1)(0,1)(-1,0)(1,0)이다.
이를 표로 만들면 다음과 같다.
const dx = [0, 0, -1, 1]
const dy = [-1, 1, 0, 0]
for(i=0; i<4; 1++) {
console.log(`(${dx[i]}, ${dy[i]})`)
}
i 인덱스가 순회하는 동안 벡터는 상, 하, 좌, 우를 탐색하게 된다. 해당 벡터값을 이중for문과 결합하게 된다.
문자열 탐색
회문 문자열
회문이면 YES, 회문이 아니면 NO를 출력하라.
- 입력예제
gooG
- 출력예제
YES
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim();
//solution함수 안에 답안을 작성하세요.
function solution(input) {
let answer = "YES";
let str = input.toLowerCase();
for (i = 0; i < parseInt(str.length) / 2; i++) {
if (str[i] !== str[str.length - 1 - i]) {
answer = "NO";
break;
}
}
console.log(answer);
}
solution(input);
- 풀이 해설
펠린드롬 문제이다. 투포인터를 이용해 풀이하였다. 유의할 점은 StringProto.toLowerCase()는 리턴값을 받아줄 변수가 필요하다는 점이다. 본 풀이에서는 str로 input.toLowerCase()의 리턴값을 받아 풀이하였다.
유효한 팰린드롬
문자열이 앞에서 읽을때나 뒤에서 읽을 때나 같은 팰린드롬이면 YES, 아니면 NO를 출력하라.
알파벳 이외의 글자는 무시하며, 대소문자를 구분하지 않는다.
- 입력예제
found7, time: study; Yduts; emit, 7Dnuof
- 출력예제
YES
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim();
//solution함수 안에 답안을 작성하세요.
function solution(input) {
let answer = "YES";
let str = input.toLowerCase().replace(/[^a-z]/g, "");
if (str !== str.split("").reverse().join("")) answer = "NO";
console.log(answer);
}
solution(input);
- 풀이 해설
팰린드롬을 reverse를 이용해 풀었다.
StringProto.replace('찾을 문자', '바꿀 문자') : 찾을 문자에 정규표현식이 들어갈 수 있다.
정규표현식(RegExp) 정규표현식의 개념과 패턴 사용법 총정리 [JavaScript] replace(치환) 및 정규식 RegExp | PoiemaWeb [JS] 📚 정규식 (RegExp) - 누구나 이해하기 쉽게 정리
-
정규표현식을 사용할 때에는 표현식 앞, 뒤로 /를 감싼다.
-
[/^표현식/] : 해당 표현식에 해당하지 않는 것을 반환한다.
-
플래그 [/표현식/igm] : 표현식 뒤에 i, g, m의 표현식을 사용할 수 있다.
-
- i : Ignore Case - 대소문자 무관하게 탐색한다.
-
g : Global - 문자열 전역을 검사합니다. g가 없으면 최초 검색결과만 만환합니다.
-
m : multiline - 문자열이 여러줄로 적혀있는 경우 여러줄 모두를 검색합니다.
숫자만 추출
문자와 숫자가 섞여있는 문자열이 주어지면 그 중 숫자만 추출하여 그 순서대로 자연수를 만
듭니다.
- 입력예제
g0en2T0s8eSoft
- 출력예제
208
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim();
//solution함수 안에 답안을 작성하세요.
function solution(input) {
let answer = "YES";
let str = input.toLowerCase().replace(/[^\d]/g, "");
answer = parseInt(str);
console.log(answer);
}
solution(input);
- 풀이 해설
정규표현식 \d는 digital number를 의미한다.
가장 짧은 문자거리
한 개의 문자열 s와 문자 t가 주어지면 문자열 s의 각 문자가 문자 t와 떨어진 최소거리를 출력하는 프로그램을 작성하세요.
- 입력예제
teachermode e
- 출력예제
1 0 1 2 1 0 1 2 2 1 0
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim().split(" ");
const s = input[0];
const t = input[1];
//solution함수 안에 답안을 작성하세요.
function solution(s, t) {
let answer = [];
let distance = Number.MAX_SAFE_INTEGER;
//앞에서 부터 탐색
for (c of s) {
if (c === t) {
distance = 0;
answer.push(distance);
} else {
answer.push(++distance);
}
}
//거꾸로 탐색하는 방법
distance = Number.MAX_SAFE_INTEGER;
for (i = s.length - 1; i >= 0; i--) {
if (s[i] === t) distance = 0;
else {
Math.min(++distance, answer[i]);
}
}
console.log(answer);
}
solution(s, t);
- 풀이 해설
부분합을 이용한 문제
문자열 압축
같은 문자가 연속으로 반복되는 경우 반복되는 문자 바로 오른쪽에 반복 횟수를 표기하는 방법으로 문자열을 압축. 단 반복횟수가 1인 경우 생략한다.
- 입력예제
KKHSSSSSSSE
- 출력예제
K2HS7E
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim();
//solution함수 안에 답안을 작성하세요.
function solution(s) {
let answer = s[0];
let cnt = 1;
for (i = 1; i < s.length; i++) {
if (s[i] === s[i - 1]) cnt++;
else {
if (cnt > 1) answer += String(cnt);
cnt = 1;
answer += s[i];
}
}
console.log(answer);
}
solution(input);
- 풀이 해설
절차가 중요. answer의 초깃값을 무엇으로 두는지, cnt를 언제 answer로 넘겨주는지 등을 꼼꼼히 체크하며 진행할 것.
cnt가 1인 경우 생략하도록 문제에서 요구하는데, 이 경우는 그냥 if문으로 예외처리 하는 것이 편함