프로그래머스 - 퍼즐 게임 챌린지

 

9월 21일에 실제 기업의 코딩 테스트를 치루고 아직 너무 부족하구나를 체감했다. 하루에 1문제 씩 푸는 현재의 공부량을 훨씬 늘려야겠다는 생각이 들었고 동시에 심란해져서 유튜브에 코딩 테스트를 공부하는 방법에 대해 검색하였다. 나동빈 님의 영상을 보게 되었고 영상을 보면서 알고리즘 별로 최소 50문제는 풀어보자 라는 다짐을 하게 되었다. 스스로에게 짜증이 났고 이거밖에 안되는구나 라는 생각이 들었지만 시간이 지나고 생각해보니 이까짓 거? 통과해본다 라는 객기가 생긴거 같다..ㅎㅎ 그래도 이것도 경험의 일종인 만큼 긍정적으로 생각하고 다시 달려볼려고 한다.

 

<참고한 영상>

https://www.youtube.com/watch?v=ukkLCl9yBvE

 

동시에 가끔 기업마다 자바스크립트로만 언어를 제한하거나 자바스크립트 언어는 없고 파이썬만 있는 경우도 있다. 그래서 두 가지 언어를 준비해야겠다 라는 생각이 들었고 22일 부터 한 문제에 대해 파이썬으로도 풀어보고 자바스크립트 로도 풀어보고 있다.(예시: 이번에 LG CNS의 코테 언어로 자바스크립트가 없고 파이썬이 있다)

 

<문제>

https://school.programmers.co.kr/learn/courses/30/lessons/340212

프로그래머스

 

 

<문제 핵심>

 

1. 이 문제는 이진 탐색을 이용하여 범위를 좁혀가며 풀어야되는 문제였다. 이진탐색으로 접근 안한다면 엄청나게 많은 연산 횟수가 필요하기 때문에 무조건 이진탐색을 사용해야 했던 문제

 

2. 문제에서 나와있듯이 난이도랑 숙련도의 비교를 통해 현재 퍼즐의 소요시간 만큼 더해주느냐, 틀렸다면 이전 퍼즐의 소요시간과 현재 퍼즐의 소요시간을 더한다음 틀린 횟수만큼 곱해주느냐를 결정한다. 또한 틀린 이후에는 현재 퍼즐의 시간만큼 더해주는거 까지 고려해야한다.

 

문제에서 나와있는 부분

 

자바스크립트 기반

 

파이썬 기반

 

 

<문제 풀이과정 및 순서도>

- 파이썬 

 

1. 퍼즐을 제한시간 안에 풀 수 있는지 없는지를 판단하는 puzzle 함수를 구현한다.

 

diffs: 난이도

level: 숙련도

def puzzle(diffs, times, limit, level) :
    clearTime = 0
    for idx in range(len(diffs)) :
        if diffs[idx] <= level : clearTime += times[idx]
        if diffs[idx] > level : clearTime += (diffs[idx]-level) * (times[idx-1] + times[idx]) + times[idx]
        if clearTime > limit : return False
    return True

  

 

2. solution함수에서 이진탐색을 적용한다.

 

제한시간 안에 문제를 풀 수 있다면 숙련도를 낮춰도 되는걸로 판단하고 end = mid - 1을 적용하고 풀 수 없다면 start = mid + 1을 통해 숙련도를 높인다.

def solution(diffs, times, limit):
    start, mid, end = 1, 0, max(diffs)
    
    while(start <= end) :
        mid = (start + end) // 2
        
        if puzzle(diffs, times, limit, mid) : end = mid - 1
        else : start = mid + 1
    
    if puzzle(diffs, times, limit, mid): return mid
    if puzzle(diffs, times, limit, mid+1): return mid+1
    return mid-1

 

<전체 코드>

- 파이썬

def puzzle(diffs, times, limit, level) :
    clearTime = 0
    for idx in range(len(diffs)) :
        if diffs[idx] <= level : clearTime += times[idx]
        if diffs[idx] > level : clearTime += (diffs[idx]-level) * (times[idx-1] + times[idx]) + times[idx]
        if clearTime > limit : return False
    return True
    
def solution(diffs, times, limit):
    start, mid, end = 1, 0, max(diffs)
    
    while(start <= end) :
        mid = (start + end) // 2
        
        if puzzle(diffs, times, limit, mid) : end = mid - 1
        else : start = mid + 1
    
    if puzzle(diffs, times, limit, mid): return mid
    if puzzle(diffs, times, limit, mid+1): return mid+1
    return mid-1

 

- 자바스크립트

자바스크립트 기반의 코드도 비슷한 맥락으로 풀이했다. 여기선 따로 puzzle 함수로 분리하진 않았다. 중요한 점은 over가 true라면 숙련도를 높여야 하므로 min = mid + 1을 적용하고 그 반대는 max = mid - 1을 적용한다.(min이 start를 의미하고 max가 end를 의미하는 것!! )

function solution(diffs, times, limit) {
  //문제 제한사항 보고 설정
  let max = 100000,
    min = 1,
    mid = 0;
  let answer = max;
  while (min <= max) {
    mid = Math.floor((max + min) / 2);
    let spendTime = 0,
      over = false;
    for (let i = 0; i < diffs.length; ++i) {
      if (mid - diffs[i] < 0) {
        spendTime += (diffs[i] - mid) * (times[i] + times[i - 1]) + times[i];
      } else {
        spendTime += times[i];
      }

      if (limit < spendTime) {
        over = true;
        break;
      }
    }

    if (over) {
      min = mid + 1;
    } else {
      answer = mid;
      max = mid - 1;
    }
  }
  return answer;
}