[HackerRank] 1Week + Day4 - Truck Tour

1. 문제

0부터 N-1개의 휘발유 pump가 있습니다.

각 pump에는

- 해당 pump에서 얻을 수 있는 휘발유의 양

- 다음 pump까지의 거리

 

위 2가지의 정보가 주어집니다.

특정 pump에서 시작해서 truck이 모든 pump를 방문하고자 합니다.

 

truck이 모든 pump를 전부 방문할 수 있는 시작점을 찾아 반환해주세요.

(* 1칸을 이동할 때 truck은 휘발유를 1 사용합니다.)

 

2. 풀이

어렵게 생각하지 않고 완전 탐색으로 풀 수 있는 문제였습니다. 🤗

 

첫 pump부터 시작하여, 해당 pump에서 시작하였을 때 모든 pump를 방문할 수 있는지

2중 for문을 사용하여 확인하고, 만약 모든 pump를 방문하였다면 해당 시작점을 반환해주면 됩니다!

 

이를 코드로 표현하면 아래와 같습니다.

size = len(petrolpumps)

# 탐색 시작점
for start in range(size):
	# 다음 pump부터 순차적으로 방문하여 해당 pump를 방문할 수 있는지 확인한다.
    for i in range(1, size-1):
    	# 해당 pump에서 다음 pump까지 이동하는데 필요한 휘발유까지 함께 계산해준다.
        if 휘발유가 부족한 경우:
        	break

🌹 pump들을 순차적으로 방문할 때, 마지막 pump는 계산하지 않는 점에 유의해주세요.
마지막 pump에 도착하면 끝이므로, 마지막 pump는 휘발유량 계산에 포함되지 않습니다.

 

해당 pump까지의 방문 가능 여부는 어떻게 판단할 수 있을까요?

현재 남아 있는 휘발유의 양에서 해당 pump에서 얻을 수 있는 휘발유량을 더해주고, 다음 pump까지 이동하는데 필요한 휘발유량을 빼주면 됩니다.

# 남은 휘발유량
petrol += petrolpumps[i][0] + petrolpumps[i][1]

 

전체적인 코드는 아래와 같습니다.

3. 코드

Python

size = len(petrolpumps)

# 탐색 시작점
for start in range(size):
	petrol = petrolpumps[start][0] - petrolpumps[start][1]
    if petrol < 0: continue
    
    able = True # 가능여부
	# 다음 pump부터 순차적으로 방문하여 해당 pump를 방문할 수 있는지 확인한다.
    for i in range(1, size-1):
    	# 해당 pump에서 다음 pump까지 이동하는데 필요한 휘발유까지 함께 계산해준다.
        petrol += petrolpumps[i][0] - petrolpumps[i][1]
        if petrol < 0:
        	able = False
        	break
            
    if able: return start
            
 return -1

 

4. Day 4 추가 문제

아래는 Day 4의 다른 문제들에 대한 간단한 풀이들입니다.

 

4.1 Grid Challenge

이번 문제는 어렵게 생각하지 않고, 일단 가로로 오름차순 정렬을 해준 후, 세로로 하나씩 탐색하며 오름차순으로 되어있는지 검사해주면 됩니다.

def gridChallenge(grid):
    # Write your code here
    temp = []
    for g in grid:
        temp.append(sorted(g))
    
    width, height= len(temp[0]), len(temp)
    for y in range(width):
        pre = temp[0][y]
        for x in range(1,height):
            if temp[x][y] < pre:
                return "NO"
            pre = temp[x][y]
    return "YES"

 

4.2 Recursive Digit Sum

k의 의미를 잘못 판단해 오래 걸렸던 문제였습니다. ( 역시 영어가 제일 큰 벽 😭 )

def getSuper(n):
    result = 0
    while n > 0:
        result += n%10
        n = n//10
    return result

def superDigit(n, k):
    n = getSuper(int(n)) * k
    # Write your code here
    while n // 10 != 0:
        n = getSuper(n)

    return n

 

여기서 처음에는

n = int(n * k)

요렇게 한 다음 풀었었는데, 문자열 계산이 들어가서 그런가 시간초과가 발생하였습니다. ㅠㅠ

그래서 좀 더 생각해보니, 굳이 n을 k번 반복한 후에 각 digit을 합하지 말고, n의 digt을 합한 수에 k를 곱해주어도 동일하다는 결론에 도달하여

n = getSuper(int(n)) * k

로 수정하였습니다.

 

4.3 New Year Chaos

🌹 이 문제는 혼자 풀다가 시간이 오래 지체되어 결국 다른 분의 풀이를 참고하였다는 점을 말씀드립니다. 😭

def minimumBribes(q):
    # Write your code here
    q = [x-1 for x in q]
    result = 0
    
    for i, o in enumerate(q):
        if o - i > 2: return "Too chaotic"
        for k in q[max(o-1,0):i]:
            if k>o: result+=1
            
    return result

 

해당 문제에서 가장 중요한 조건은

🛠 하나의 숫자를 3번 이상 움직일 수 없다!

입니다.

때문에 어떤 특정 숫자와 해당 숫자가 원래 있어야 하는 위치가 3 이상 차이나는 경우에는 "Too chaotic"을 반환해주면 됩니다.

if o-i > 2: return "Too chaotic"

그러지 않을 경우에는 자신 앞에 자신보다 큰 숫자만큼 뇌물(bribe)를 찔러주면 됩니다. 🤗

 

---

연습문제인데도 반해 꽤 난이도가 있는 Hackerrank입니다.

그래도 이제 UI에도 적응하여, 이전보다는 빠르게 문제를 풀고 있는듯 하네요.ㅋㅋ

 

감사합니다.🔥