coding 연습/프로그래머스
프로그래머스 level2 문제들(정답률 50%~60%)
blackbearwow
2024. 2. 5. 20:50
- 게임 맵 최단거리
처음에는 dfs로 풀어 시간초과가 되었지만, bfs로 푸니 빠르게 풀 수 있었다.
def solution(maps):
from collections import deque
answer = -1
height = len(maps)
width = len(maps[0])
queue = deque()
queue.append((0, 0))
udlr = [[0,1],[0,-1],[-1,0],[1,0]]
while len(queue) != 0:
(y, x) = queue.popleft()
# 상하좌우
for idx in range(4):
nx = x + udlr[idx][1]
ny = y + udlr[idx][0]
if ny >= 0 and nx>=0 and ny<height and nx<width and maps[ny][nx] == 1:
queue.append((ny, nx))
maps[ny][nx] = maps[y][x] + 1
if maps[height-1][width-1] == 1:
maps[height-1][width-1] = -1
return maps[height-1][width-1]- 모음사전
def solution(word):
answer = 0
# 5번째는 ' ', 'A', 'E', 'I', 'O', 'U' 6가지가 올 수 있다
# 4,5번째는 31(6x5+1)가지가 올 수 있다
# 3,4,5번째는 156(31x5+1)가지가 올 수 있다
# 2,3,4,5번째는 781(156x5+1)가지가 올 수 있다
count = 0
# 해당 알파벳이 나왔을 때 곱해야 할 숫자
constDict = {'A':0, 'E':1, 'I':2, 'O':3, 'U':4}
countNumList = [781, 156, 31, 6, 1]
# 0번째 자리부터 4번째 자리까지 나올 수 있는 숫자들을 더함
while count < len(word):
answer += constDict[word[count]] * countNumList[count]
answer += 1
count += 1
return answer- 더 맵게
def solution(scoville, K):
answer = 0
scoville.sort(reverse=True)
length = len(scoville)
while scoville[length-1] < K:
if length < 2:
break
scoville[length-2] = scoville[length-1]+scoville[length-2]*2
del scoville[length-1]
length -= 1
scoville.sort(reverse=True)
answer += 1
if scoville[0] < K:
answer = -1
return answer위와 같이 하면 효율성 테스트를 통과할 수 없다.
def solution(scoville, K):
import heapq
answer = 0
heapq.heapify(scoville)
while scoville[0] < K:
if len(scoville) < 2:
return -1
min1 = heapq.heappop(scoville)
min2 = heapq.heappop(scoville)
heapq.heappush(scoville, min1+min2*2)
answer += 1
return answer위는 hepq 라이브러리를 사용하여 풀었다.
직접 힙을 구현한 클래스를 사용하였는데, 효율설테스트를 통과하지 못했다.
- 뒤에 있는 큰 수 찾기
def solution(numbers):
# stack을 이용해보자
answer = [0 for i in range(len(numbers))]
stack = []
for i in range(len(numbers)):
num = numbers[i]
# 스택에 마지막 부분이 현재 숫자보다 작다면?
while len(stack) > 0 and stack[len(stack)-1][0] < num:
answer[stack.pop()[1]] = num
stack.append([num, i])
while len(stack) > 0:
answer[stack.pop()[1]] = -1
return answer- 주차 요금 계산
def solution(fees, records):
import math
defaultTime = fees[0]
defaultFee = fees[1]
unitTime = fees[2]
unitFee = fees[3]
inoutDict = {}
timeDict = {}
for record in records:
time = int(record[0:2]) * 60 + int(record[3:5])
carNum = record[6:10]
if record[11:] == 'IN':
inoutDict[carNum] = time
else:
if carNum in timeDict:
timeDict[carNum] += time - inoutDict[carNum]
else:
timeDict[carNum] = time - inoutDict[carNum]
del inoutDict[carNum]
for carNum, time in inoutDict.items():
if carNum in timeDict:
timeDict[carNum] += 23*60+59 - time
else:
timeDict[carNum] = 23*60+59 - time
answer = sorted(timeDict.items())
for i in range(len(answer)):
if answer[i][1] <= defaultTime:
answer[i] = defaultFee
else:
answer[i] = defaultFee + math.ceil((answer[i][1] - defaultTime) / unitTime) * unitFee
return answer- 방문 길이
def solution(dirs):
# 가로줄 11개 세로줄 11개이다. 각 10칸씩 나뉜다.
horizontal = [[0 for x in range(10)]for y in range(11)]
vertical = [[0 for x in range(11)]for y in range(10)]
currentX = 0
currentY = 0
answer = 0
for dir in dirs:
if dir == "U":
if currentY != 5:
if vertical[currentY+5][currentX+5] == 0:
answer += 1
vertical[currentY+5][currentX+5] = 1
currentY += 1
elif dir == "D":
if currentY != -5:
if vertical[currentY+4][currentX+5] == 0:
answer += 1
vertical[currentY+4][currentX+5] = 1
currentY -= 1
elif dir == "L":
if currentX != -5:
if horizontal[currentY+5][currentX+4] == 0:
answer += 1
horizontal[currentY+5][currentX+4] = 1
currentX -= 1
elif dir == "R":
if currentX != 5:
if horizontal[currentY+5][currentX+5] == 0:
answer += 1
horizontal[currentY+5][currentX+5] = 1
currentX += 1
return answer- 주식가격
def solution(prices):
answer = []
for i in range(len(prices)):
count = 0
for k in range(i+1, len(prices)):
count += 1
if prices[i] > prices[k]:
break
answer.append(count)
return answer2중for문을 사용해도 문제가 통과된다.
def solution(prices):
pLength = len(prices)
answer = [0 for i in range(pLength)]
stack = []
for idx in range(pLength):
# stack에 현재보다 큰 숫자가 top이면 answer에 반영하기
while len(stack) != 0 and prices[stack[-1]] > prices[idx]:
beforeIdx = stack.pop()
answer[beforeIdx] = idx - beforeIdx
# stack에 인덱스 push
stack.append(idx)
# stack에 남아있는것들 처리
while len(stack) != 0:
beforeIdx = stack.pop()
answer[beforeIdx] = pLength - beforeIdx - 1
return answerstack으로 하면 효율성 문제가 2중for문을 사용한것보다 3~4배 빠르다.
- 땅따먹기
처음에는 dfs문제인줄 알고 stack을 사용해 완전탐색을 했다. 하지만 효율성 검사가 아닌 정확성 검사에서조차 시간초과가 뜨면서 안되었다. 질문하기를 살펴보니 dp(dynamic programming)를 사용해 푸는것이라고 한다. 보아하니 꼭 모든 경우를 탐색할 필요가 없었다. 최대값만 구하는 문제이니 해당 칸이 가질 수 있는 최대값들을 구해나가면 되는 문제이다.
def solution(land):
stack = []
answer = 0
xLength = len(land[0])
yLength = len(land)
# 최대값을 가지는 배열
arr=[[0 for x in range(xLength)]for y in range(yLength)]
arr[0] = land[0]
for y in range(1, yLength):
for x in range(xLength):
# 전 행에서 자신을 제외한 열의 최대값 + 자신의 땅 점수가 현재 땅 점수의 최대값이 된다
arr[y][x] = land[y][x] + max(arr[y-1][:x] + arr[y-1][x+1:])
answer = max(arr[yLength-1])
return answer- 스킬트리
def solution(skill, skill_trees):
answer = 0
preSkill = {}
for skill_tree in skill_trees:
preSkill[skill[0]] = {'need': None, 'learn': False}
for i in range(1, len(skill)):
preSkill[skill[i]] = {'need': skill[i-1], 'learn': False}
idx = 0
while idx < len(skill_tree):
# 배울 수 없는 스킬이면 break
if skill_tree[idx] in preSkill:
if preSkill[skill_tree[idx]]['need'] == None:
preSkill[skill_tree[idx]]['learn'] = True
elif preSkill[preSkill[skill_tree[idx]]['need']]['learn'] == True:
preSkill[skill_tree[idx]]['learn'] = True
else:
break
idx += 1
if idx == len(skill_tree):
answer += 1
return answer- 롤케이크 자르기
순차탐색을 했을 때 시간초과를 했지만, 이진탐색을 사용하고 통과했다.
def solution(topping):
import math
answer = 0
low = 0
high = len(topping)
mid = math.ceil((low+high)/2)
# 왼쪽토핑가지수가 오른쪽토핑가지수보다 작을 때의 최대인덱스
while low != high:
if len(set(topping[:mid])) < len(set(topping[mid:])):
low = mid
mid = math.ceil((low+high)/2)
else:
high = mid - 1
mid = math.ceil((low+high)/2)
lowerMax = mid
low = 0
high = len(topping)
mid = (low+high)//2
# 왼쪽토핑가지수가 오른쪽토핑가지수보다 클 때의 최소인덱스
while low != mid:
if len(set(topping[:mid])) > len(set(topping[mid:])):
high = mid
mid = (low+high)//2
else:
low = mid
mid = (low+high)//2
higherMin = high
return higherMin - lowerMax - 1- 오픈채팅방
def solution(record):
answer = []
idNick = {}
# 아이디에 대응하는 닉네임 알아내기
for x in record:
cmd = x.split()[0]
if cmd == "Enter" or cmd == "Change":
cmd, uid, nick = x.split()
idNick[uid] = nick
# 메시지 알아내기
for x in record:
cmd = x.split()[0]
if cmd == "Enter":
cmd, uid, nick = x.split()
answer.append(f"{idNick[uid]}님이 들어왔습니다.")
elif cmd == "Leave":
cmd, uid = x.split()
answer.append(f"{idNick[uid]}님이 나갔습니다.")
return answer- [3차] 파일명 정렬
def solution(files):
import re
# Head 영문대소문자, 공백, 마침표, 빼기 부호 (숫자전까지)
# NUMBER 숫자만 1~5글자
# TAIL NUMBER 뒤 나머지
files.sort(key=lambda x:(re.search("[A-Za-z .-]+", x)[0].upper(), int(re.search("[0-9]+", x)[0])))
return files- [1차] 프렌즈4블록
def solution(m, n, board):
for y in range(m):
board[y] = list(board[y])
answer = 0
change = [[0 for x in range(n)]for y in range(m)]
changeCount = 1
while changeCount != 0:
changeCount = 0
# 2x2 형태라면 바꿔야할 것이다.
for y in range(m-1):
for x in range(n-1):
if board[y][x] != ' ' and board[y][x] == board[y][x+1] == board[y+1][x] == board[y+1][x+1]:
change[y][x] = 1
change[y][x+1] = 1
change[y+1][x] = 1
change[y+1][x+1] = 1
# 바꿔야할 것을 0으로 바꿈.
for y in range(m):
for x in range(n):
if change[y][x] == 1:
board[y][x] = ' '
change[y][x] = 0
changeCount += 1
# 빈공간이 있으면 아래로 채운다.
for y in range(m-2, -1, -1):
for x in range(n):
if board[y][x] != ' ':
for nextY in range(y+1, m+1):
if nextY == m or board[nextY][x] != ' ':
if nextY != (y+1):
board[nextY-1][x] = board[y][x]
board[y][x] = ' '
break
answer += changeCount
return answer- 택배상자
def solution(order):
length = len(order)
answer = 0
cIdx = 0 # 컨테이너 벨트의 인덱스. 인덱스의 택배가 가장 앞에있는 택배이다
oIdx = 0 # 오더 인덱스. 현재 적재할 주문의 인덱스이다.
auxCon = []
while True:
# 모두 적재 면 종료
if answer == length:
break
# 컨테이너 벨트가 비었고 보조 컨테이너 벨트의 맨 뒤 둘다 원하는 박스가 아니라면 종료
if cIdx == length and (auxCon[-1] != order[oIdx]):
break
# 원하는 박스가 컨테이너 벨트의 맨 앞상자(cIdx+1)라면 택배적재
if order[oIdx] == (cIdx + 1):
answer += 1 # 적재된 택배개수 증가
cIdx += 1 # 컨테이너 벨트 인덱스 증가
oIdx += 1
# 원하는 박스가 컨테이너 벨트의 맨 앞상자가 아니라면
else:
# 원하는 박스가 보조 컨테이너 벨트의 맨 뒤라면 택배적재
if len(auxCon) > 0:
if auxCon[-1] == order[oIdx]:
del auxCon[-1]
answer += 1
oIdx += 1
# 원하는 박스가 보조 컨테이너에도 없다면 보토 컨테이너에 옮김
else:
auxCon.append(cIdx+1)
cIdx += 1
# 원하는 박스가 보조 컨테이너에도 없다면 보토 컨테이너에 옮김
else:
auxCon.append(cIdx+1)
cIdx += 1
return answer- 숫자 변환하기
def solution(x, y, n):
from collections import deque
minC = -1
nums = set() # 만들어진 숫자들
deq = deque()
deq.append([x, 0])
nums.add(x)
while deq:
[num, count] = deq.popleft()
if num == y:
minC = count
break
elif num < y:
# 전에 호출된 숫자라면 같은 count거나 더 작은 count를 가졌을 것이다.
if (num + n) not in nums:
deq.append([num + n, count+1])
nums.add(num+n)
if (num * 2) not in nums:
deq.append([num * 2, count+1])
nums.add(num*2)
if (num * 3) not in nums:
deq.append([num * 3, count+1])
nums.add(num*3)
return minC- 2 x n 타일링
왜 피보나치 수열인지 모르겠으나, 피보나치였다...
def solution(n):
arr = [1, 1, 2, 3, 5, 8, 13]
if n <= 6:
return arr[n]
i = 7
while i <= n:
arr.append((arr[i-1]+arr[i-2])%1000000007)
i += 1
return arr[n]- 가장 큰 수
처음 한 코드이다. bfs + dp로 풀었는데 15문제중 7문제가 시간초과 났다.
# bfs + dp
def insertToDeque(deq, n):
# deq을 오른쪽부터 비교해서 작은 값들은 없애줌
while True:
# deq이 비었으면 그냥 추가
if len(deq) == 0:
deq.append(n)
break
ele = deq[-1]
digitLen = min(len(ele['s']), len(n['s']))
# deq의 오른쪽이 추가하는 값보다 작다면 pop
if ele['s'][:digitLen] < n['s'][:digitLen]:
deq.pop()
# 같으면 추가
elif ele['s'][:digitLen] == n['s'][:digitLen]:
deq.append(n)
break
# 추가하는 값이 더 작으면 더하지 않음
else:
break
def solution(numbers):
from collections import deque
allIdxSet = set(range(len(numbers)))
deq = deque()
numbers = list(map(str, numbers))
numbers.sort(reverse=True)
# 앞자리수가 가장 큰것
firstMax = numbers[0][0]
deq.append({'s':numbers[0], 'added':set([0])})
# 최대값이 될 수 있는것들을 더해줌
for i in range(1, len(numbers)):
if numbers[i][0] != firstMax:
break
insertToDeque(deq, {'s':numbers[i], 'added':set([i])})
# bfs로 최대값 탐색. 같은 자리수에서
while len(deq):
el = deq.popleft()
# 안더한것들을 더해주며 deq에 추가한다.
for idx in list(allIdxSet - el['added']):
insertToDeque(deq, {'s':el['s'] + numbers[idx], 'added':el['added'].union(set([idx]))})
if len(deq) == 1:
if len(deq[0]['added']) == len(numbers):
break
return deq[0]['s']질문하기 세션을 본 후 정답.
절대적인 우선순위를 주지 않고, cmp_to_key를 사용하면 js처럼 상대적인 우선순위를 계산하는 방법을 사용할 수 있다.
def compare(x, y):
return int(y + x) - int(x + y)
def solution(numbers):
from functools import cmp_to_key
numbers = list(map(str, numbers))
numbers.sort(key=cmp_to_key(compare))
return str(int(''.join(numbers)))- 다리를 지나는 트럭
def solution(bridge_length, weight, truck_weights):
from collections import deque
truckCount = len(truck_weights)
deq = deque() # 다리를 건너는 트럭 [truckWeight, distance]를 원소로 가짐
waitIdx = 0
time = 0
while True:
# 다리를 건너는 트럭도 없고 대기 트럭도 없다면 끝
if waitIdx == truckCount and len(deq) == 0:
break
# deq에 트럭이 있으면 거리를 하나씩 늘림. 맨앞트럭은 최대거리라면 끝낸다
if len(deq) > 0 and deq[0][1] >= bridge_length:
deq.popleft()
weightSum = 0
for i in range(0, len(deq)):
[truckW, dis] = deq.popleft()
weightSum += truckW
deq.append([truckW, dis+1])
# 다리건너는트럭 + 다음트럭이 최대무게를 초과하지 않는다면 다음트럭 다리에 추가
if waitIdx < truckCount and weightSum + truck_weights[waitIdx] <= weight:
deq.append([truck_weights[waitIdx], 1])
waitIdx += 1
time += 1
#print(time, deq)
return time- 소수 찾기
def isPrime(num):
import math
if num < 2:
return False
elif num == 2:
return True
if num % 2 == 0:
return False
for i in range(3, int(math.sqrt(num))+1, 2):
if num % i == 0:
return False
return True
def solution(numbers):
import itertools
answer = 0
numSet = set()
for r in range(1, len(numbers)+1):
nPr = list(itertools.permutations(numbers, r))
for x in range(0, len(nPr)):
numSet.add(int(''.join(nPr[x])))
numSet = list(numSet)
for x in range(0, len(numSet)):
if isPrime(numSet[x]):
answer += 1
return answer- 쿼드압축 후 개수 세기
def solution(arr):
zero = 0
one = 0
length = len(arr)
for y in range(length):
for x in range(length):
if arr[y][x]:
one += 1
else:
zero += 1
# 2개 4개 8개씩 묶으며 중복을 줄인다.
# 0은 하위것들까지 모두 0, 1은 하위것들까지 모두 1, 2는 섞였다는 뜻
# 4개씩 조합하여 모두 0이거나 1이면 0 또는 1, 아니면 2가 된다. 이때 0이거나 1이면 3개씩 빼면 된다.
n = 2
while n <= length:
for y in range(0, length, n):
for x in range(0, length, n):
if arr[y][x] == arr[y+n//2][x] == arr[y][x+n//2] == arr[y+n//2][x+n//2]:
if arr[y][x] == 1:
one -= 3
elif arr[y][x] == 0:
zero -= 3
else:
arr[y][x] = 2
n = n * 2
return [zero, one]- 두 큐 합 같게 만들기
def solution(queue1, queue2):
answer = 0
length = len(queue1)
sum1 = sum(queue1)
sum2 = sum(queue2)
q1Idx = 0
q2Idx = 0
while True:
# 만들 수 없는 경우는 둘중 하나가 빈 큐가 된다. 또는 길이 3배가 넘었는데 안끝나면 만들수 없다.
if q1Idx == len(queue1) or q2Idx == len(queue2) or answer > length*3:
return -1
# 양쪽 sum이 똑같다면 정답
if sum1 == sum2:
break
# sum1이 크다면 queue1에서 하나를 빼서 queue2에 더함
elif sum1 > sum2:
num = queue1[q1Idx]
sum1 -= num
sum2 += num
q1Idx += 1
queue2.append(num)
answer += 1
elif sum1 < sum2:
num = queue2[q2Idx]
sum1 += num
sum2 -= num
q2Idx += 1
queue1.append(num)
answer += 1
return answer- 삼각 달팽이
def solution(n):
arr = [0 for i in range(n*(n+1)//2)]
num = 1
count = 0 # 겉에서부터 몇번째 칸에 떨어진 삼각형을 그리는건지
nextN = n
while nextN > 0:
# 꼭대기에서 왼쪽 아래로
for i in range(nextN):
#arr[i*(i+1)//2] = num
arr[(count*2+i)*(count*2+i+1)//2+count] = num
num += 1
# 왼쪽 아래에서 오른쪽 아래로
for i in range(1, nextN):
#arr[nextN*(nextN-1)//2 + i] = num
arr[(n-count-1)*(n-count)//2 + i + count] = num
num += 1
# 오른쪽 아래에서 꼭대기로
for i in range(1, nextN-1):
idx = nextN - i - 1
#arr[idx*(idx+1)//2+idx] = num
arr[(count*2+idx)*(count*2+idx+1)//2+idx+count] = num
num += 1
nextN -= 3
count += 1
# for i in range(1, n+1):
# print(arr[i*(i-1)//2:i*(i-1)//2+i])
return arr- 큰 수 만들기
def solution(number, k):
stack = []
for i in range(len(number)):
while k > 0 and stack:
if stack[-1] < number[i]:
stack.pop()
k -= 1
else:
break
stack.append(number[i])
for i in range(k):
stack.pop()
return ''.join(stack)- 연속된 부분 수열의 합
def solution(sequence, k):
end = len(sequence) - 1
start = end
total = sequence[-1]
# 뒤에서부터 더하고 빼고 함. k가 될때까지
while total != k:
if total < k:
start -= 1
total += sequence[start]
elif total > k:
total -= sequence[end]
end -= 1
# start-1과 end가 같다면 1씩 빼줌
while start > 0:
if sequence[start-1] == sequence[end]:
start -= 1
end -= 1
else:
break
return [start, end]- 124 나라의 숫자
def solution(n):
# 1의자리수는 숫자가 3개지만, 자리수가 커질수록 숫자 개수도 3배가 된다.
# 등비수열 합공식을 사용해 f(n)=3*(3^n-1)/2를 이용한다.
# f(15) = 21,523,359
answer = ''
f = lambda x:int(3*(3**x-1)/2)
# i는 자리수를 의미한다
for i in range(1, 17):
if f(i-1) < n:
answer += "124"[int((n-1-f(i-1))/(3**(i-1)))%3]
continue
else:
break
return answer[::-1]질문하기 세션에서 간략화된 버전
def solution(n):
answer = ''
while n > 0:
n -= 1
answer = '124'[n%3] + answer
n //= 3
return answer