Algorithm

[Baekjoon]2491번 수열 - Javascript

호밀이 2023. 12. 29. 22:06

https://www.acmicpc.net/problem/2491

 

2491번: 수열

0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾

www.acmicpc.net

문제

0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라. 

예를 들어 수열 1, 2, 2, 4, 4, 5, 7, 7, 2 의 경우에는 1 ≤ 2 ≤ 2 ≤ 4 ≤ 4 ≤ 5 ≤ 7 ≤ 7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 수열 4, 1, 3, 3, 2, 2, 9, 2, 3 의 경우에는 3 ≥ 3 ≥ 2 ≥ 2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 또 1, 5, 3, 6, 4, 7, 1, 3, 2, 9, 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 2를 출력하여야 한다.

입력

첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다. N은 1 이상 100,000 이하의 정수이다.

출력

첫째 줄에 가장 긴 길이를 출력한다.

예제 입력 1 복사

9
1 2 2 4 4 5 7 7 2

예제 출력 1 복사

8

예제 입력 2 복사

9
4 1 3 3 2 2 9 2 3

예제 출력 2 복사

4

 

문제풀이(1)

연속해서 커지거나 작아지는 수열이 가장 큰 길이를 구하면된다.
연속해서 커지는지 확인하는 로직, 연속해서 작아지는지 확인하는 로직 2개가 필요하다.
같은 숫자 예를들어 2 -> 2는 연속해서 작아지거나 커지는 것으로 간주한다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [N, ...arr] = require("fs").readFileSync(filePath).toString().trim().split("\n");

const sequence = arr[0].split(" ").map(Number);

let upCount = 1;
let downCount = 1;

const answer = [];

for (let i = 0; i < Number(N); i++) {
  const nowNum = sequence[i];
  const nextNum = sequence[i + 1];

  if (nowNum <= nextNum) {
    upCount++;
  } else if (nowNum > nextNum) {
    upCount = 1;
  }

  if (nowNum >= nextNum) {
    downCount++;
  } else if (nowNum < nextNum) {
    downCount = 1;
  }
  answer.push(upCount);
  answer.push(downCount);
}

console.log(Math.max(...answer));

 

문제풀이(2)

1. 배열에 모든 count를 넣는 것이 아니라 바로 비교하여 메모리 최적화
2. 최고 값을 찾는 max 메서드를 사용하지 않음으로 실행시간 최적화
메모리 - 20132kb -> 12192kb
실행시간 - 208ms -> 188ms

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [N, ...arr] = require("fs").readFileSync(filePath).toString().trim().split("\n");

const sequence = arr[0].split(" ").map(Number);

let upCount = 1;
let upResult = 1;

let downCount = 1;
let downResult = 1;

for (let i = 0; i < Number(N); i++) {
  const nowNum = sequence[i];
  const nextNum = sequence[i + 1];

  if (nowNum <= nextNum) {
    upCount++;
    if (upCount >= upResult) {
      upResult = upCount;
    }
  } else if (nowNum > nextNum) {
    upCount = 1;
  }

  if (nowNum >= nextNum) {
    downCount++;
    if (downCount >= downResult) {
      downResult = downCount;
    }
  } else if (nowNum < nextNum) {
    downCount = 1;
  }
}

console.log(upResult >= downResult ? upResult : downResult);