Welcome to My IT World

코딩테스트 연습 - 미로 탈출 명령어

문제요약

n x m 격자 미로

(x, y) → (r, c)로 이동하여 탈출

• 격자 밖으로 나갈 수 없음
• (x, y) → (r, c) 이동거리는 총 k
• (x, y), (r, c) 포함하여 같은 격자 2번 이상 방문 가능
• 탈출경로를 문자열로 나타넀을 때, 사전 순으로 가장 빠른 경로 반환 (d : 아래 1칸, l: 왼쪽 1칸, r: 오른쪽 1칸, u: 위로 1칸)
• 미로탈출 경로를 반환하되, 탈출 못하면 ‘impossible’반환

입력

2 ≤ n ≤ 50

2 ≤ m ≤ 50

1 ≤ x ≤ n

1 ≤ y ≤ m

(x, y) ≠ (r, c)

1≤ k ≤ 5^2*10^2

출력

return str

어떻게 풀까?

• 시간복잡도 : 최대 50x50 크기의 격자이고 한 칸 당 최대 4방향으로 이동이 가능하며, k의 최대 값도 5^2*10^2인데다, 여러 경로가 나올 수 있고 그 중에서 사전 순으로 가장 빠른 경로를 반환해야함
  ⇒ 단순 BFS로 모든 경우를 산출한 뒤 그 중에서 사전 순으로 가장 빠른 답 반환하면 시간초과 발생
• 사전 순으로 가장 빠르다
  ⇒ 매번 결정마다 가장 빠른 경로를 큐의 가장 앞에 넣어서 최단경로를 도출 필요
  ⇒ 다익스트라 활용 가능
• 다익스트라를 활용하더라도, 이 문제의 경우 최단거리가 아닌 k 번 이내 방문에 대한 경로를 도출해내야하고 같은 격자를 여러번 방문할 수 있기 때문에, 이러한 조건들에 대해 별도 처리를 해줌으로써 최대한 시간복잡도를 다익스트라의 시간복잡도에 가깝도록 조치해줄 필요가 있음
  - 도착지점에 도착했을 때, 남은 이동가능 횟수가 2의 배수여야함(갔다 돌아오기 (예: d→u, l→r등))
  - 다음 지점을 탐색할 때, 해당 지점과 도착지점의 거리가 k보다 크면 어차피 탈출 불가능한 경로임(모두 거리가 1칸이기 때문에 지점 간 거리가 이동거리와 동일함)

내 코드

import heapq

def solution(n, m, x, y, r, c, k):
    q = []
    dr = ['d', 'l', 'r', 'u']
    dx = [1, 0, 0, -1]
    dy = [0, -1, 1, 0]

    heapq.heappush(q, ('', x, y))

    while q:
        path, x, y = heapq.heappop(q)
        if x == r and y == c:
            if len(path) == k:
                return path
            elif (k - len(path)) % 2:
                return 'impossible'
        for i in range(4):
            next_x = x + dx[i]
            next_y = y + dy[i]
            if next_x <= 0 or next_x > n or next_y <= 0 or next_y > m:
                continue
            if abs(next_x - r) + abs(next_y - c) + len(path) > k:
                continue
            heapq.heappush(q, (path+dr[i], next_x, next_y))
    return 'impossible'

코딩테스트 연습 - 부대복귀

문제요약

각 지역은 유일한 번호로 구분

두 지역간 통과 시 걸리는 시간은 모두 1

흩어진 부대원들이 최단시간 내에 부대가 있는 지역으로 복귀하고자 함

단, 경로가 없어져서 복귀 불가능한 대원이 있음

총 지역 수 n, 두 지역 왕복길 정보 roads, 각 부대원 위치 정보 sources, 지역 destination → sources 순서대로 복귀 가능한 최단 시간 배열을 구하고 복귀가 불가능하면 -1로 표기하라

입력

3≤ n ≤ 10^5

(각 지역 : 정수 1부터 n까지 번호로 구분)

2≤roads [[a,b], …] 2차원 배열 ≤ 5*10^5

([a,b] : a, b가 왕복가능)

1≤sources≤5*10^2

1≤destination≤n

출력

return int[]

어떻게 풀까?

• 다른 지역에 있는 부대원들이 모두 부대가 있는 한 지역으로 최단 시간 내에 가야함 ⇒ 거꾸로 생각해보면, 한 지점에서 모든 지점으로 가야함 ⇒ 다익스트라 문제 ⇒ 다익스트라의 시간복잡도는 O(nlogn)이므로 가능
• 다익스트라로 모든 지역에서 부대 복귀하는 최단distance 구한 뒤, sources를 돌아가면서 해당하는 distance 값을 answer 배열에 넣기 (단, 무한대(불가능)일 경우, -1 넣기)
• 지역번호는 1부터 n인 점 유의!

