11월 2주차 코딩 테스트 Study

1. Billboard

문제 설명

n개의 문자를 보여주는 크기가 n인 전광판이 있습니다. 전광판의 문자는 오른쪽에서 왼쪽으로 반복해서 흘러가며, 1초에 한 글자씩 흘러갑니다.

예를 들어, 크기가 5인 전광판에 "Snowball" 노출한다고 가정할 때, 시간 t의 변화에 따른 노출 예시는 다음과 같습니다.

t : 0초 전광판 : .....

t : 1초 전광판 : ....S

t : 5초 전광판 : Snowb

t : 10초 전광판 : all..

t : 15초 전광판 : ...Sn

전광판의 크기 n과 전광판에 노출할 문자 s그리고 시간 t가 주어질 때, t초 후의 전광판에 표시될 문구를 출력하는 함수, solution을 완성해주세요.

제한 사항

전광판의 문자는 1초부터 흐르기 시작합니다.

입력 형식

n은 1 이상 50 이하의 정수입니다.
s는 길이가 1 이상 100 이하의 문자열입니다.
s는 알파벳 대/소문자와 숫자로 구성됩니다.
t는 1 이상 1000 이하의 정수입니다.

출력 형식

t 초 후, 주어진 전광판에 노출되는 문자를 출력합니다.
전광판의 공백은 마침표(".")로 대체하여 출력합니다.

풀이

n = 5이고 s = ‘Snowball’ 이면 전체 프로세스에 대한 전광판 상태는 아래와 같다.

시간 t	전광판 상태	설명
0	.....	초기 상태
1	....S	'S' 등장
2	...Sn	'n' 추가
3	..Sno	'o' 추가
4	.Snow	'w' 추가
5	Snowb	'b' 추가
6	nowba	'a' 추가
7	owbal	'l' 추가
8	wball	'l' 추가
9	ball.	메시지가 왼쪽으로 이동, 점 등장
10	all..	점이 하나 더 추가
11	ll...	점이 하나 더 추가
12	l....	점이 하나 더 추가

전광판은 0번 부터 12번까지를 반복한다(11 .. 12가 되면 다시 0번 .. 1번 .. 2번). 즉 한 사이클은 13초가 걸린다.

그럼 이걸 어떻게 계산할 수 있을까?

(A) 초기 상태의 전광판은 빈 상태(n개의 점)에서 메시지의 첫 글자가 전광판 가장 왼쪽에 도달하는데 까지 걸리는 시간은 n초가 걸린다. (표에서는 0 ~ 5까지 = 5초)

