Home 프로그래머스 알고리즘 문제 - 08
Post
X

프로그래머스 알고리즘 문제 - 08

게시 2023/12/03
By Psmin
15 m읽는 시간

Level 1

가장 가까운 같은 글자

문제 링크

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.

예를 들어, s=”banana”라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.

  • b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.

  • a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.

  • n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.

  • a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.

  • n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.

  • a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.

따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.

문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

풀이

문자열을 배열로 변환한 후 Map 메서드로 앞에서부터 순서대로 반복문을 돌린 후 반환된 배열을 return

Map 객체에 각 문자의 index 값을 저장합니다.

Map에 문자를 key로 값이 undefined이면 처음 나온 것이므로 -1을 return

undefined가 아니라면 현재 문자의 index값에서 Map 객체에 저장되어있던 값를 뺸 값을 return

또한, 매 반복마다 Map 객체를 갱신합니다.

1
2
3
4
5
6
7
8
9
10
11

function solution(s) {
  let map = new Map();

  return [...s].map((x, index) => {
    let idx = map.get(x) == undefined ? -1 : map.get(x);

    map.set(x, index);

    return idx == -1 ? idx : index - idx;
  });
}

두 개 뽑아서 더하기

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

풀이

재귀 함수를 활용한 조합을 활용하자. for문 중첩으로 완전 탐색도 가능하다.

종료 조건은 두 값을 뽑았을 때이므로 뽑은 값을 배열에 담아 길이가 2일 때로 설정, 더한 값을 answer Set 객체에 저장했습니다.

이후 answer를 배열로 변환한 후 sort() 해줍니다

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function solution(numbers) {
  var answer = new Set();

  function arraySum(arr, cur) {
    if (arr.length == 2) {
      answer.add(arr[0] + arr[1]);
      return;
    }

    for (let i = cur; i < numbers.length; i++) {
      arraySum([...arr, numbers[i]], i + 1);
    }
  }

  arraySum([], 0);

  return [...answer].sort((a, b) => a - b);
}

소수 찾기

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

function solution(n) {
  let answer = 0;

  function isPrime(n) {
    for (let i = 2; i <= Math.sqrt(n); i++) {
      if (n % i == 0) return false;
    }

    return true;
  }

  for (let i = 2; i < n; i++) {
    if (isPrime(n)) answer++;
  }

  return answer;
}

효율성 테스트 실패한 이유

  • isPrime 함수는 2 ~ n의 제곱근 까지의 수를 모두 탐색합니다.
    시간 초과
  • set 객체를 이용하거나 다른 방식으로 풀어야합니다.

다른 풀이 - 메모리제이션

  • 판별함수를 통과하면 cnt를 올리는게 아니라 해당 소수를 배열로 저장합니다.
  • 소수판별함수인 isPrime은 2 ~ n의 제곱근을 모두 탐색에서 저장된 소수들 중에 n의 제곱근보다 낮은 수 중 n의 약수가 있는 지 탐색합니다.

시간을 줄여 효율성 테스트를 통과할 수 있었습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

function solution(n) {
  var primes = [];

  function isPrime(n) {
    for (let x of primes) {
      if (x > Math.sqrt(n)) return true;
      if (n % x == 0) return false;
    }
  }

  for (let i = 2; i <= n; i++) {
    if (isPrime(i)) primes.push(i);
  }

  return primes.length;
}

실패율

문제 링크

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

실패율은 다음과 같이 정의한다. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

function solution(N, stages) {
  let map = new Map();

  // Map 객체 : 스테이지 번호, 각 스테이지에 있는 사용자 수
  stages.forEach((x, index) => {
    if (x <= N) map.set(x, map.get(x) + 1 || 1);
  });

  let n = stages.length;

  for (i = 1; i <= N; i++) {
    let cnt = map.get(i);

    if (cnt) {
      // 스테이지 번호, 실패율 로 변경
      map.set(i, cnt / n);
      n -= cnt;
    } else {
      // 배열에 없는 번호에 실패율 0 설정
      map.set(i, 0);
    }
  }

  return [...map]
    .sort((a, b) => {
      // 실패율이 같으면 번호 순, 다르면 실패율이 낮은 순서로
      return b[1] == a[1] ? a[0] - b[0] : b[1] - a[1];
    })
    .map(([x, _]) => x); // 스테이지 번호만 배열로 정렬
}

가독성이 좋지못한 코드가 되었다 다른 풀이를 살펴보자.

다른 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function solution(N, stages) {
  let result = [];
  for (let i = 1; i <= N; i++) {
    // i번 스테이지에 도달한 사용자 수
    let reach = stages.filter((x) => x >= i).length;

    // 현재 i번 스테이지에 머물러 있는 사용자 수
    let cur = stages.filter((x) => x === i).length;

    // 스테이지 번호와 실패율을 배열로 result 배열에 push
    result.push([i, cur / reach]);
  }

  // 실패율 순서로 정렬
  // for문에서 i를 1부터 순서대로 진행했으므로 번호 순 정렬 생략 가능
  result.sort((a, b) => b[1] - a[1]);

  return result.map((x) => x[0]);
}

