99클럽 코테 스터디 1일차 TIL - 문제를 관통하는 키 찾기

뭐 하고 있는지: 99클럽

이게 뭔지: 항해99에서 운영하는 코테 스터디

어떻게 하는 건지: 매일 주어진 문제를 풀고, 월목은 게더타운에서 다같이 풀기 

계기: 개발자 오픈카톡방에 99클럽 홍보 메시지가 올라왔고, 재밌겠다 싶어서 신청했다. 가격도 무료였다.

기간: 3/25 ~ 4/25 매주 월,목 9pm~11pm

난이도: 상(챌린저) 등급 신청

 

오늘 배운 점

1. 예제에 대해 답을 구하는 과정을 단계별로 작성하며 규칙성을 찾아라.

2. 사이클은 어디에서나 시작해도 사이클 내의 모든 노드를 방문할 수 있다.

 

문제 1 - 마법의 엘리베이터 문제 링크

문제를 관통하는 키: 최우항 자리수부터 0으로 만들기, 예제에 대해 답을 구하는 과정을 단계별로 작성하며 규칙을 찾기 

임의의 숫자 n이 주어질 때, +-10^x 의 연산을 최소한으로 수행해서 0이 되는 경우를 구하는 문제다.

여기서 x는 0 이상의 정수값이다.

n은 음수가 되면 안된다. n보다 더 큰 값을 빼는 것은 금지이다.

"""
처음에는 dp 아니면 bfs 풀이를 생각했었는데 storey가 최대 1억이라서 bfs를 너무 많은 원소들이 돌 것 같다고 생각했습니다. 그래서 bfs를 버리고 예시숫자가 0이 되는 과정을 다시 살펴보았는데,
16->20->0
2554->2550->2600->3000->0
이런식으로 맨 오른쪽 자리수부터 0으로 바꾸면서 큰 자리수로 넘어가는걸 확인했습니다.
그런데 각 자리수가 0이 되는 방법은 커져서 0이 되거나 작아져서 0이 되거나 둘 중 하나이므로
두가지 경우 중 연산 횟수가 적은 쪽을 택해야 했습니다.

이걸 재귀함수로 구현했고, 제일 작은 자릿수가 0이 되면 10으로 나눈 몫을 가지고 다시 재귀호출해서 판단하러 가는 내용입니다.
재귀함수의 종료조건은 1만 남거나 0이 되는 경우에 종료합니다.
1이면 1만큼 빼줘야하기 때문에 cnts + 1을 리턴하고,
0이면 0이 됐기 때문에 바로 cnts를 리턴합니다.
"""

def solution(storey):
    def recur(val, cnts):
        if val == 1:
            return cnts + 1
        
        if val == 0:
            return cnts

        # 최우항 값 구함
        rightest = val % 10

        # 남은 수만큼 더하기
        c1 = recur((val + (10 - rightest)) // 10, cnts + (10 - rightest))

        # 남은 수만큼 빼기
        c2 = recur((val - rightest) // 10, cnts + rightest)

        if c1 < c2:
            return c1
        return c2

    return recur(storey, 0)

입력값이 최대 1억이라서 dp나 bfs로는 풀기 힘들어보였다.

풀이 시작한지 10분 정도까지 감이 잡히지 않아서 예시 숫자가 0이 되는 과정을 살펴보았다.

 

16->20->0

2554->2550->2600->3000->0

 

의외로 예시 숫자가 0으로 되는 순차적 과정을 살펴보니 규칙이 보였다.

가장 작은 단위의 숫자부터 0이 되도록 더하거나 빼면서 전체 숫자가 x*10^y꼴이 되도록 만든 후 다 빼버리면 되는 문제였다.

 

그리고, 가장 작은 단위 숫자는 더해져서 0이 되거나 빼져서 0이 되는 경우가 있으므로, 두 경우에 대한 결과값을 구한 후 더 작은 연산 횟수인 값을 리턴하면 되었다.

 

재귀함수에서 가장 중요한 부분은 종료조건을 잘 설정해주는 것이다.

해당 재귀함수는 recur(val, cnts)에서 val값은 결국엔 1이나 0이 될 것이다.

1인 경우엔 1을 빼줘야 하기 때문에 cnts + 1, 0인 경우엔 바로 cnts를 리턴하면 된다.

 

재귀로 푼 이유는 각 단위의 숫자를 더하는 경우와 빼는 경우 중 어느쪽이 더 적은 연산수를 사용하는 방향일지 몰라서였는데, 코테장님이 그리디하게 4 이하면 빼고 5 이상이면 더하면 된다고 해서 좀 어렵게 푼 느낌이 들었다.

 

문제 2 - 혼자 놀기의 달인 문제링크

문제를 관통하는 키: 사이클은 어디에서나 시작해도 사이클 내의 모든 노드를 방문할 수 있다는 것.

def solution(cards):
    vis = set()

    sizes = []
    for card in cards:
        if card in vis:
            continue
        vis.add(card)
        cnts = 1
        nxt = cards[card - 1]
        while nxt != card:
            vis.add(nxt)
            cnts += 1
            nxt = cards[nxt - 1]
        sizes.append(cnts)
    
    sizes.sort()
    if len(sizes) == 1:
        return 0
    return sizes[-1] * sizes[-2]

 

간단히 사이클을 구하면 풀리는 문제이다.

처음 시작했던 위치로 다시 돌아올 때까지 whlie을 돌면서 다음 노드로 탐색해나가며 cnts를 증가시키다가, 되돌아오면 cnts를 sizes에 넣어주면 된다. cnts는 사이클의 크기를 의미한다.

처음엔 2차원 graph를 만들고 cards for문 돌면서 deque로 인접노드 탐색하려고 했다. 그런데 인접노드가 무조건 한개이기도 해서 굳이 그럴 필요는 없겠다 싶어서 그냥 while문으로 풀어서 불필요한 graph 공간소비 없이 풀 수 있었다.

sizes를 다 구하고 sort를 수행하는데, 뭔가 더 최적화하는 방법이 있지 않을까 싶다.

 

오늘 배운 점

1. 예제에 대해 답을 구하는 과정을 단계별로 작성하며 규칙성을 찾기 

2. 사이클은 어디에서나 시작해도 사이클 내의 모든 노드를 방문할 수 있다는 것.