내 코드

import heapq

def solution(n, roads, sources, destination):
    answer = []

    INF = int(1e9)
    graph = [[] for _ in range(n + 1)]
    for road in roads:
        a, b = road
        graph[a].append(b)
        graph[b].append(a)
    distance = [INF]*(n+1)
    distance[destination] = 0
    q = []
    heapq.heappush(q, (0, destination))

    while q:
        dist, now = heapq.heappop(q)
        if dist > distance[now]:
            continue
        if not graph[now]:
            continue
        for next in graph[now]:
            cost = dist + 1
            if cost < distance[next]:
                distance[next] = cost
                heapq.heappush(q, (cost, next))

    for region in sources:
        if distance[region] == INF:
            answer.append(-1)
        else:
            answer.append(distance[region])

    return answer

코딩테스트 연습 - 유사 칸토어 비트열

문제요약

칸토어 집합이란, [0,1] 부터 시작해서 각 구간을 3등분 한 후에 가운데 구간을 반복적으로 제외하는 방식

다음과 같이 유사칸토어 비트열을 생성함

• 0 번째 유사칸토어 비트열 : 1
• n 번째 유사칸토어 비트열 : n-1 번째 비트열에서 1을 ‘11011’로 치환하고 0을 ‘00000’로 치환

n 번째 유사칸토어 비트열에서 특정 구간 내의 1의 개수가 몇개인지 return하라

입력

1≤ n ≤ 20

1≤ l, r ≤ 5^n

• l ≤ r < l + 10^7
• ㅣ과 r은 비트열에서 인덱스(1-base)이며, 폐구간 [l, r]을 나타냄

출력

return int

어떻게 풀까?

• 주의할 점 : l, r 이 1로 시작하는 인덱스이며 l과 r을 포함하는 구간으로 구해야 함
• 1≤ l, r ≤ 5^n 및 l ≤ r < l + 10^7 조건으로 인하여, 시간복잡도를 고려한 알고리즘 구현 필요
• 칸토어 집합 자체가 규칙이 있음 ⇒ 손으로 풀어보며 규칙을 찾아보자

⇒ 길이에 따라서 일정한 유사성을 가진 비트열이 생성되고 길이에 따라서 4의 배수로 1의 개수를 구할 수 있음

⇒ r-1번(index-0)까지의 1의 개수에서 l-2번(index-0)까지 1의 개수를 제외해주면 될 것

⇒ 이 때, 1의 개수는 해당 길이를 통해서 n번째 비트열에 속하는 지를 구한 후에 n-1번째 비트열의 길이로 그룹을 구하고 그 그룹의 개수만큼 4의 n-1승을 활용하여 구하면 됨

(단, 그룹의 수가 3개 이상일 때는 0이 5^(n-1)개 있는 그룹이 3번째 구간에 있으므로 그만큼을 제외해주어야함)

나머지의 경우, 재귀를 활용하여 처리

⇒ 현재, n을 5로 나누어주는 것으로 계속 진행을 하고 있기 때문에, 재귀의 종료조건은 n이 5이하가 될 때로 설정