(B) 이후 메시지의 맨 마지막 글자가 전광판의 가장 왼쪽에 오는데까지 걸리는 시간은 글자 수 - 1가 된다. (표에서는 (표에서는 6 ~ 12까지 = 7초)

따라서 최종적으로 한 사이클에는 13초(5초 + 7초 + 1초)가 걸리게 된다.

(B)가 걸리는 시간을 좀 더 자세히 살펴보면

전광판 첫 번째 위치를 가르키는 포인터(화살표)가 있다고 가정해보자. 그럼 5초후에는 문자열의 0번째를 가르키고 있을 것이다.

그 화살표가 메시지 끝을 가르킬 때는 문자열의 마지막 인덱스, 7번 인덱스를 가르키고 있을 것이다.

(0→ 1번 인덱스로 가는데 1초, 1 → 2번 인덱스로 가는데 1 + 1초 … 6 → 7번 인덱스로 가는데 7초)

따라서 0번 인덱스에서 7번인덱스 까지는 7초가 소요된다.

마지막으로 아무것도 없는 상태의 시간 1초를 추가하면 하나의 사이클은 총 8초이다.(표에서는 1번부터 13번)

전광판은 표에서 0부터 12번을 계속반복한다. 코드는 아래 처럼 표현할 수 있다.

repeat_duration = n + len(s) # 5 + 7 + 1 = 13

총 문자는 아래처럼 구성할 수 있다.

저렇게 구성하는 이유는 t를 repeat_duration으로 나눈 나머지는 13을 주기로 돌게된다.

0초일때는 0번부터 5번까지,
1초일때는 1번부터 6번까지..
12초일때는 16번까지..
13초가 되면 다시 0초부터 5번까지..

즉 t = 12일 때 l.... 가 구성되어야 하고 13 일때 다시 처음으로 돌아와 ..... 를 구성해야 한다.

optimize_time = t % repeat_duration # 0 ~ 12 반복

text = ('.' * n) + s + ('.' * (n - 1)) # .....Snowball....

따라서 최종코드는 아래와 같다.

def solution(n, s, t):
    repeat_duration = n + len(s)

    optimize_time = t % repeat_duration

    text = ('.' * n) + s + ('.' * (n - 1))
    return text[optimize_time:optimize_time + n]

TestCase

n = 20
s = 'Apple'
t = 9
# result: '..A'

n = 7
s = '0123456789'
t = 77
# result: '2345678'

n = 20
s = 'AlGoRiThM0123’
t = 249
# result: '..AlGoRiThM0123.....'

n = 5
s = 'Snowball’
t = 9
# result: 'ball'
print(solution(5, "Snowball", 9))

2. Take the sand (Nim 게임)

문제 설명

여름을 맞아 가족들과 함께 해수욕장을 방문했습니다. 코로나로 인해서 많은 사람이 각자의 파라솔 아래에서 마스크를 쓰고 둘러앉아 모래 뺏기 게임을 하고 있습니다. 흥민이와 흥민이의 누나는 numkg의 모래를 쌓아두고 게임을 시작합니다. 모래성 중앙의 깃발이 쓰러지지 않도록 하는 모래성의 무게는 1kg입니다. 흥민, 누나의 순서대로 게임이 진행됩니다. 한사람이 한 번에 가져갈 수 있는 모래의 양은 최소 1kg, 최대 3kg입니다. 여기에서 모래의 양 num을 입력하여 흥민이가 이길 수 있는 경우를 true, false로 출력하는 함수를 작성해 보세요.

제한 사항

최소 1kg, 최대 3kg의 모래를 가져갈 수 있습니다.
흥민, 누나의 순서대로 게임이 진행됩니다.
모래성은 1kg미만으로 남게 되면 쓰러집니다.
즉, 1kg이 자기 차례에 남으면 승리합니다.

입력 형식

num은 1 이상 100,000 이하의 정수입니다.

출력 형식

흥민이가 이길 수 있는 경우를 true, false로 출력합니다.

풀이

이 문제는 Nim게임과 비슷하다. 그리고 단 둘이 할 경우 필승전략이 있으며 먼저 시작하는 것이 매우 유리하다.

핵심 전략은

처음 주어진 숫자를 4N + 1로 만드는 것
상대방이 제시하는 숫자와 내가 제시하는 숫자를 4N씩 맞춰가는 것

예를 들어 40이라는 숫자가 있다. 이는 4로 나누었을 때 나머지가 0이다.

40 % 4 = 0

핵심전략 1번을 통해 40 이라는 숫자를 4로 나누었을 때 1이 되게끔 만들려면 나는 37을 만들면 된다.

즉, 40개에서 3개를 가져가면 37이된다(4*9 + 1).

그 후에 상대방이 1개를 가져가면 나는 3개를 가져가고

상대방이 2개를 가져가면 2개를 가져가고

1개를 가져가면 3개를 가져간다.

이렇게하면 4N개씩 숫자가 사라지고 최종적으로 상대방이 1이 남게되어 무조건 내가 이기게 된다.

37에서 4개씩 사라져 게임이 끝나기 전에 5개(37 - 4*8)가 남게될 것이고 상대방 차례가 된다.

상대방이 1을 가져간 경우 → 4개가 남음 → 내가 3개를 가져가서 승리
상대방이 2를 가져간 경우 → 3개가 남음 → 내가 2개를 가져가서 승리
상대방이 3을 가져간 경우 → 2개가 남음 → 내가 1개를 가져가서 승리

무조건 승리하게 된다.

그러나, 내가 먼저 시작했을 때, 처음 4N + 1을 만들지 못하면 상대방 턴에서 4N + 1을 만들기 내가 지게된다.

4N + 1을 만들지 못하는 경우는 4N + 1인 숫자인 경우이다.

예를들어 처음 숫자가 37이라 해보자. 최소 1개는 가져가야 하는 상황에서 최대 3개까지 사용해도 나머지 1이 남지않는다.

1. 37 - 1 = 36 = 4*9 + 0
2. 37 - 2 = 35 = 4*8 + 3
3. 37 - 3 = 34 = 4*8 + 2

1번을 선택해서 만들면 상대방이 36에서 33(4*8 + 1) 을 만들어버릴 것이고 4의 배수로 숫자를 가져가게 되어 내가 지게 된다.
2번을 선택하면 상대방이 35에서 33로 ..
3번을 선택하면 상대방이 34에서 33으로 ..

즉, 처음 부여된 숫자가 4N + 1로 시작하는 숫자가 아니라면 나는 4N + 1의 숫자를 만들 수 있어 내가 이기게 된다!

따라서 정답은 아래 코드가 된다.

def solution(nums):
		return nums % 4 != 1

Test Case

n = 4
# result: False

n = 3
# result: True

n = 40
# Result: False

n = 200
# result: False

n = 310
# Result: True

n = 100
# result: False

이 게임은 두 명이서 베스킨라빈스를 31게임을 두명이서 진행할 때도 적용할 수 있다.

베스킨 라빈스는 반대로 1부터 시작해 31까지 1개 ~ 3개 이하의 숫자를 부르며 순차적으로 진행하다 맨 마지막에 31을 외치는 사람이 지는 게임이다.

이 경우는 숫자를 갯수로 생각하면 된다. 31개의 숫자가 있고, 내가먼저 시작해 4N+1개를 상대방한테 준 후에 4N개씩 맞추며 왔다 갔다 하면 된다.

4 * 7 + 3 = 31
4 * 7 + 2 = 30
4 * 7 + 1 = 29

즉 29개의 숫자를 만들어 주면 됨으로 31개중에서 2개를 뺀 29개의 숫자를 상대방한테 건네주고 시작하면 됨으로 1, 2를 외치며 시작하면 29개의 숫자만 남게된다.

나    상대
1,2   3, 4, 5
6     7, 8, 9
10    11, 12, 13
14    15, 16, 17
18    19, 20, 21
22    23, 24, 25
26    27, 28, 29
30    31(패배)

29개만 만들어 주면 됨으로 32(4*N)도 1, 2, 3으로 시작해 29개를 만들 수 있다.

나       상대
1,2,3   4, 5, 6
7       8, 9, 10
11      12, 13, 14
15      16, 17, 18
19      20, 21, 22
23      24, 25, 26
27      28, 29, 30
31      32(패배)

29개만 만들어 주면 됨으로 30(4*N + 2)도 1로 시작해 29개를 만들 수 있다.

단, 33(4N + 1)인 경우는 최대 3을 빼도 30임으로 4N + 1을 만들 수 없어 이 경우는 필승 전략이 없다.

따라서 4N으로 나누었을때 나머지가 1이면 필승전략이 없는 것이다.

3. Greatest Common divisor

문제 설명

배열 A에는 0보다 큰 숫자가 N개 들어있습니다. 모든 숫자를 아우르는 최대 공약수를 구하는 함수를 작성하세요.

입력 형식

0보다 큰 정수가 들어있는 배열 A

입력타입: int[] A

출력 형식

배열 A의 모든 정수를 아우르는 최대 공약수 출력타입: int

풀이

이 문제는 유클리드 호제법을 사용하면 빠르게 풀 수 있다.

유클리드 호제법은 아래 처럼 몫과 나머지가 계속해서 작은 수로 쪼개어지다가 B자리가 0이될 때 A위치가 A와, B의 최대공약수가 된다.

gcd(A,\;B) \;\;\; (A > B, A \neq B)\\ A = Q_1*B +R_1 \\ gcd(A,\;B) = gcd(B,\;R_1) \\ B = Q_2*R_1 + R_2 \\ gcd(A,\;B) =gcd(B, R_1)=gcd(R_1,\;R_2)= ... = gcd(R_n,\;0)

(A > B) 라는 조건이 있으나 사실상.. 3과 4의 최대공약수나 4, 3의 최대공약수나.. 결과는 같기 때문에 A와 B의 순서를 바꿔도 문제가 없다.

그런데 (A > B)라하는 이유는 아래 예시를 보자 한번 로테이션이 일어나기 때문에 … 결국 똑같다..

그렇다면 다수의 최대공약수는 어떻게 될까? 아래와 같이 4개의 숫자로된 배열이 있을 때 아래와 같다

[A,\;B,\;C]\\ gcd(gcd(A,\;B,\;C),\;D)\\ gcd(A,\;B,\;C) = gcd(gcd(A,\;B),\;C)

즉 먼저 두 개의 숫자를 계산하고 그 결과값을 이후 다음 숫자와의 최대공약수를 계산해나가면 된다.

이때 가장 큰 두 값을 먼저 계산해주는 이유는 위 처럼 로테이션되는 부분 줄이기 위한 최적화 하기 위함이라 보면 된다.

def GCD(a, b): # (a > b)
	if b == 0:
		return a
	else:
		return GCD(b, a%b)

def solution(A)
	A.sort()[::-1]
	
	retv = GCD(A[0], A[1])
	for i in range(2, len(A)):
		retv = GCD(retv, A[i])
	
	return retv

Testcase

[2, 12, 15, 18]
# result = 2

4. 중복문자 제거

문제 설명

문자열에 연속한 2개의 같은 문자가 존재하지 않도록 만들고 싶습니다.

연속한 2개의 같은 문자가 존재한다면 이 문자를 지우고 남은 문자열을 이어 붙입니다.

이 과정을 연속한 2개의 같은 문자가 없을 때까지 반복하면 목표한 문자열을 얻게 됩니다.

문자열 s가 주어질 때, 위와 같은 과정을 적용해서 나오는 문자열을 출력하는 함수, solution을 완성해주세요.

입력 형식

s는 길이가 1 이상 100,000 이하의 문자열입니다.
s는 알파벳 소문자로만 이루어져 있습니다.

출력 형식

중복을 제거한 문자열을 출력합니다.

이 문제는 스택을 사용하면 매우 쉽게 풀 수 있다.

문자를 하나씩 추가해 나가는데 가장 최근에 추가한 문자와 새로 추가할 문자와 같으면 가장 최근에 추가한 문자를 제거하는 방식이다.

코드는 아래와 같다.

def solution(s):
		stack = []
		for char in s:
				if len(stack) > 0 and stack[-1] == char:
					stack.pop()
				else:
					stack.append(char)
		
		return ''.join(stack)

Test Case

s = 'aacddefg'
# Result: 'cefg'

s = 'abba'
# Result: ''

s = 'a'
# Result: 'a'

s = 'accaaaaaaabccbbbcabc'
# Result: 'cabc'

s = 'aaaegdaeccdffahddgadbhghddgcbdabcdggcgaefedeccfcfd'
# Result: 'aegdaedahgadbhghgcbdabcdcgaefedefcfd'

5. Repeat Alphabet

문제 설명

S는 알파벳으로 이루어진 문자열 입니다.

해당 문자열에서 2회 이상 연속해서 나오는 알파벳을 소거 합니다.

소거한뒤에 나온 문자열에서 다시 연속해서 나오는 알파벳을 소거하는 작업을 더 이상 작업할 것이 없을 때 까지 반복합니다.

이때 최종 문자열이 완전히 소거되어 빈 문자열이라면 1을 리턴하고 알파벳이 남아있으면 0을 리턴하는 함수를 작성하세요.

입력 형식

문자열 S

타입: string

출력 형식

조건 수행후 문자열이 비어있다면 1, 남아있다면 0

타입 : int

이 문제는 중복문자 제거와 동일한 문제로 마지막 출력부만 수정하면 된다.

def solution1(s):
    stack = []
    for c in s:
        if len(stack) > 0 and stack[-1] == c:
            stack.pop()
        else:
            stack.append(c)


    return 0 if ''.join(stack) else 1

6. WordPatternGame

문제 설명

상현이와 성민이는 낱말 게임을 하고 있습니다. 패턴을 주면 이 패턴대로 한 사람씩 돌아가면서 낱말을 말하는 게임입니다.

예를 들어, 주어진 패턴 p가 "가나나가" 이고, 낱말 s가 "드래곤 바나나 바나나 드래곤" 라고 가정할 때 게임의 경과는 무승부로 true를 출력합니다.

한 사람이 첫 번째 패턴인 "가" 시점에 특정 낱말을 말합니다. ex: "드래곤" 그다음 사람은 "가" 패턴에 말한 낱말을 제외하고, 두 번째 패턴인 "나" 시점에 맞는 임의의 낱말을 말합니다. ex: "바나나" 그다음 사람은 세 번째 패턴인 "나" 시점에 맞는 낱말을 말합니다. ex: "바나나" 마지막으로 네 번째 패턴인 "가" 시점에 맞는 낱말을 말합니다. ex: "드래곤"

패턴 p와 언급한 낱말들 s가 주어질 때, 해당 게임이 무승부로 끝났는지를 출력하는 함수, solution을 완성해주세요.

제한 사항

각 낱말은 공백이 없는 연속된 문자열입니다.
s의 각 낱말은 스페이스(" ")로 구분됩니다.

입력 형식

p는 길이가 4인 문자열입니다.
s는 길이가 1 이상 1,000 이하의 문자열입니다.

출력 형식

게임의 결과가 승리이면 True, 패배이면 False

def solution(p, s): # p = '가나다라' s = '바나나 사과 딸기 오렌지'
		maps = {}
		words = s.split()
		
		if len(p) != len(words):
				return False
				
		if len(set(p)) != len(set(words)):
				return False
		
		for i in range(len(p)):
				if p[i] in maps and maps[p[i]] != words[i]:
						return False
				
				maps[p[i]] = words[i]
		
		return True

7. JumpCase

문제 설명

당신은 수직선 위의 0지점에 서있습니다.

그리고 당신은 같은 수직선 위의 n미터 떨어진 목적지로 가려고 합니다.

당신은 한번에 수직선 위를 k 이하의 정수 거리만큼 이동할 수 있으며, 처음 이동한 방향으로만 계속 이동할 수 있습니다.

그리고 직전에 이동한 거리와 같은 거리만큼 다시 이동할 수는 없습니다.

예를 들어, 3-2-3 순서대로 이동했다면 다음에 3만큼 이동할 수 없습니다.

수직선 길이 n과 이동 가능한 최대 거리 k가 주어질 때, 목적지에 도착 가능한 방법의 경우의 수를 출력하는 프로그램을 구현하세요.

결과 값이 매우 클 수 있으니, 1,000,000,007로 나눈 나머지 값을 구해주세요.

입력 형식

n: 목적지까지의 거리 정수 값
k: 한 번에 이동할 수 있는 최대 거리 정수 값

출력 형식

목적지로 도착 가능한 경로의 경우의 수를 1,000,000,007로 나눈 나머지를 정수로 반환

제약 사항

1 ≤ n ≤ 1000
1 ≤ k ≤ 100

입출력 예시

입력:
- n = 5
- k = 3
출력: 4
설명: 아래와 같이 총 4개의 방법이 있다.
- 3 + 2
- 2 + 3
- 1 + 3 + 1
- 2 + 1 + 2

풀이

이 문제를 재귀함수로 시도했으나 테스트 케이스 중에서

n = 1000, k = 100인 경우가 있는 경우 10초내로 풀이되지 않는다. 따라서 DP테이블을 만들어서 메모지에이션(Memoziation)형태로 풀어나가야 빠른 속도로 풀 수 있다.

dp 테이블은 0행 0열 상태에서 기저사례를 추가하기 위해 n+1개, 열이 k+1개로 구성되어야 한다.

*기저사례: 쪼개지지 않는 가장 작은 작업

dp = [[0]*(k+1) for _ in range(n+1)]

문제의 조건에서 연속되는 숫자가 올 수 없음으로 각 행은 합을 만족해야 하는 숫자 이며 각 열은 합을 만족하는 요소중 마지막 숫자로 구성해야 한다.

for i in range(1, n+1):

합이 되는 숫자는 i보다 마지막 숫자는 클 수 없다. (합이 4가 되야 하는데 마지막 숫자가 5일수 없는 것 처럼)

또한 최대 k개 숫자까지만 사용가능하다

만약 합을만족해야하는 숫자 i가 2인데, k가 3이라 할지라도 마지막 숫자 j는 2를 넘어설 수 없다.

그러다가 i가 k보다 커지는 순간이 오는데, 이때 마지막 숫자는 k가 최대값이 되야한다. 이렇게 동작하기 위해 아래처럼 구성한다.

for j in range(min(k+1, i+1))

이렇게 이중 반복문이 구성되었고 마지막으로 숫자 j까지 반복하면된다.

예를들어 합이 i(3)이고 마지막 숫자가 j(1)이 가능한 경우는 합이 2(i-j)이고 마지막 숫자가 1이 아니면 된다.

즉, dp[3][1] = dp[2][0] + ~~dp[2][1]~~ + dp[2][2] + dp[2][3]

dp[2][0]: 합이 2이고 마지막 숫자가 0이 되는 경우의 수는 [2, 0] 이 존재하나 k>0임으로 고려대상이 아니다. 따라서 존재하지 않아야 함으로 0개
dp[2][2]: 합이 2이고 마지막 숫자가 2가 되는 경우의 수는 [2] 가 존재하여 1가지다
- 그럼 [2]에 1을 추가하면 [2, 1] 이 되어 합이 3이고 마지막 숫자가 1인 경우가 만족함으로 이 경우에 대해서 더해준다.
dp[2][3]: 합이 2이고 마지막 숫자가 3이되는 경우의 수는 존재하지 않음으로 0이다.

따라서 dp[3][1]은 최종적으로 1이된다.

이렇게 동작하기 위해 아래처럼 구성해보자

for z in range(0, k+1):
		if z != j:
				dp[i][j] += dp[i-j][z]
				dp[i][j] %= 1_000_000,007

기저 조건과 3가지 반복문을 중첩시키면 아래처럼된다. 마지막행을 전부 더해주면 정답이 된다.

최종 코드는 아래와 같다.

def solution(n, k):
		MOD = 1_000_000_007
		dp = [[0]*(k+1) for _ in range(n+1)]
		dp[0][0] = 1 # 합이 0이고 마지막 숫자가 0인 경우는 [0]
		
		for i in range(1, n + 1):
				for j in range(min(k + 1, i + 1)):
						for z in range(k + 1):
								if z != j:
										dp[i][j] += dp[i - j][z]
										dp[i][j] %= MOD
										
		result = 0
		for i in range(k + 1):
				result += dp[n][i]
				result %= MOD
				
		return result

이해를 돕기위해 n = 5, k = 3일 때 예시를 들어 진행해보자. 최종적으로 dp 테이블은 아래와 같다.

i \ j	0	1	2	3
0	1	0	0	0
1	0	1	0	0
2	0	0	1	0
3	0	1	1	1
4	0	2	0	1
5	0	1	2	1

기저 조건 dp[0][0] = 1 잊지말자.

처음에는 구성되는 숫자가 0보다 커야한다.

n = 1, k = 1 : 합이 1이고 마지막 숫자가 1이 될 수 있는 경우 → [1] 1가지
- 합이 0이고 마지막 숫자가 1이 아닌 경우
- dp[1][1] = dp[0][0] + dp[0][2] + dp[0][3] = 1

n=1일 때 더 이상 비교할 경우의 수가 없다.

n = 2, k = 1: 합이 2이고 마지막 숫자가 1이 될 수 있는 경우 → [1, 1]이 있으나 중복됨으로 0가지
- 합이 1이고 마지막 숫자가 1이 아닌 경우
- dp[2][1] = dp[1][0] + dp[1][2] + dp[1][3] = 0 + 0 + 0 = 0
n = 2, k = 2: 합이 2이고 마지막 숫자가 2이 될 수 있는 경우 → [2] 가 가능함으로 1가지
- 합이 0이고 마지막 숫자가 2가 아닌 경우
- dp[2][2] = dp[0][0] + dp[0][1] + dp[1][3] = 1 + 0 + 0 = 1

n=2일 때 더 이상 비교할 경우의 수가 없다.(k가 2보다 클 수는 없음으로)

n = 3, k = 1: 합이 3이고 마지막 숫자가 1이 될 수 있는 경우 → [2, 1] 1가지
- 합이 2이고 마지막 숫자가 1이 아닌 경우
- dp[3][1] = dp[2][0] + dp[2][2] + dp[2][3] = 0 + 1 + 0 = 1
n = 3, k = 2: 합이 3이고 마지막 숫자가 2가 될 수 있는 경우 → [1, 2] 1가지
- 합이 1이고 마지막 숫자가 2가 아닌 경우
- dp[3][2] = dp[1][0] + dp[1][1] + dp[1][3] = 0 + 1 + 0 = 1
n = 3, k = 3: 합이 3이고 마지막 숫자가 3이 될 수 있는 경우 → [3] 1가지
- 합이 0이고 마지막 숫자가 3이 아닌 경우
- dp[3][3] = dp[0][0] + dp[0][1] + dp[0][2] = 1 + 0 + 0 = 1

n=3일 때 더 이상 비교할 경우의 수가 없다.(k가 3보다 클 수는 없음으로)

n = 4, k = 1: 합이 4이고 마지막 숫자가 1이 될 수 있는 경우 → [3, 1], [1, 2, 1] 2가지
- 합이 3이고 마지막 숫자가 1이 아닌 경우
- dp[4][1] = dp[3][0] + dp[3][2] + dp[3][3] = 0 + 1 + 1 = 2
n = 4, k = 2: 합이 4이고 마지막 숫자가 2가 될 수 있는 경우 → [1, 1, 2], [2, 2]가 있으나 연속됨으로 존재하지 않으로 0가지
- 합이 2이고 마지막 숫자가 2가 아닌 경우
- dp[4][2] = dp[2][0] + dp[2][1] + dp[2][3] = 0 + 0 + 0 = 0
n = 4, k = 3: 합이 4이고 마지막 숫자가 3이 될 수 있는 경우 → [1, 3] 1가지
- 합이 1이고 마지막 숫자가 3이 아닌 경우
- dp[4][3] = dp[1][0] + dp[1][1] + dp[1][2] = 0 + 1 + 0 = 1

n =4일 때 k의 최대값은 3임으로 더 이상 비교할 수 없다.

n = 5, k = 1: 합이 5이고 마지막 숫자가 1이 될 수 있는 경우 → [1, 3, 1], [2, 2, 1] 2가지
- 합이 4이고 마지막 숫자가 1이 아닌 경우
- dp[5][1] = dp[4][0] + dp[4][2] + dp[4][3] = 0 + 0 + 1 = 1’
n = 5, k = 2: 합이 5이고 마지막 숫자가 2가 될 수 있는 경우 → [1, 2, 2], [3, 2] 2가지
- 합이 3이고 마지막 숫자가 2가 아닌 경우
- dp[5][2] = dp[3][0] + dp[3][1] + dp[3][3] = 0 + 1 + 1 = 2
n = 5, k = 3: 합이 5이고 마지막 숫자가 3이 될 수 있는 경우 → [2, 3] 1가지
- 합이 2이고 마지막 숫자가 3이 아닌 경우
- dp[5][3] = dp[2][0] + dp[2][1] + dp[2][2] = 0 + 0 + 1 = 1

n =5이지만 k의 최대값은 3임으로 더 이상 비교할 수 없다.

최종적으로 n=5, k=3일 때의 결과를 얻을 수 있고 마지막 행의 합을 전부 더한 4가 정답이 된다.

Testcase

n = 5
k = 3
#result: 4

n = 5
k = 2
#result: 1

n = 1000
k = 100
#result: 722510153


n = 100
k = 5
# result: 100195169

n = 11
k = 3
# result: 37

8. Bus stop

문제 설명

도시의 아파트에서 버스 정류장까지 거리를 구하려고 합니다.

도시는 격자 모양의 지역으로 구분되어 있으며 아파트는(1)로, 버스 정류장은(0)으로 표시되어 있습니다.

아파트에서 버스 정류장으로 이동은 상 하 좌 우로만 이동할 수 있으며, 대각선으로는 이동이 불가합니다.

이러한 방식으로 구하는 거리를 맨해튼 거리라고 합니다.

h x w 크기의 도시가 2차원 정수 배열 city 로 주어질 때, 각 아파트에서 가장 가까운 버스 정류장까지의 거리를 구하는 프로그램을 구현하세요.

결과는 입력과 동일한 크기의 2차원 정수 배열로 반환하며, 아파트 위치에는 가장 가까운 버스 정류장까지의 거리를, 버스 정류장 위치에는 0을 입력하세요

단, 버스 정류장은 도시에서 최소 하나 이상 존재합니다.

입력 형식

city: 0과 1로 이루어진 2차원 정수 배열

출력 형식

입력과 동일한 크기의 2차원 정수 배열

제약 사항

0 < city.length ≤ 100
0 < city[i].length ≤ 100

입출력 예시

입력
- city = [[1, 0, 1], [1, 1, 1], [1, 1, 1]]
출력: [[ 1, 0, 1 ], [ 2, 1, 2 ], [ 3, 2, 3 ]]
설명: 이 도시에는 정류장이 1개밖에 없으므로, 해당 정류장까지의 맨해튼 거리를 구하면 된다.

풀이

시간이 없어서 제때 풀이를 못해서 문제를 저장해뒀다가 주말에 풀었다..

BFS를 활용해 최단거리를 구하면 풀린다.

단, 버스 정류장이 여러개가 있음으로 1의 위치에 대해서모든 0번 버스정류장의 거리를 구한 다음, 가장 최소값을 적용해 넣어주면 된다.

풀이는 아래와 같다

def solution(city):
    rows = len(city)
    cols = len(city[0])
    
    def bfs(start, end):
        
        q = collections.deque()
        q.append([start[0], start[1], 0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        visited = [[False]*cols for _ in range(rows)]
        visited[start[0]][start[1]] = True
        
        while q:
            x, y, dist = q.popleft()
            
            if (x, y) == end:
                return dist
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                
                if 0 <= nx < rows and 0 <= ny < cols:
                    if not visited[nx][ny]: # and city[i][j] == '0':
                        q.append([nx, ny, dist + 1])
                        visited[nx][ny] = True
            
    # find bus stop
    bus_stops = []
    for i in range(rows):
        for j in range(cols):
            if city[i][j] == 0:
                bus_stops.append((i, j))    
    
    
    for i in range(rows):
        for j in range(cols):
            if city[i][j] == 1:
                dist = sys.maxsize
                for bus_stop in bus_stops:
                    dist = min(bfs((i, j), bus_stop), dist)
                city[i][j] = dist
                    
    return city

Testcase

입력값 〉 [[1, 0, 1], 
				[1, 1, 1], 
				[1, 1, 1]]
				
기댓값 〉 [[1, 0, 1],
				[2, 1, 2], 
				[3, 2, 3]]

입력값 〉[[1, 1], 
			 [1, 1],
			 [1, 0]] 
			 
기댓값 〉 [[3, 2],
				[2, 1],
				[1, 0]]

입력값 〉 [[0, 1, 1, 1], 
        [1, 0, 1, 1],
        [1, 1, 0, 1],
        [1, 1, 1, 0]]
			 
기댓값 〉 [[0, 1, 2, 3],
        [1, 0, 1, 2],
        [2, 1, 0, 1],
        [3, 2, 1, 0]]

입력값 〉 [[0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0]]
			 
기댓값 〉 [[0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 2, 1, 0]]

입력값 〉 [[0], [1], [1], [1], [1], [1], [0], [1], [1], [1],[1], [1], [0]]
			 
기댓값 〉 [[0], [1], [2], [3], [2], [1], [0], [1], [2], [3], [2], [1], [0]]

출처:

해당 문제와 코드는 제로베이스(ZeroBase)에서 제공받았습니다.

11월 2주차 코딩 테스트 Study

목차

1. Billboard

문제 설명

제한 사항

입력 형식

출력 형식

풀이

TestCase

2. Take the sand (Nim 게임)

문제 설명

제한 사항

입력 형식

출력 형식

풀이

Test Case

3. Greatest Common divisor

문제 설명

입력 형식

출력 형식

풀이

Testcase

4. 중복문자 제거

문제 설명

입력 형식

출력 형식

Test Case

5. Repeat Alphabet

문제 설명

입력 형식

출력 형식

6. WordPatternGame

문제 설명

제한 사항

입력 형식

출력 형식

7. JumpCase

문제 설명

입력 형식

출력 형식

제약 사항

입출력 예시

풀이

Testcase

8. Bus stop

문제 설명

입력 형식

출력 형식

제약 사항

입출력 예시

풀이

Testcase

출처:

Comment