두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.
예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.
문제 해결 방법
순회를 통한 문제 해결
코드 구현
from collections import deque
def solution(X, Y):
answer = ''
tem = []
Y=list(Y)
Y.sort()
X=list(X)
X.sort()
y = deque(Y)
new = deque()
cnt = 0
for idx, i in enumerate(X):
while 1:
if cnt == len(y):
break
t= y[cnt]
if i == t:
del y[cnt]
tem.append(t)
break
else:
if y[cnt]<i:
cnt+=1
else:
break
if len(tem) == 0:
return '-1'
else:
cntt = 0
check = 0
while 1:
if cntt == len(tem):
break
if check == 1:
break
if tem[cntt] =='0':
check = 0
cntt +=1
else:
check =1
if check == 0:
return "0"
tem.sort(reverse=True)
answer = "".join(tem)
return answer
시간/공간 복잡도
최악의 경우 O(N)
최적화 및 개선
테스트케이스 11번~ 15번까지 실패했다.
실패 이유는 시간초과였는데, 문제 조건에서 X, Y는 최대 300만 까지의 길이를 가질 수 있다고 했다.
기존에 내가 작성한 코드는 X를 전부 돌면서 Y또한 전부 순회하도록 돼있었는데, 그러면 시간초과가 날 수 밖에 없는 상황이였다. 즉, 길이가 긴 대상을 전부 순회하지 않고 원하는 값을 찾아야 했다.
for i in range(10):
length = int(input())
check=[]
for j in range(8):
stringg = input()
check.append(stringg)
#print(check)
answer = 0
ccheck = 0
if length % 2 == 0: # 짝수
checkN = length // 2
ccheck = 0
else:
checkN = ((length+1)//2)-1 # 홀수 한 가운데
ccheck = 1
for one in check: # 가로 체크
stackk = []
if ccheck == 0:
for idx, k in enumerate(one):
if idx > len(one) - length:
break
for ik in range(checkN):
stackk.append(one[idx+1])
good = 0
for jk in range(checkN):
print
if stackk.pop == one[checkN+idx+1]:
good = 1
else:
good = 0
break
if good == 1:
answer+=1
else:
for idx, k in enumerate(one):
if idx > len(one) - length:
break
for ik in range(checkN):
stackk.append(one[idx+1])
good = 0
stackk.pop()
for jk in range(checkN-1):
if stackk.pop == one[checkN+idx+1]:
good = 1
else:
good = 0
if good == 1:
answer+=1
for p in range(8): # 세로 체크
stackk = []
if ccheck == 0:
for idx, two in enumerate(check):
if idx > len(two) - length:
break
for ik in range(checkN):
stackk.append(check[idx+ik][p])
good = 0
for jk in range(checkN):
if stackk.pop == check[checkN+idx+jk][p]:
good = 1
else:
good = 0
if good == 1:
answer+=1
else:
# 홀수
for idx, two in enumerate(check):
if idx > len(two) - length:
break
for ik in range(checkN):
stackk.append(check[idx+ik][p])
good = 0
stackk.pop()
for jk in range(checkN-1):
if stackk.pop == check[checkN+idx+jk][p]:
good = 1
else:
good = 0
if good == 1:
answer+=1
print("#"+str(i+1), str(answer))
N = int(input())
for i in range(N):
stringg=""
n, a, b = input().split()
n = int(n)
a = int(a)
b = int(b)
so = 0
dae = 0
if a+b <= n:
so = 0
else:
so = abs(a+b) - n
if a>= b:
dae = b
else:
dae = a
if a == b == n:
so = a
dae = b
if a == b and a != n:
dae = a
stringg="#"+str(i+1)+" "+ str(dae)+" "+ str(so)
print(stringg)
시간/공간 복잡도
최악의 경우 O(N)
최적화 및 개선
따로 하지않음
어려웠던 점 / 느낀점
애매하게 테스트케이스를 절반만 맞추고 이랬는데, 별 다르게 고쳐나갈 방법을 생각할 수 없었다.
테스트케이스로 들어갈만한 실제 값을 임의로 넣어보는 수 밖에 없었다.
사실 프로그래머스로 공부하다보면 질문하기 기능에 의존하게 되는데, swea는 질문 할 수도 없고 사람들이 댓글로 힌트를 달지 않은 경우, 오로지 혼자 힘으로 테스트케이스를 만들어서 적용해보는 수 밖에 없다.
한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.
한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.
문제 해결 방법
파이썬의 조합으로도 풀 수 있었지만, 백트래킹으로 문제를 풀었다.
number리스트의 원소별로 학생의 번호를 달았다. 왜냐하면 문제 제한 사항에 서로 다른 학생의 정수 번호가 같을 수 있다는 문구때문이다. 예를들어 number리스트에 학생 10명이 있다고 가정했을때, 5명의 정수 번호가 0이면 학생 번호로 구분해야한다.
number리스트를 방문 여부를 체크하면서 조건에 맞게 재귀 호출을 한 경우 카운트를 매기며, 총 카운트가 3이되면, 더이상 재귀 호출을 하지 않게끔 했다.
카운트가 3이 됐을때, 문제의 조건(삼총사의 정수 번호 합이 0인 경우)에도 부합하면 totalResult에 삼총사를 추가한다.
최종적으로 totalResult가 만들어졌으면, 중복된 요소들을 삭제하기 위해 요소들을 tuple형태로 바꾸어 주고, 리스트를 최종적으로 set() 으로 변경하기 좋은 상태를 만든다.
준비가 되었으면 set()으로 변경해주면 중복 요소 처리를 할 수 있다.
정리된 집합의 원소 수를 세면 그것이 정답이다.
코드 구현
dfs를 통해 구현한 코드
# 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사
def solution(number):
answer = 0
newL = []
for idx, i in enumerate(number):
newL.append([idx, i])
totalResult = []
def dfs(cnt, visited, summ, result, totalResult):
for idx, i in enumerate(newL):
if visited[idx] == False:
cnt += 1
summ += i[1]
visited[idx] = True
result.append(i)
if cnt == 3 and summ == 0:
totalResult.append(result[:])
if cnt < 3:
dfs(cnt, visited, summ, result, totalResult)
visited[idx] = False
cnt -= 1
summ -= i[1]
result.pop()
for idx, i in enumerate(newL):
summ, cnt = 0, 0
result = []
visited = [False] * len(newL)
visited[idx] = True
cnt+=1
summ+=i[1]
result.append(i)
dfs(cnt, visited, summ, result, totalResult)
newS = set()
tmpL = []
for i in totalResult:
tmpL = sorted(i, key = lambda x:x[0])
tuple_arr = [tuple(i) for i in tmpL]
newS.add(tuple(tuple_arr))
answer = len(newS)
return answer
시간/공간 복잡도
최악의 경우 O(N!)
최적화 및 개선
재귀 함수 호출시 불필요한 매개변수를 삭제함
어려웠던 점
이번 문제는 진짜 어려웠다.
특히 백트래킹을 구현할 때 계속 시간초과가 났다. 분명히 코드는 제대로 작성한것 같다고 생각했다.
코드를 분석해보니, 문제 조건과 카운트 수가 맞아서 totalResult에 삼총사를 추가하고나서 다음 절차를 진행할 때, totalResult내부의 값이 자꾸 바뀌는 문제가 발생했다. 알아보니 리스트를 새로 만들어주지 않고 계속 똑같은 리스트가 뒤에 절차를 진행할 때도 재활용된다는 문제였다. 이를 위해서 리스트 슬라이싱을 통해 새로운 리스트를 만드는 식으로 코드를 변경했더니 문제가 해결됐다.
이 이후에는 자꾸 대부분의 테스트케이스에서 시간 초과가 났다.
진짜 분명 코드는 제대로 작성한 것 같다고 생각했다.
그런데 아뿔싸 설마,,?
재귀 호출을 할때, 카운트 제한(3)을 조건문으로 걸어주지 않아서 시간 초과가 나는건가?
맞았다. 이때문에 불필요한 재귀 호출을 마구마구마구 하기 때문에 시간 초과가 났었다.
해당 조건을 추가해주고 나니 더이상 시간 초과가 나지 않았다.
그리고 리스트 원소를 중복제거 하기 위해서 집합자료형으로 바꾸는 과정에서 애를 먹었다.
그냥 일반 리스트면 몰라도 이중 리스트는 쉽지 않았다!!! 내부의 내부의 리스트를 튜플로 변경시켜주고, 그것들을 감싸고있는 껍데기도 튜플로 변경시켜줘야 한다. 그러면 Hashable 자료형인 튜플로 변경할 수 있게된다..!!!!!!
lv1짜리 문제지만, 내가 알고있는 파이썬 문법에 구멍이 있다는 것을 크게 깨달았다. 이대로 정진!!!!!!!
XX게임에는 피로도 시스템(0이상의 정수로 표현합니다)이 있으며,일정 피로도를 사용해서 던전을 탐험할 수 있습니다.이때,각 던전마다 탐험을 시작하기 위해 필요한"최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는"소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다.예를 들어"최소 필요 피로도"가80, "소모 피로도"가20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는80이상 이어야 하며,던전을 탐험한 후에는 피로도20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데,한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다.유저의 현재 피로도k와 각 던전별"최소 필요 피로도", "소모 피로도"가 담긴2차원 배열dungeons가 매개변수로 주어질 때,유저가 탐험할수 있는 최대 던전 수를return하도록solution함수를 완성해주세요.
제한사항
k는1이상5,000이하인 자연수입니다.
dungeons의 세로(행)길이(즉,던전의 개수)는1이상8이하입니다.
dungeons의 가로(열)길이는2입니다.
dungeons의 각 행은 각 던전의["최소 필요 피로도", "소모 피로도"]입니다.
"최소 필요 피로도"는 항상"소모 피로도"보다 크거나 같습니다.
"최소 필요 피로도"와"소모 피로도"는1이상1,000이하인 자연수입니다.
서로 다른 던전의["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
입출력 예
kdungeonsresult
80[[80,20],[50,40],[30,10]]3
입출력 예 설명
현재 피로도는80입니다.
만약,첫 번째→두 번째→세 번째 던전 순서로 탐험한다면
현재 피로도는80이며,첫 번째 던전을 돌기위해 필요한"최소 필요 피로도"또한80이므로,첫 번째 던전을 탐험할 수 있습니다.첫 번째 던전의"소모 피로도"는20이므로,던전을 탐험한 후 남은 피로도는60입니다.
남은 피로도는60이며,두 번째 던전을 돌기위해 필요한"최소 필요 피로도"는50이므로,두 번째 던전을 탐험할 수 있습니다.두 번째 던전의"소모 피로도"는40이므로,던전을 탐험한 후 남은 피로도는20입니다.
남은 피로도는20이며,세 번째 던전을 돌기위해 필요한"최소 필요 피로도"는30입니다.따라서 세 번째 던전은 탐험할 수 없습니다.
만약,첫 번째→세 번째→두 번째 던전 순서로 탐험한다면
현재 피로도는80이며,첫 번째 던전을 돌기위해 필요한"최소 필요 피로도"또한80이므로,첫 번째 던전을 탐험할 수 있습니다.첫 번째 던전의"소모 피로도"는20이므로,던전을 탐험한 후 남은 피로도는60입니다.
남은 피로도는60이며,세 번째 던전을 돌기위해 필요한"최소 필요 피로도"는30이므로,세 번째 던전을 탐험할 수 있습니다.세 번째 던전의"소모 피로도"는10이므로,던전을 탐험한 후 남은 피로도는50입니다.
남은 피로도는50이며,두 번째 던전을 돌기위해 필요한"최소 필요 피로도"는50이므로,두 번째 던전을 탐험할 수 있습니다.두 번째 던전의"소모 피로도"는40이므로,던전을 탐험한 후 남은 피로도는10입니다.
따라서 이 경우 세 던전을 모두 탐험할 수 있으며,유저가 탐험할 수 있는 최대 던전 수는3입니다.
문제 해결 방법
1. dungeons에서 모두 나올 수 있는 순서에 대해 경우의 수를 순열로 뽑는다.
2. 리스트를 하나 만들고, 순열로 뽑은 모든 경우의 수에 대해서 조건을 따져가면서 던전에 방문한 횟수를 카운트 하여 최종적으로 카운트 한 수를 해당 리스트에 추가한다.
2-1. 위에서 말한 조건으로 각 던전의 최소 필요 피로도가 k와 같거나 커야지 던전에 방문할 수 있으니 해당하는 조건을 체크한다.
from itertools import permutations
def solution(k, dungeons):
answer = -1
cpk=k
cases = list(permutations(dungeons, len(dungeons)))
checkList=[]
for i in range(len(cases)):
cpK=k
checkcheck = 0
for j in range(len(cases[i])):
if cpK >= cases[i][j][0]:
cpK = cpK - cases[i][j][1]
checkcheck += 1
else:
pass
if j == len(cases[i])-1:
checkList.append(checkcheck)
answer = max(checkList)
return answer
주석 포함 코드
from itertools import permutations
def solution(k, dungeons):
answer = -1
#print('k', k, 'dungeons', dungeons)
# 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"
# 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"
#최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됨
#하루에 한 번씩 탐험할 수 있는 던전이 여러개
# 1. dungeons는 [0]기준 MAX를 뽑는다.
# 2. dungeons의 순열을 뽑는다.
cpk=k
cases = list(permutations(dungeons, len(dungeons)))
#print(cases)
checkList=[]
#print("")
for i in range(len(cases)):
#maxx = cases[i][0][0]
cpK=k
#print("1 cpK", cpK)
checkcheck = 0
#print('i', i, cases[i])
for j in range(len(cases[i])):
#print('j', j, cases[i][j])
if cpK >= cases[i][j][0]:
cpK = cpK - cases[i][j][1]
#print('cpK', cpK)
checkcheck += 1
else:
pass
if j == len(cases[i])-1:
checkList.append(checkcheck)
#print("")
#print("")
#print(checkList)
answer= max(checkList)
return answer
dfs를 통해 구현한 현재 코드
def solution(k, dungeons):
answer = []
# k - 현재 피로도, 하루 한번 탐험가능한 던전 dungeons
# 유저가 탐험할 수 있는 최대 던전 수
cnt = len(dungeons)
visited = [False] * cnt
def check2(k, iz, io):
if k >= iz:
return k - io
else:
return None
def check(k, cnt, visited):
answer.append(cnt)
for idx, i in enumerate(dungeons):
cs, sm = i
if check2(k, cs, sm) and visited[idx] == False:
kk = check2(k, cs, sm)
visited[idx] = True
check(kk, cnt + 1, visited)
visited[idx] = False
# 예를들어서 1, 2, 3, 4, 5 가 있는데 조건 때문에 1, 2, 3까지 방문을 마치고 기록을 했다. 근데 이제 1, 2까지 온 상태에서 3을 빼고 나머지 4, 5와도 조합을 했을때 조건이 맞을 수 있기 때문에 3에 대한 방문을 false처리하고 나머지를 탐색해봐야해서
# visited[idx] = False 코드가 필요한 것임.
for idx, i in enumerate(dungeons):
visited = [False] * len(dungeons)
cs, sm = i
if check2(k, cs, sm):
valueK = check2(k, cs, sm)
visited[idx] = True
check(valueK, 1, visited)
print(answer)
answer = max(answer)
return answer
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
문제 해결 방법
triangle을 순회할때, n번째 리스트의 각 원소를 기준으로 n-1번째 리스트에서 자신이 거쳐올 수 있었던 원소 후보 중에서 큰 값을 자신과 더해나가면 된다.
코드 구현
def solution(triangle):
answer = 0
for idx, i in enumerate(triangle):
if idx == 0:
continue
for cnt, j in enumerate(i):
if cnt == 0:
i[cnt] = triangle[idx-1][cnt] + i[cnt]
elif cnt == len(i)-1:
i[cnt] = triangle[idx-1][cnt-1] + i[cnt]
else:
if triangle[idx-1][cnt-1] > triangle[idx-1][cnt]:
i[cnt] = triangle[idx-1][cnt-1] + i[cnt]
else:
i[cnt] = triangle[idx-1][cnt] + i[cnt]
if len(triangle)-1 == idx:
answer = max(triangle[idx])
return answer
다음 그림과 같이 지뢰가 있는 지역과 지뢰에 인접한 위, 아래, 좌, 우 대각선 칸을 모두 위험지역으로 분류합니다.
지뢰는 2차원 배열 board에 1로 표시되어 있고 board에는 지뢰가 매설 된 지역 1과, 지뢰가 없는 지역 0만 존재합니다.
지뢰가 매설된 지역의 지도 board가 매개변수로 주어질 때, 안전한 지역의 칸 수를 return하도록 solution 함수를 완성해주세요.
문제 해결 방법
폭탄 주변에 지뢰와 인접한 지역을 판단할 좌표를 미리 만들어두고, 지도를 탐색할 때, 폭탄이 발견되는 경우, 주변을 지뢰 인접 지역으로 표시하면된다.
코드 구현
def solution(board):
answer = 0
dx = [0, 0, -1, 1, -1, 1, -1, 1]
dy = [1, -1, 0, 0, 1, 1, -1, -1]
m = len(board)
for idx, i in enumerate(board):
for idx2, j in enumerate(i):
if j == 1:
# 상, 하, 좌, 우, 대각선 4개 다 -1칠하기
for k in range(8):
nx = idx+dx[k]
ny = idx2+dy[k]
if nx<0 or ny<0 or nx>=m or ny>=m:
continue
if board[nx][ny]==1:
continue
elif board[nx][ny]==-1:
continue
elif board[nx][ny]==0:
board[nx][ny]=-1
for i in board:
for j in i:
if j == 0:
answer+=1
return answer
하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.
한 번에 하나의 원판만 옮길 수 있습니다.
큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.
1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.
문제 해결 방법
재귀 함수를 이용하여 문제를 해결하면 된다.
n개의 원판을 x에서 y로 움직여야 하는 경우, 로직은 다음과 같다.
1. n-1개의 원판을 x번 기둥에서 6-x-y번 기둥으로 옮긴다. (n이 1이 될 때까지, n이 1이 되는 경우 x번기둥에서 y번 기둥으로 바로 옮겨준다. )
2. n번째 원판을 x번 기둥에서 y번 기둥으로 옮긴다.
3. n-1개의 원판을 6-x-y번 기둥에서 3번 기둥으로 옮긴다. (n이 1이 될 때까지)
(n이 1이 될 때까지, n이 1이 되는 경우 x번기둥에서 y번 기둥으로 바로 옮겨준다. )