[1차] 다트게임

문제 링크

0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.

“점수|보너스|[옵션]”으로 이루어진 문자열 3세트. 예) 1S2D*3T

점수는 0에서 10 사이의 정수이다. 보너스는 S, D, T 중 하나이다. 옵선은 *이나 # 중 하나이며, 없을 수도 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

function solution(dartResult) {
  var answer = [];

  // 입력반은 문자열을 3번의 라운드 별로 나누기
  let str = dartResult.match(new RegExp("\\d{1,2}[SDT]+[*#]?", "g"));

  // 각 라운드마다
  str.forEach((x, index) => {
    // 나눠진 문자열을 구조분해할당
    [score, bonus, option] = x.match(new RegExp("\\d{1,2}|[SDT]|[*#]", "g"));

    // 보너스 조건에 따른 점수 계산
    let n = bonus == "T" ? score ** 3 : bonus == "D" ? score ** 2 : +score;

    // 옵션에 따른 점수 계산
    if (option) {
      if (option == "*") {
        // 스타상
        n *= 2;
        if (index >= 1) answer[index - 1] *= 2;
      } else {
        // 아차상
        n *= -1;
      }
    }

    // 배열에 push
    answer.push(n);
  });

  // reduce로 합계
  return answer.reduce((acc, x) => acc + x, 0);
}

다른 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

function solution(dartResult) {
  // 객체로 점수의 변화를 미리 저장
  const bonus = { S: 1, D: 2, T: 3 },
    options = { "*": 2, "#": -1, undefined: 1 };

  // match 메서드로 라운드 분할
  let darts = dartResult.match(/\d.?\D/g);

  // 각 라운드별
  for (let i = 0; i < darts.length; i++) {
    // 라운드별 문자열 분할
    let split = darts[i].match(/(^\d{1,})(S|D|T)(\*|#)?/),
      // 점수 계산 한번에 하기
      score = Math.pow(split[1], bonus[split[2]]) * options[split[3]];

    // 스타상의 전 점수도 2배만 따로 구현
    if (split[3] === "*" && darts[i - 1]) darts[i - 1] *= options["*"];

    darts[i] = score;
  }

  return darts.reduce((a, b) => a + b);
}

대충 만든 자판

문제 링크

예를 들어, 1번 키에 “A”, “B”, “C” 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 “A”, 두 번 누르면 “B”, 세 번 누르면 “C”가 되는 식입니다.

1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과 입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.

단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

function solution(keymap, targets) {
  var answer = [];
  // Map 객체 사용
  let map = new Map();

  // 사용될 알파벳 문자의 최소 클릭 수를 Map에 알파벳 key값으로 저장
  for (let keys of keymap) {
    for (let i = 0; i < keys.length; i++) {
      if (!map.has(keys[i]) || map.get(keys[i]) > i + 1) {
        map.set(keys[i], i + 1);
      }
    }
  }

  // target들을 반복문으로 map의 key값으로 돌려 더합니다.
  targets.forEach((target) => {
    let cnt = 0;

    for (let word of target) {
      cnt += map.get(word);
    }

    // Map 객체에 없는 문자를 get 시도하면 undefined
    // clicks는 NaN가 된다.
    answer.push(cnt ? cnt : -1);
  });

  return answer;
}

로또의 최고 순위와 최저 순위

민우가 구매한 로또 번호를 담은 배열 lottos, 당첨 번호를 담은 배열 win_nums가 매개변수로 주어집니다.

이때, 당첨 가능한 최고 순위와 최저 순위를 차례대로 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function solution(lottos, win_nums) {
  let min = 7;
  let max = 7;

  lottos.forEach((x) => {
    if (x == 0) {
      max--;
    } else if (win_nums.includes(x)) {
      max--;
      min--;
    }
  });

  return [max > 5 ? (max = 6) : max, min > 5 ? (min = 6) : min];
}
  • 6등 조건을 따로 처리해주는 것은 조건이 복잡해질수록 구현하기 어렵습니다. rank 배열을 이용해보자.

다른 풀이

1
2
3
4
5
6
7
8
9
10
11

function solution(lottos, win_nums) {
  // min, max 변수가 아닌 rank 배열을 생성
  const rank = [6, 6, 5, 4, 3, 2, 1];

  let minCount = lottos.filter((v) => win_nums.includes(v)).length;
  let zeroCount = lottos.filter((v) => !v).length;

  const maxCount = minCount + zeroCount;

  return [rank[maxCount], rank[minCount]];
}
코딩테스트, Programmers
programmers
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.

Recent Update
Link