[소프티어] 우물 안 개구리 | JavaScript

문제출처

1. 문제

헬스장에서 N명의 회원이 운동을 하고 있다. 각 회원은 1에서 N사이의 번호가 부여되어 있고, i번 회원이 들 수 있는 역기의 무게는 Wi이다. 회원들 사이에는 M개의 친분관계 (Aj, Bj)가 있다. (Aj, Bj)는 Aj번 회원과 Bj번 회원이 친분 관계가 있다는 것을 의미한다. i번 회원은 자신과 친분 관계가 있는 다른 회원보다 들 수 있는 역기의 무게가 무거우면 자신이 최고라고 생각한다. 단, 누구와도 친분이 없는 멤버는 본인이 최고라고 생각한다.

이 헬스장에서 자신이 최고라고 생각하는 회원은 몇 명인가?

제약조건

2 ≤ N ≤ 10^5
1 ≤ M ≤ 10^5
1 ≤ Wi ≤ 10^9
1 ≤ Aj, Bj ≤ N
Aj ≠ Bj

입력형식

첫 번째 줄에 두 정수 N, M이 주어진다.
두 번째 줄에 N개의 정수 W1, W2, ... , WN 이 주어진다.
다음 M개의 줄의 j번째 줄에는 두 정수 Aj, Bj 가 주어진다.

출력형식

첫 번째 줄에 자신이 최고라고 생각하는 회원 수를 출력한다.

입력예제1

5 3
1 2 3 4 5
1 3
2 4
2 5

출력예제1

3

입력예제2

5 3
7 5 7 7 1
1 2
2 3
3 4

출력예제2

2

2. 풀이

첫 번째로 푼 방식은 선택된 회원을 세는 방식이고, 두 번째 방식은 선택되지 않은 회원을 세는 방식이다.

첫 번째 방식으로 풀었더니 틀렸고, 두 번째 방식으로 풀어보니 맞았다.
두 무게가 같은 경우 두 명 모두 자신이 최고라고 생각하는 회원이 될 수 없으므로 두 번째 방식으로 푸는 게 맞다.

공통적으로 사용한 방식은 다음과 같다.

• 멤버의 번호를 index로 사용하기 위해 역기의 무게를 저장한 배열(weights ) 맨 앞에 0을 추가한다.

2.1. 틀린 코드

그 다음 아래의 첫 번째로 작성한 코드는

• 회원수+1개 길이의 배열을 생성 후 0으로 채워준다.(frog_member)
• for문을 돌면서

  • a의 무게가 b의 무게보다 크다면 frog_member에 해당하는 인덱스 값을 1로 바꾼다.

  • b의 무게가 a의 무게보다 크다면 frog_member에 해당하는 인덱스 값을 1로 바꾼다.

  • a와 b의 무게가 같다면 아무런 조치를 취하지 않는다.

    • 이 경우를 처리하지 않아서 해당되는 두 사람(a, b)이 최고라고 생각하는 회원이 될 수 없음에도 선택될 수 있다.

// 틀린 코드 //

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let lines = [];

rl.on("line", (line) => {
  lines.push(line.split(" ").map(Number));
}).on("close", () => {
  // [회원 수, 친분관계 개수]
  let [members, connects] = lines[0];
  // 회원 번호를 인덱스로 사용하기 위해 맨 앞에 0추가
  let weights = [0, ...lines[1]];
  let frog_member = new Array(members + 1).fill(0);

  for (let i = 2; i < lines.length; i++) {
    let a = lines[i][0];
    let b = lines[i][1];

    if (weights[a] > weights[b]) {
      frog_member[a] = 1;
    } else if (weights[b] > weights[a]) {
      frog_member[b] = 1;
    }
  }

  console.log(frog_member.reduce((acc, cur) => acc + cur, 0));
  process.exit();
});

2.2. 통과한 코드

두 번째 방식은 다음과 같다.

• 회원수+1개 길이의 배열을 생성 후 1로 채워준다.(frog_member)
• for문을 돌면서
  • a의 무게가 b의 무게보다 크다면 frog_member에 해당하는 인덱스 값을 0로 바꾼다.
  • b의 무게가 a의 무게보다 크다면 frog_member에 해당하는 인덱스 값을 0으로 바꾼다.
  • a와 b의 무게가 같다면 frog_member에 해당하는 두 인덱스 값을 모두 0으로 바꾼다.

이렇게 코드를 작성했더니 모든 경우의 수를 처리하였기 때문에 문제를 통과할 수 있었다.

// 통과한 코드 //

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let lines = [];

rl.on("line", (line) => {
  lines.push(line.split(" ").map(Number));
}).on("close", () => {
  // [회원 수, 친분관계 개수]
  let [members, connects] = lines[0];
  // 회원 번호를 인덱스로 사용하기 위해 맨 앞에 0추가
  let weights = [0, ...lines[1]];
  let frog_member = new Array(members + 1).fill(1);

  // 최고라고 생각하는 회원이 될 수 없는 회원 처리
  for (let i = 2; i < lines.length; i++) {
    let a = lines[i][0];
    let b = lines[i][1];

    if (weights[a] > weights[b]) {
      frog_member[b] = 0;
    } else if (weights[b] > weights[a]) {
      frog_member[a] = 0;
    } else {
      frog_member[a] = 0;
      frog_member[b] = 0;
    }
  }

  // frog_member[0] = 1이므로 총 합에서 -1해주기
  console.log(frog_member.reduce((acc, cur) => acc + cur, 0) - 1);
  process.exit();
});