Welcome to My IT World

코딩테스트 연습 - 마법의 엘리베이터

문제요약

절대값이 10^c 형태인 엘리베이터 버튼

버튼 누르면 현재 층수 + 버튼 값으로 이동

(단, 합이 0 보다 작으면 움직이지 않음)

0층 : 가장 아래층

현재 엘베층 : 민수가 있는 층

버튼 1번에 마법의 돌 1개 소모

어떤 층에서 0층으로 갈 때, 필요한 돌의 개수?

입력

1 ≤ 엘베 층수 storey ≤ 10^8

출력

return int

어떻게 풀까?

• +/- 양측으로 조정 가능

⇒ 각 자리수 별로 0에 가까운지 10에 가까운지 구분해서 10-n/n 값 중 작은 것을 카운팅해주면 될 것!

⇒ 1의 자리에서 가장 높은 단위까지로 반복문으로 수행(10^8이지만, 9자리이므로 충분)

• 이 때, 10에 가깝다면 윗 자리 값에 +1을 해주기

⇒ 아래 단위에서 버튼 한 번 누르나, 윗 단위에서 한 번 누르나 버튼 누른 횟수 카운팅은 동일

⇒ 가장 높은 자리의 경우, 별도 처리 필요(10에 가깝다면 10-n을 카운팅 해주고 그 값이 올림이 되었을 때를 고려하여 +1을 추가 카운팅해주기)

• 단, 0이나 10에 대하여 동일하게 가까운 5의 경우는 별도 고려 필요할 것!

⇒ 이 때에는 윗자리가 5이상인지 조건을 걸어, 5이상이면 올려주고 미만이면 내려주는 방식으로 처리 필요

내 코드

def solution(storey):
    storey_list = list(map(int, str(storey)))
    ans = 0

    for i in range(len(storey_list)-1, -1, -1):
        if 10 - storey_list[i] > storey_list[i]:
            ans += storey_list[i]
        elif storey_list[i] == 5:
            ans += 5
            if storey_list[i-1] >= 5:
                storey_list[i-1] += 1
        else:
            ans += 10 - storey_list[i]
            if i == 0:
                ans += 1
            else:
                storey_list[i-1] += 1
    return ans

코딩테스트 연습 - 할인 행사

문제요약

일정금액 지불 → 10일간 회원

회원 대상 매일 1가지 제품 할인

할인 제품은 하루에 하나씩만

정현이는 자신이 원하는 제품과 수량이 할인하는 날짜와 10일 연속으로 일치한 경우 회원가입 하려고 함

정현이가 가입 가능한 날짜의 총 일수 return

없으면 return 0

입력

1 ≤ want(원하는 제품 문자열 배열), number(원하는 수량 배열) ≤ 10

10 ≤ discount 배열 길이 ≤ 10^5

1 ≤ number의 원소 ≤ 10

number의 원소 합 = 10

출력

return int

불가능하면, return 0

어떻게 풀까?

discount 범위를 생각할 때, O(NlogN) 정도까지 가능

회원가입 일수가 10일 → 슬라이딩 윈도우?

⇒ 회원가입 일수가 10일일 뿐, 1일 안에도 정현이의 want가 모두 채워질 수 있음

⇒ 투포인터로 적용해서 discount for문 한 바퀴(10^5) 돌리면서 조정해주고 그 안에서 want 길이(10)만큼 돌면서 모두 충족되었는지 검사해도 시간복잡도 충분할듯

내 코드

def check_satisfied(want_num):
    for want in want_num.keys():
        if want_num[want] > 0:
            return False
    return True

def solution(want, number, discount):
    # 데이터 전처리(want, number-> dict)
    want_num = dict()
    for i in range(len(want)):
        want_num[want[i]] = number[i]
    # answer 초기화
    answer = 0
    # discount 돌면서 투포인터 적용
    start = 0
    end = 0
    # 초기화 처리
    if discount[start] in want and want_num[discount[start]] > 0:
        want_num[discount[start]] -= 1
    while end < len(discount):
        days = end - start + 1
        # 10일 초과 -> start += 1
        if days > 10:
            if discount[start] in want:
                want_num[discount[start]] += 1
            start += 1
        # 10일 전까지 -> 검사
        elif check_satisfied(want_num):
            answer += 1
            if discount[start] in want:
                want_num[discount[start]] += 1
            start += 1
        # 그 외의 경우
        else:
            end += 1
            if end == len(discount): break
            if discount[end] in want:
                want_num[discount[end]] -= 1
    return answer