N과 M문제는 자다가도 풀 수 있어야 한다고 해서 순열로 풀었다가 눈물 좍좍 흘리면서 백트래킹을 뿌셨다.
백트래킹은 불필요한 경우를 탐색하지 않는다. 즉 특정 조건에서는 탐색을 그만하고 뒤로 되돌아가는(back) 성질을 가지고 있다. 따라서 DFS로 무작정 들이박으면 시간초과가 나는 상황에 유용하게 쓰이겠다.
숫자 1~N까지 중복 없는 M개의 요소를 가진 수열을 구하는 문제이다.
따라서 1) 수열의 길이가 M을 넘으면 안됨 2) 배열 내에 중복 X 두 가지 조건을 만족하는 숫자 뽑기를 진행하면 된다.
ex. N = 4, M = 3
첫번째 숫자로 1,2,3,4 중 가장 작은 숫자인 1을 선택한다. -> for 문으로 순차 증가
두번째 숫자로 2,3,4 중 가장 작은 숫자인 2를 선택한다. -> 선택 과정에서 배열 안에 존재하는지 체크하여 중복 제거
세번째 숫자로 3,4 중 가장 작은 숫자인 3을 선택한다.
수열의 길이가 M(3)이 되었으므로 다시 단계 3로 돌아간다. -> 재귀 탈출
세번째 숫자로 4를 고른다.
수열의 길이가 M(3)이 되었으므로 단계 2로 돌아간다.
두번째 숫자로 다음 작은 숫자인 3를 선택한다.
세번째 숫자로 2,3,4 중 2를 선택한다. -> 추후 여기에서 다시 숫자를 고를 때 3은 이미 배열안에 존재하므로 X
... 반복
즉 위의 과정을 코드로 구현하면 다음과 같다.
n, m = map(int, input().split())
result = []
def backTracking():
# 수열의 길이가 m이면 출력해주고 전단계로 돌아가기 (재귀 탈출)
if len(result) == m:
print(" ".join(map(str, result))) # "구분자".join(리스트)
return
# 1 ~ n 까지 체크
for i in range(1, n + 1):
# 중복 체크
if i not in result:
result.append(i)
backTracking()
# return 문으로 돌아온 경우 실행되는 부분
result.pop() # n=4, m=3일때 1,2,3이 들어온 경우 3을 없앰으로써 전단계로 돌아감
backTracking()
백트래킹 어렵다. 재귀라서 더 어렵게 느끼는 것 같기도 하고...! 익숙해질때까지 킵고잉이다 정말
출력 관련해서 문자열 다룰 때 자주 쓰이는 함수 join도 짚고 가보자.
"구분자".join(리스트) 형태로 사용하며 join 함수는 매개변수로 들어온 리스트에 있는 요소 하나 하나를 합쳐서 하나의 문자열로 바꿔 반환하는 함수이다. "구분자"를 값과 값 사이에 넣어서 하나의 문자열로 합쳐준다!
파이썬이 문자열 다룰 때 깡패인 언어인 만큼 join함수에도 익숙해지자. 자주 써야된다~!
수학 -> 자료구조 -> 재귀 -> DP -> 그래프(DFS/BFS) -> 최단경로 -> 이분탐색 -> 분할정복 -> 그리디 -> 완전탐색, 시뮬레이션, 구현(가능하면 이걸 많이 푸는 게 좋다. 구현력이 늘고 풀 수 있는 문제가 많아진다) -> 문자열 -> 투 포인터, 슬라이딩 윈도우 -> 백트래킹 1주씩
DP로 접근했는데 애초에 재귀를 보면서 분명 같은 경우를 살펴볼 일이 없어야 하는데... 같은 경우를 체크한다...ㅠㅠㅠ
실패한 소스코드
import copy
frodo = [0 for _ in range(11)]
answer = []
max_gap = 0
def cmpScore(frodo, apeach):
score_f = 0
score_ap = 0
for i in range(11):
if frodo[i] > apeach[i]:
score_f += 10-i
elif frodo[i] <= apeach[i] and apeach[i] != 0:
score_ap += 10-i
else:
continue
return score_f - score_ap
def isFrodoWinner(frodo, apeach):
score_f = 0
score_ap = 0
for i in range(11):
if frodo[i] > apeach[i]:
score_f += 10-i
elif frodo[i] <= apeach[i] and apeach[i] != 0:
score_ap += 10-i
# k점에 아무도 못 맞힌 경우
else:
continue
if score_f > score_ap:
return True
else:
return False
def shoot(score, n, info):
global max_gap
# 해당 점수 맞히는 경우
frodo[10-score] = info[10-score] + 1
if sum(frodo) == n:
# print(frodo, isFrodoWinner(frodo, info))
if isFrodoWinner(frodo, info):
if len(answer) == 0:
answer.append(copy.deepcopy(frodo))
max_gap = cmpScore(frodo, info)
else:
if max_gap < cmpScore(frodo, info):
answer.clear()
answer.append(copy.deepcopy(frodo))
max_gap = cmpScore(frodo, info)
elif max_gap == cmpScore(frodo, info):
answer.append(copy.deepcopy(frodo))
return
elif sum(frodo) > n:
frodo[10-score] = 0
if score - 1 < 0:
return
else:
shoot(score-1, n, info)
else:
if score - 1 < 0:
return
else:
shoot(score-1, n, info)
# 해당 점수 안맞히고 넘어가는 경우
frodo[10-score] = 0
if score - 1 < 0:
return
else:
shoot(score-1, n, info)
def solution(n, info):
shoot(10, n, info)
if len(answer) == 0:
answer.append([-1])
else:
answer.sort(key=lambda x:(-x[10], -x[9], -x[8], -x[7], -x[6], -x[5], -x[4], -x[3], -x[2], -x[1], -x[0]))
print(answer)
return answer[0]
올바른 접근
완전 탐색으로 접근
0점부터 10점까지 모든 점수를 획득할지 말지만 결정하면 되므로 모든 경우의 수는 2^11 로 충분히 살펴볼 수 있다. 2시간 넘게 DP로 끙끙 앓았더니 슬프다. 운동하고 와서 다른 사람 코드 좀 보고... 카카오 코테 보기 전날 한번 더 완탐 문제들 풀어볼 때 다시 봐야겠다. 아직 문제 유형을 파악하는데 서툴구만 흑
BFS 접근
1. 10점부터 0점까지 화살 쏨
현재 몇점인지 : score ( 0 -> 10점과녁)
현재 라이언 과녁 상황 : lion [0 for _ in range(11)]
2. 어피치를 이기려면
1) 어피치보다 +1발
2) 해당 점수 포기
* 주의할 점은 그냥 '=' 연산자 써서는 X. copy() 메소드로 깊은 복사 해주자.
( 2차원 이상의 배열을 깊은 복사 해주려면 copy 라이브러리의 deepcopy() 메소드 써야한다. 리스트의 copy() 메소드는 1차원까지만 깊은 복사 지원 )
3. 조건 체크
1) 화살을 n발보다 더 쏜 경우 ( sum(lion) > n ) : 패스
2) 0점까지 갔는데 다 못 쏜 경우 ( score == 10 ): 마지막 과녁에 다 쏘기
3) 다 쏜 경우 ( sum(lion) == n ) : 점수 계산. 최대 점수차 갱신해가면서 최대 점수차를 내는 경우만 따로 배열로 저장하기
4. shoot() 함수를 실행한뒤 최종 조건 체크
1) 리턴값이 빈 배열인 경우 : [-1] 리턴
2) 리턴값 배열의 길이가 1인 경우 : 해당 배열 리턴
3) 그 외의 경우 : 가장 낮은 점수를 많이 맞힌 경우 리턴.
* score을 통해 가장 높은 점수부터 쏘기 시작했으므로 배열의 가장 마지막 요소가 해당됨.
python 코드
from collections import deque
def shoot(n, info):
q = deque([(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])])
result = [] # 가능한 시나리오 모두 저장
max_gap = 0 # 최대 점수차
while q:
score, lion = q.popleft()
# 화살 다 쐈으니 점수 계산
if sum(lion) == n:
score_ap, score_l = 0, 0
for i in range(11):
if not (info[i] == 0 and lion[i] == 0):
if info[i] >= lion[i]:
score_ap += 10 - i
else:
score_l += 10 - i
if score_ap < score_l:
gap = score_l - score_ap
if max_gap > gap:
continue
if max_gap < gap:
max_gap = gap
result.clear()
result.append(lion)
# 화살을 n발보다 더 쏜 경우
elif sum(lion) > n:
continue
# 마지막 과녁까지 간 경우, 화살 마지막 과녁에 다 쏘기
elif score == 10:
tmp = lion.copy()
tmp[score] = n - sum(tmp)
q.append((-1, tmp))
# 슛슛슛
else:
# 어피치보다 1발 더
shoot_lion = lion.copy()
shoot_lion[score] = info[score] + 1
q.append((score + 1, shoot_lion))
# 해당 점수 포기, 패스
giveup_lion = lion.copy()
giveup_lion[score] = 0
q.append((score + 1, giveup_lion))
return result
def solution(n, info):
answer = []
all_cases = shoot(n, info)
if len(all_cases) == 0:
answer.append(-1)
elif len(all_cases) == 1:
answer = all_cases[0]
else:
answer = all_cases[-1]
return answer
파이썬 내 올림 기능을 지원하는 메소드가 math.ceil 인데 실수로 반올림하는 round() 메서드를 썼다... 주의하자!
먼저 수도코드로 쭉 작성한 뒤 구현했고, 바로 통과됬다.
1. records 내 값을 공백 기준으로 split해서 time, car_num, inout에 넣기
2. 딕셔너리에 car_num을 키로 time 넣어주기. 각 딕셔너리 value값은 배열. (in, out 순서로 들어간다)
* 만약 배열 길이가 홀수면 출차 내역이 입력되지 않은 요소이므로 23:59를 직접 넣어준다
3. records 배열 순회가 끝나면 딕셔너리를 살펴보면서 시간을 계산한다.
- [짝수] : IN / [홀수] : OUT 이므로 홀수 - 짝수 해주면 된다.
인자를 받아올 때 ":"를 기준으로 hour, min을 쪼개주었다.
시간은 상관없는데 분은 음수값이 나왔을 때 예외처리를 해주자. (hour -= 1, min += 60)
4. 총 누적시간이 기본 시간을 넘는다면 문제 조건대로 계산하고, 넘지 않는다면 기본 요금을 저장한다.
* 여기에서 문제 조건 상 차량번호가 작은 요소부터 출력해달라고 했으므로 [차량번호, 요금] 을 저장하는 배열을 만들어준 뒤 차량번호를 기준으로 정렬한 뒤 요금값을 차례대로 answer에 넣어주자.
40분 정도 소요됬다!
python 코드
import math
def solution(fees, records):
carnum_fee = [] # (차량번호, 요금) 순 저장
car_dict = {}
for r in records:
time, car_num, inout = r.split(" ")
if car_num in car_dict:
car_dict[car_num].append(time)
else:
car_dict[car_num] = [time]
for k in car_dict.keys():
# 출차 기록이 없는 경우
if len(car_dict[k]) % 2 != 0:
car_dict[k].append("23:59")
# 시간 계산
total_time = 0
for i in range(0, len(car_dict[k]), 2):
# OUT : i+1, IN : i
out_h, out_m = map(int,car_dict[k][i+1].split(":"))
in_h, in_m = map(int, car_dict[k][i].split(":"))
hour = out_h - in_h
minute = out_m - in_m
if minute < 0:
hour -= 1
minute += 60
total_time += hour * 60 + minute
# 요금 계산
if total_time > fees[0]:
carnum_fee.append([k, fees[1] + math.ceil((total_time-fees[0]) / fees[2]) * fees[3]])
else:
carnum_fee.append([k, fees[1]])
carnum_fee.sort(key = lambda x : x[0])
answer = [v[1] for v in carnum_fee]
return answer
진법변환, 소수판별은 자주 등장하는 부분이라 비교적 쉽게 구현했다. 소수의 판별 조건이 약간 까다로웠는데 가능한 시나리오들을 차근차근 생각해봤다.
1. 진법변환
2. 앞에서부터 살펴보는데
1) 맨 앞인 경우 -> P0, P 케이스가 등장할 수 있다.
- P0 : 뒷 숫자에서 0이 등장하는 경우, 그 앞까지의 숫자가 소수인지 체크
- P : 숫자 끝까지 0이 등장하지 않는 경우, 해당 숫자 자체가 소수인지 체크
2) 0이 한번이라도 등장한 경우 -> 0P0, 0P 케이스가 등장할 수 있다.
- 0P0 : 0이 한번 더 등장한 경우, 0과 0 사이의 숫자가 소수인지 체크
- 0P : 숫자 끝까지 0이 한번 더 등장하지 않은 경우, 0 뒤의 숫자가 소수인지 체크
따라서 가능한 경우를 flag로 만들어서 체크해줘야 할 때마다 체크해줬다. 요즘 디버깅 안하고 프로그래머스 내에서 최대한 풀어보려고 하다 보니 print 문을 섞어서 실행했다. 두가지 버전 모두 기록해두려고 한다!
주의할 점은 소수인지 체크할 숫자를 담는 문자열이 빈 문자열인 경우 소수 체크를 하지 않고 넘어가줘야 한다. (코드 내 check_num != '' 조건)
ex. P0 경우가 등장하여 check_num이 빈 문자열로 초기화되었는데 그 뒤에 다시 0이 등장하면 빈 문자열이 isPrime 함수로 넘어가 형변환 에러가 발생한다.
중간에 10분정도 쉬다가 다시 풀었는데 한 1시간정도 걸렸다.
python 코드 (print 출력문 O)
# 진법 변환
def convert(n, k):
result = ''
q, r = divmod(n, k)
result += str(r)
while q != 0:
q, r = divmod(q, k)
result += str(r)
return result[::-1]
# 소수 판별 (제곱근까지만 판단)
def isPrime(num):
if num == 0 or num == 1:
return False
for i in range(2, int(num**0.5)+1):
if num % i == 0:
# 소수 아님
return False
return True
def solution(n, k):
answer = 0
converted_n = convert(n, k)
check_num = ''
flag_0P0 = False
flag_P0 = False
flag_0P = False
flag_P = False
for i in range(len(converted_n)):
print("------")
print(flag_0P0,flag_P0,flag_0P,flag_P)
print(check_num)
print("------")
# 맨 앞인 경우
if i == 0:
# P0, P 가능
check_num += converted_n[i]
flag_P, flag_P0 = True, True
continue
if converted_n[i] == '0':
flag_P = False
flag_0P = True
# 만약 맨앞에서부터 보던 중이었다면
if flag_P0:
print("PO case", check_num)
if isPrime(int(check_num)):
print("PO Hit", check_num)
answer += 1
check_num = ''
flag_0P0, flag_P0 = True, False
continue
# 한번이라도 0이 등장한 적이 있다면
elif flag_0P0 and check_num != '':
print("0PO case", check_num)
if isPrime(int(check_num)):
print("0PO Hit", check_num)
answer += 1
check_num = ''
else:
check_num += converted_n[i]
# 맨 뒤까지 다 봤는데 0이 안나온 경우였다면, P 경우 체크
if flag_P and check_num != '' and isPrime(int(check_num)) :
answer += 1
print("P Hit", check_num)
# 맨 뒤까지 다 봤고 0P가 가능한 경우
if flag_0P and check_num != '' and isPrime(int(check_num)) :
answer += 1
print("0P Hit", check_num)
return answer
python 코드 (깔끔 ver)
# 2022-09-20
# 2022 카카오 테크 인턴십 기출 - k진수에서 소수 개수 구하기 (프로그래머스 lv2)
# https://school.programmers.co.kr/learn/courses/30/lessons/92335
# 소요 시간 : 15:17 ~ 16:06, 16:21~16:31 (60m)
# 진법 변환
def convert(n, k):
result = ""
q, r = divmod(n, k)
result += str(r)
while q != 0:
q, r = divmod(q, k)
result += str(r)
return result[::-1]
# 소수 판별 (제곱근까지만 판단)
def isPrime(num):
if num == 0 or num == 1:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
# 소수 아님
return False
return True
def solution(n, k):
answer = 0
converted_n = convert(n, k)
check_num = ""
flag_0P0 = False
flag_P0 = False
flag_0P = False
flag_P = False
for i in range(len(converted_n)):
# 맨 앞인 경우
if i == 0:
# P0, P 가능
check_num += converted_n[i]
flag_P, flag_P0 = True, True
continue
if converted_n[i] == "0":
flag_P = False
flag_0P = True
# 만약 맨앞에서부터 보던 중이었다면
if flag_P0:
if isPrime(int(check_num)):
answer += 1
check_num = ""
flag_0P0, flag_P0 = True, False
continue
# 한번이라도 0이 등장한 적이 있다면
elif flag_0P0 and check_num != "":
if isPrime(int(check_num)):
answer += 1
check_num = ""
else:
check_num += converted_n[i]
# 맨 뒤까지 다 봤는데 0이 안나온 경우였다면, P 경우 체크
if flag_P and check_num != "" and isPrime(int(check_num)):
answer += 1
# 맨 뒤까지 다 봤고 0P가 가능한 경우
if flag_0P and check_num != "" and isPrime(int(check_num)):
answer += 1
return answer
두 큐의 합을 같게 만들어주려면, 합이 더 큰 큐에서 pop해가면서 중간값을 맞춰봐야 최소횟수.
이 과정에서 완전히 빈 큐가 생겨버리면 두 큐의 합을 같게 만들 수 없는 것이므로 -1을 리턴해주면 된다.
로직 자체는 맞게 접근한 것 같은데 테스트케이스 몇개가 계속 시간초과가 나서 파이썬 메서드의 시간복잡도를 봤더니 답이 나왔다.
배열의 가장 앞의 요소를 pop해주기 위해 배열 자료형의 pop(0) 메서드를 사용했는데, pop() 연산 자체는 복잡도가 O(1)인데 pop(0)은 O(n)이다. 그 이유는 맨 앞에 있는 값을 출력해주기 위해 전체 복사를 하기 때문이다..! 따라서 리스트 말고 deque를 사용하여 pop(0) 대신 popleft()를 사용하는 것이 시간복잡도 상 매우 유리하다.
자료형을 list -> deque로 바꾸고 테스트케이스 22~24번이 해결됬으며,
최대 가능한 횟수를 모든 요소끼리 서로 다 바꿔도 안될 때 (리스트의 최대길이만큼 교환했을 때) 300,000번으로 제한해두니 테스트케이스 11, 28번이 해결되었다.
sum() 메서드와 len() 메서드 역시 매번 연산해줄 필요는 없어서 산술연산만 할 수 있게 코드를 약간 길게 적었다.
방향은 맞게 잡았는데 시간복잡도에서 30분은 더 쓴 듯 하다.
python 코드
from collections import deque
def solution(queue1, queue2):
answer = 0
deque1 = deque(queue1)
deque2 = deque(queue2)
sum1 = sum(queue1)
sum2 = sum(queue2)
len1 = len(queue1)
len2 = len(queue2)
goal = (sum1 + sum2) / 2
while len1 != 0 and len2 != 0:
if sum1 == goal and sum2 == goal:
return answer
if answer > 300000:
break
if sum1 > sum2:
value = deque1.popleft()
deque2.append(value)
sum1 -= value
sum2 += value
len1 -= 1
len2 += 1
elif sum1 < sum2:
value = deque2.popleft()
deque1.append(value)
sum1 += value
sum2 -= value
len1 += 1
len2 -= 1
else:
if sum1 == goal and sum2 == goal:
return answer
answer += 1
answer = -1
return answer
유일성을 만족하기 위해 set 자료형을 사용했다. 키의 최대 길이가 8개로, 가능한 키 조합을 모두 구해 각 경우별로 set 자료형으로 변환해도 길이가 변하지 않는 것을 체크했다.
2차원 배열은 set연산을 적용하기가 골치 아파 중간에 한번 tuple 자료형으로 변환해주었다.
유일성을 만족하는 모든 경우의 수를 ck_list 배열에 저장한 뒤, ck_list 배열을 돌면서 최소성을 만족하는지 체크했다.
최소성을 만족하는지 체크하기 위해 실제로 최소성을 만족하는 후보키 배열 ck를 만들었다. 모든 후보키에 대해 합집합을 수행해 키가 최소성을 만족하는 경우를 체크했다. (단순히 합집합 한번만 했더니 [(0), (1,2)]과 [1,2,3] 경우를 계산하는 과정에서 0, (1,2,3) 이 조건을 만족하는 것으로 되서 cnt 변수를 통해 모든 후보키에 대해서 고려하도록 수정했다.)
한시간정도 걸린 문제였다. 은근 어려워..!
코드
from itertools import combinations
def solution(relation):
answer = 0
column_list = [i for i in range(len(relation[0]))]
# 모든 후보키가 될 수 있는 경우의 수(컬럼 인덱스 배열)
cases = []
for i in range(1, len(column_list)+1):
cases.append(list(combinations(column_list, i)))
ck_list = []
for case_list in cases:
for case in case_list:
all_senario = []
for row in range(len(relation)):
arr = [relation[row][c] for c in case]
all_senario.append(tuple(arr))
# print(all_senario)
if len(all_senario) == len(list(set(all_senario))):
ck_list.append(case)
# print(ck_list)
ck = []
for key in ck_list:
if len(ck) == 0:
ck.append(key)
continue
cnt = 0
for k in ck:
if set(key) != set(k) | set(key):
cnt += 1
if cnt == len(ck):
ck.append(key)
answer = len(ck)
return answer
