[선형] 4. 배열 문제(2)

01 Oct 2021 in 자료구조 on 선형

목차

1. Two Sum

배열과 정수 값이 주어질 때, 배열 내 두 값을 합하여 정수 값을 만들 수 있도록 두개의 Index를 반환하는 함수를 작성하시오.
각 입력에 정확히 하나의 솔루션이 있다고 가정하고, 동일한 요소를 두 번 사용하지 않는다.
배열의 index는 오름차순으로 정렬하여 반환하다.

function answer(nums, target) {
  // 구현
  let result = [];
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] == target) {
        result.push(i);
        result.push(j);
      }
    }
  }

  // 구현 종료
  return result;
}

let input = [
  // TC : 1
  [[2, 7, 11, 15], 9],
  // TC : 2
  [[3, 2, 4], 6],
  // TC :3
  [[3, 3], 6],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i][0], input[i][1]));
}

// 배열 바로 반환 가능 // O(n^2)
function answer(nums, target) {
  // 구현
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] == target) {
        return [i,j]
      }
    }
  }

  // 구현 종료
  return [];
}

function answer(nums, target) {
  // 구현
  // 시간복잡도 O(n)
  let map = {};

  🤔🤔
  // target = num[i] + num[j]
  for (let i = 0; i < nums.length; i++) {
    if (map[target - nums[i]] != undefined) {
      return [map[target - nums[i]], i];
    }
    map[nums[i]] = i;
  }

  // 구현 종료
  return [];
}

2. OX 퀴즈

대학교에서 OX 퀴즈 쇼를 진행한다.
정답을 맞췄을 경우 문제당 1점을 부여하며, 연속적으로 맞출 경우 연속한 정답 개수 만큼의 가산점을 부여해준다.
진행자를 위해 채점표를 보고 점수를 산추해주는 프로그램을 제작해주자.
배열 형태의 채점 값이 1(정답), 0(오답)으로 입력되며, 점수의 합계를 반환한다.

function answer(mark) {
  let result = 0;
  // 구현
  let seq_sum = 0;
  for (let i = 0; i < mark.length; i++) {
    if (mark[i] === 1) {
      seq_sum += 1;
      result += seq_sum;
    } else {
      seq_sum = 0;
    }
  }

  // 구현 종료
  return result;
}

let input = [
  // TC : 1
  [1, 0, 1, 1, 1, 0, 1, 1, 0, 0],
  // TC : 2
  [1, 1, 0, 1, 1, 0, 1, 1, 1, 1],
  // TC :3
  [1, 1, 1, 1, 1, 0, 0, 1, 1, 0],
];

for (let i = 0; i < input.length; i++) {
  console.log(`#${i + 1} ${answer(input[i])}`);
}

// #1 10
// #2 16
// #3 18

3. 벽돌 옮기기

새로운 알바생이 벽돌의 높이를 맞추지 않고 벽을 쌓아 놓았다.
관리자를 위해 몇 개의 벽돌을 옮겨야 벽돌의 높이가 같아질 수 있을지 구해주는 프로그램을 제작하시오.
입력은 배열 형태의 정수이며, 같은 높이를 맞추기 위해 옮겨야 하는 벽돌의 개수를 반환한다.
단, 입력으로 들어오는 배열은 남는 벽돌 없이 높이가 딱 나눠 떨어지도록 들어온다.

function answer(block) {
  let result = 0;
  // 구현
  let sum = 0;
  for (let i of block) {
    sum += i;
  }
  let height = sum / block.length;
  for (let key in block) {
    if (block[key] > height) {
      result += block[key] - height;
    }
  }

  // 구현 종료
  return result;
}

let input = [
  // TC : 1
  [5, 2, 4, 1, 7, 5],
  // TC : 2
  [12, 8, 10, 11, 9, 5, 8],
  // TC :3
  [27, 14, 19, 11, 26, 25, 23, 15],
];

for (let i = 0; i < input.length; i++) {
  console.log(`#${i + 1} ${answer(input[i])}`);
}

// #1 10
// #2 16
// #3 18

