글 읽기 - 맞았습니다만, 혹시 시간 복잡도 봐주실 분 게신가요?

hse05105 2년 전 0

안녕하세요 고수님들 이제 코딩테스트 연습한지 2주 정도 된 코린이 입니다.

혹시 시간 복잡도를 봐주실 분 계신가 해서요..

저는 시간 초과가 날 것 같았는데 통과가 되어서 시간 복잡도를 어떻게 계산해야할지 감이 안오네요

1. input.shift().split(' ').map(v => +v) 는 메소드 체이닝이니까 병합적으로 동작해서 O(N)이라고 보면 될까요?

2. input.splice(0, K).map(elem => elem.split(' ').map(v => +v)) 은 중첩으로 splice와 map을 사용하였으니 O(N^2)로 보면 될까요?

dfs로 풀기도 했고 주어진 자료가 시간에 비해 턱없이 작아서 통과한 것 같아요. 이 코드의 총 시간 복잡도가 대충 어느정도 될까요..?

그 외에 이 코드에서 부족한 접 말씀해주시면 적극적으로 받아들이겠습니다. 고수님들의 피드백을 기다리겠습니다.

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
let T = +input.shift();
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

// dfs 함수 선언
function dfs(M, N, graph, v, visited) {
	for(let i = 0; i < 4; i++) {
	  let nx = v.x + dx[i];
      let ny = v.y + dy[i];
      if(nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
      if(visited[nx][ny] === false && graph[nx][ny] === 1) {
    	visited[nx][ny] = true;
        dfs(M, N, graph, {x: nx, y: ny}, visited);
      }
  }
}

function solution() {
  // 입력 받기
  let [M, N, K] = input.shift().split(' ').map(v => +v);
  let position = input.splice(0, K).map(elem => elem.split(' ').map(v => +v));
  // 2차원 배열로 그래프 구성
  let graph = Array.from({length: M}, () => Array.from({length: N}, () => 0));
  for(let i = 0; i < position.length; i++) {
  	graph[position[i][0]][position[i][1]] = 1;
  }
  // 방문 표시할 배열 선언
  let visited = Array.from({length: M}, ()=> Array.from({length: N}, () => false));
  // count 할 변수 선언
  let answer = 0;
  // 모든 칸에 대하여 dfs 호출
  for(let i = 0; i < M; i++) {
  	for(let j = 0; j < N; j++) {
    	if(visited[i][j] === false && graph[i][j] === 1) {
      	visited[i][j] = true;
        dfs(M, N, graph, {x: i, y: j}, visited);
        answer++;
      }
    }
  }
  // 출력
  console.log(answer);
}

// TestCase 만큼 solution 실행
for(let i = 0; i < T; i++) {
	solution();
}

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

문제

문제

출처

ICPC

맞았습니다만, 혹시 시간 복잡도 봐주실 분 게신가요?

hse05105 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말