글 읽기 - 질문게시판의 테스트케이스들 시도해봤는데 반례륾 못찾겠네요 ㅠㅠ

sunyong0321 2년 전 0

안녕하세요

자바스크립트로 문제를 풀었는데

로컬에서는 질문게시판상 테스트케이스는 다 정답으로나오는데

시간초과도 아닌 틀렸습니다가 계속 나오고 반례 감이 안잡히네요

혹시 반례 보이시는 분 계실까요 ? ? ..

let fs = require('fs');
let stdin = fs.readFileSync('/dev/stdin').toString().split('\n');
const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

function check(x,y){
  visited[y][x]=1;
  cnt+=1;
  if(x-1>=0){
    if(board[y][x-1]==1 && visited[y][x-1]==0){
      check(x-1,y);
    }
  }
  if(x+1<n){
    if(board[y][x+1]==1 && visited[y][x+1]==0){
      check(x+1,y);
    }
  }
  if(y-1>=0){
    if(board[y-1][x]==1 && visited[y-1][x]==0){
      check(x,y-1);
    }
  }
  if(y+1<n){
    if(board[y+1][x]==1 && visited[y+1][x]==0){
      check(x,y+1);
    }
  }
}

let n = input().split(" ");
let board=[];
let visited=[];
for (let i=0;i<n;i++){
  let row=input().split("");
  board.push(row);
  visited.push(row.map((pos)=>{
    return 0;
  }));
}

let cnt=0;
let complexes=[]
board.forEach((row,by)=>{
  for(let [bx,pos] of row.entries()){
    if(pos==1 && visited[by][bx]==0){
      check(bx,by);
      if(cnt>0){
        complexes.push(cnt);
        cnt=0;
      }
    }
  }
});
complexes.sort();
console.log(complexes.length);
complexes.forEach((c)=>{
  console.log(c);
})


/* input
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

*/

wizardrabbit 2년 전 1

안녕하세요? 반례 드립니다:

preview

틀린 이유 한 줄 요약: 마지막 부분에서 정렬(sort)이 정수의 오름차순이 아닌, 사전 순(정확히는 유니코드 값 순)으로 정렬되고 있어요!

자바스크립트의 sort()는 기본적으로 정렬되는 데이터를 문자열로 간주하고, 유니코드 값을 기준으로 정렬합니다. 그렇기 때문에 결과적으로 사전 순으로 정렬되게 되며, '10' 은 '3' 보다 사전순으로 앞이기 때문에 '10' 이 먼저 출력되게 된 것입니다.

만약 sort()를 사전 순 외의 다른 기준 (예를 들면 문제에서는 사전 순이 아닌 정수의 오름차순이 기준이겠지요) 으로 정렬하고 싶으시다면, sort() 내부에 별도의 함수를 정의해 그 기준을 적어주시면 됩니다.

해당 내용에 대해 참고하시면 좋은 사이트의 링크와 문제를 해결하는 예제를 첨부해 드릴테니, 이해에 도움이 되셨으면 좋겠습니다!

https://developer.mozilla.org/...

// sort() 를 이용한 오름차순
complexes.sort((a, b) => a - b);

// sort() 를 이용한 내림차순
complexes.sort((a, b) => b - a);

sunyong0321 2년 전 1

확인하고 감사 댓글을 단 줄 알았는데 어쩌다보니 댓글 등록을 안했었나봅니다

감사 인사가 너무 늦었네요 ㅠㅠ

해결 되었고 친절한 답변 감사드립니다!!

댓글을 작성하려면 로그인해야 합니다.