4. 숫자 빈도수 구하기

두 자연수 M, N을 입력 받아, M부터 N까지의 각 자리수의 빈도수를 합하는 프로그램을 제작하시오.
예를 들어 129와 137이 주어졌을 때, 129,130,131,132,133,134,135,136,137 숫자가 나오고,
이 숫자들의 자릿수 별 숫자 빈도수를 계산하여, 0부터 0까지의 빈도수 값을 반환한다.
입력 값은 M, N은 10000 이하의 자연수이며, 0부터 9꺼지의 자릿수 별 빈도수를 배열 형태로 반환한다.

// 자릿수 구하기 > 문자열로 뱌꾸기
// 10으로 나눠서 몫이 0보다 클때까지 반복하여 일의자리부터 구하기
function answer(s, e) {
  let result = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
  // 구현
  let str;
  for (let i = s; i <= e; i++) {
    str = i + "";
    for (let j = 0; j < str.length; j++) {
      //   console.log(str[j]);
      switch (str[j]) {
        case "0":
          result[0]++;
          break;
        case "1":
          result[1]++;
          break;
        case "2":
          result[2]++;
          break;
        case "3":
          result[3]++;
          break;
        case "4":
          result[4]++;
          break;
        case "5":
          result[5]++;
          break;
        case "6":
          result[6]++;
          break;
        case "7":
          result[7]++;
          break;
        case "8":
          result[8]++;
          break;
        case "9":
          result[9]++;
          break;
      }
    }
  }

  // 구현 종료
  return result;
}

let input = [
  // TC : 1
  [129, 137],
  // TC : 2
  [1412, 1918],
  // TC :3
  [4159, 9182],
];

for (let i = 0; i < input.length; i++) {
  console.log(`#${i + 1} > ${answer(input[i][0], input[i][1])}`);
}

// #1 10
// #2 16
// #3 18

switch 대신 result[str[j] / 1]++;

function answer(s, e) {
  let result = []
  // 구현
  for (let i = 0; i<10;i++){
      result[i] = 0
  }

  let num
  for (let i = s; i<e; i++){
    num = i
    while(num != 0){
        result[num % 10]++
        num /= 10
        num = parseInt(num)
    }
  }
  return result
}

5. 달팽이 만들기🤔

조카를 잠재우기 위해 달팽이 모양으로 숫자를 하나씩 적어주는 프로그램이 필요하게 되었다.
이를 위해 정사각형 모양의 달팽이 2차원 배열을 그려주는 함수를 작성하시오.
입력한 크기의 정사각형으로, 아래 그림처럼 시계방향으로 돌면서 숫자를 채워 2차원 배열을 반환한다.

function answer(length) {
  let result = [];
  // 구현

  // 1. 첫번 열만 1번씩
  // 2. 두번째부터 짝수개로 length-1
  // 3. 방향 변경

  // 1. result > 2차원 배열
  for (let i = 0; i < length; i++) {
    result[i] = [];
  }

  // 2. 반복문 패턴 구현
  // 1) length 길이만큼 시작해서 숫자를 채워준다.
  // 2) length-1, 방향, 2회
  // 3) length == 0, 프로그램이 멈춘다.
  let direction = 1;
  let x, y, num;
  x = y = num = 0;
  x--;
  while (1) {
    for (let i = 0; i < length; i++) {
      x += direction;
      result[y][x] = ++num;
    }

    length--;
    if (length == 0) break;

    for (let j = 0; j < length; j++) {
      y += direction;
      result[y][x] = ++num;
    }

    direction *= -1;
  }

  // 구현 종료
  return result;
}

let input = [
  // TC : 1
  3,
  // TC : 2
  5,
  // TC :3
  6,
];

for (let i = 0; i < input.length; i++) {
  console.log(`#${i + 1} > ${answer(input[i])}`);
}

와 이건 전혀 규칙성을 못찾겠어서 못풀었는데 풀이 대박이다… 감탄사밖에 안나온다…🤭🤭

2차원 배열 문제는 좌표 x, y 활용하기