[Programmers] Level 3. 징검다리 건너기

2022. 11. 26. 22:09·코딩테스트/Python
728x90
반응형

🔗 Problem Link

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr


❔Thinking

  • 니니즈 친구들이 징검다리를 건널 수 있도록 한다.
  • 모든 디딤돌에는 숫자가 적혀있고(1<= stones <= 200,000,000) 밟을 때마다 1씩 줄어든다.
  • 0인 디딤돌은 건너뛰고, 가장 가까운 디딤돌로 건너뛴다. (최대 k칸을 건너 뛸 수 있다.)

💻Solution

def check(stones, mid, k):
    cnt = 0
    for s in stones:
        if s <= mid:
            cnt += 1
        else:
            cnt = 0
        if cnt == k:
            return False
    return True

def solution(stones, k):
    left, right = 1, max(stones)
    while left <= right:
        mid = (left+right) // 2
        if check(stones, mid, k):
            left = mid + 1
        else:
            right = mid - 1
    return left

🗝️keypoint

  1. 징검다리에 적힌 0의 개수가 k개 연속되면 반대편으로 건널 수 없다.
  2. 건널 수 있는 사람의 수는 징검다리의 값들 가운데 조건에 만족하는 값과 같은 의미를 가진다. 

'코딩테스트 > Python' 카테고리의 다른 글

[Programmers] Level 2. 수식 최대화  (0) 2022.11.29
[Programmers] Level 2. 방금 그 곡  (0) 2022.11.29
[Programmers] Level 3. 디스크 컨트롤러  (0) 2022.11.17
[Programmers] Level 2. 메뉴 리뉴얼  (0) 2022.11.15
[Programmers] Level 3. 보석 쇼핑  (0) 2022.11.13
'코딩테스트/Python' 카테고리의 다른 글
  • [Programmers] Level 2. 수식 최대화
  • [Programmers] Level 2. 방금 그 곡
  • [Programmers] Level 3. 디스크 컨트롤러
  • [Programmers] Level 2. 메뉴 리뉴얼
swwho
swwho
일상을 데이터화하다
  • swwho
    하루한장
    swwho
  • 전체
    오늘
    어제
    • 분류 전체보기 (188)
      • ML_DL (39)
        • MUJAKJUNG (무작정 시리즈) (18)
        • 딥러닝 공부하기 (21)
      • 데이터사이언스 (1)
        • EDA (1)
        • 데이터과학을 위한 통계 (0)
      • 데이터엔지니어링 (2)
      • 논문리뷰 (2)
        • Computer Vision (2)
      • Python 활용하기 (12)
      • 코딩테스트 (127)
        • Python (109)
        • MySQL (14)
      • Git (3)
      • MySQL 활용하기 (0)
      • 일상 이야기 (1)
  • 블로그 메뉴

    • 홈
    • 태그
  • 최근 글

  • 250x250
  • hELLO· Designed By정상우.v4.10.3
swwho
[Programmers] Level 3. 징검다리 건너기
상단으로

티스토리툴바