(이 때는, '11011’[:길이]에서의 1의 개수를 반환하면 될 것)

내 코드

def get_power_of_base5(num):
	power = 1
	while 5**(power+1) < num:
	power += 1
	return power

def get_1_cnt(num):
	res = 0
	
	if num <= 5:
	    return '11011'[:num].count('1')
	
	power = get_power_of_base5(num)
	
	group = num // (5 ** power)
	
	res += group*(4** power)
	
	if group == 2:
	    return res
	elif group >= 3:
	    res -= 4 ** power
	
	remain = num % (5 ** power)
	if remain:
	    return res + get_1_cnt(remain)
	
	return res

def solution(n, l, r):
	return get_1_cnt(r) - get_1_cnt(l-1)

어려웠던 점

• 처음에 시간복잡도를 미처 고려하지 못한 탓에 아래와 같은 코드를 작성하였고 시간초과 오류가 발생하였다.

def solution(n, l, r):
    ans = 0

    r -=1
    l -=1

    memo = []
    memo.append('1')
    for i in range(1, n+1):
        memo.append(memo[i-1]*2+'0'*5**(i-1)+memo[i-1]*2)

    r_group = (r//5**(n-1))

    if r_group <= 2 :
        ans += r_group*(4**(n-1))
    else:
        ans += (r_group-1)*(4**(n-1))

    for i in range(r_group*(5**(n-1)), r+1):
        if memo[n][i] == '1':
            ans += 1

    l_group = ((l//5**(n-1)))
    if l_group <= 2:
        ans -= l_group*(4**(n-1))
    else:
        ans -= (l_group-1)*(4**(n-1))

    for i in range(l_group*(5**(n-1)), l):
        if memo[n][i] == '1':
            ans -= 1

    return ans

• 답을 찾는 데, n번째라는 인자값은 굳이 필요하지 않았다. 오히려 이 n번째 인자값을 어떻게 사용할지 고민하는 과정이 혼란을 주었던 것 같다. 주어지는 모든 인자들이 문제 해결에 필요하지 않을 수 있다는 점을 명심하자.
• 재귀함수를 사용할 때, num이 1이 되는 조건을 처음에 걸었었는데 함수 내부에서 num을 5로 나누어 진행을 하다보니 이 조건으로 인하여 무한재귀가 발생하였다. 인자값을 어떻게 처리하는 지 잘 확인하고 해당 처리를 거치지 못하는 값에 대해서 종료조건이나 예외처리를 해주어야할 것이다.
• 처음에 group 개수에 대한 1의 개수를 res에 반영함에 있어서 아래와 같이 처리하여 group이 1개이고 나머지가 있을 때를 제대로 처리하지 못했다.

def get_1_cnt(num):
...(중략)...

if group <= 2:
    return group*(4** power)
elif group >= 3:
    res -= 4 ** power
if remain:
        return res + get_1_cnt(remain)
return res

• 전체적으로 처리를 한 후에, 일부 예외사항을 반영하는 아래와 같은 방식으로 변경하였다.

def get_1_cnt(num):
...(중략)...

res += group*(4** power)

if group == 2:
    return res
elif group >= 3:
    res -= 4 ** power

if remain:
        return res + get_1_cnt(remain)
return res

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

문제요약

절대값이 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

코딩테스트 연습 - 두 큐 합 같게 만들기

문제요약

길이가 동일한 큐 2개가 주어짐

하나의 큐에서 추출해서 다른 큐에 삽입함 : FIFO 방식으로 진행

추출+삽입 = 1회

두 큐의 합이 같아질 수 있는 최소 횟수 return

만일, 불가능하면 -1 return

입력

1≤ 각 q의 길이 ≤ 3*10^5

1≤ q의 원소 ≤ 10^9

출력

return int

불가능하면, return -1

어떻게 풀까?

1. 일단, 입력 값의 범위를 봤을 때, O(n^2)는 불가능하고 O(nlogn) 정도까지는 가능
2. 제일 먼저 예외처리를 할 수 있는 건, 두 큐의 합이 짝수가 아닐 때! 큐의 합을 모두 더해서 짝수가 아니면 바로 return -1을 해주자!
3. 가장 간단하게 푸는 방법?
   while 문 돌리면서 각 큐의 합을 비교하고 큰 큐에서 값을 빼서 작은 큐에 넣어주는 것 반복 어차피 FIFO 방식이기 때문에, 결국 돌고 돌면서 크고 작음이 조율될 것!
   이때 문제는, 이게 얼마나 돌아야 return -1 판별이 가능한지임 사실 두 q 길이의 합 만큼 돌리면 원상복귀이기 때문에 더 이상 돌 필요가 없음! => 두 q 길이의 합은 2*3*10^5 로 충분히 가능!
4. 이 때, 주의할 점은 deque로 만들어주고 해야한다는 점! 배열에서 바로 pop(0)을 해주면, O(N)이 걸리기 때문(배열에서 앞에걸 빼면 뒤에 원소들도 다 자리이동을 시키기 때문에)에 시간초과가 남 ⇒ deque popleft() 이용 : O(1)

내 코드

다르게 푸는 방법?

투포인터 활용하기!

def solution(queue1, queue2):
    target = (sum(queue1) + sum(queue2)) // 2
    cur = sum(queue1)
    queue3 = queue1 + queue2 + queue1

    s = 0
    e = len(queue1) - 1
    answer = 0
    while True:
        if cur == target:
            return answer
        if cur < target:
            e += 1
            if e >= len(queue3):
                return -1
            cur += queue3[e]
        else:
            cur -= queue3[s]
            s += 1
        answer += 1

" 위 풀이코드 출처 : algorithm-ps/두 큐 합 같게 만들기.md at main · dali0202/algorithm-ps "  

위 코드에서 유심히 볼 점!

단순히 q1+q2로 합치지 않고 q1+q2+q1를 해준 점

아래와 같은 경우가 있을 수 있음