Algorithm/프로그래머스

[프로그래머스] 43164. 여행경로

풀이 1 deq에 넣어가며 하나씩 빼면서.. from collections import deque def solution(tickets): ticketDeq = deque(tickets) deq = deque(["ICN"]) answer = ["ICN"] while ticketDeq: start = deq.popleft() for s, f in ticketDeq: if s == start: deq.append(f) mini = min(deq) deq.clear() ticketDeq.remove([start, mini]) deq.append(mini) answer.append(mini) return answer 풀이 틀림. 풀이 2 조심해야 할 점이 있었습니다. 중복된(같은 이름의) 티켓이 여러 장 들어갈..

[프로그래머스] 42898. 등굣길

풀이 1 보자마자 생각나는 것.. 확통에서 풀던 최단거리 경우의 수 문제 (같은 것이 있는 순열) 그 방식대로 풀이해보자 from math import factorial def solution(m, n, puddles): def shortcut(m, n): return int(factorial(m+n) / (factorial(m) * factorial(n))) answer = shortcut(m-1, n-1) for li in puddles: answer -= shortcut(m - li[0], n - li[1]) * shortcut(li[0]-1, li[1]-1) return answer 이러면 문제가.. puddles의 개수가 2개를 넘어가면 두 웅덩이를 모두 지나는 경우의 수를 여러 번 빼 주게 되..

[프로그래머스] 43163. 단어 변환

Programmers - 43163. 단어 변환 접근 BFS로 구현. 한 스텝마다, deq에 있는 단어들에서 변경할 수 있는 단어 목록을 뽑아와 저장. 그리고 그 목록을 다시 다음 스텝에 deq에서 하나씩 뽑아와서 반복. from collections import deque def solution(begin, target, words): def canChange(fromWord, toWord): difChar = 0 for i in range(len(fromWord)): if fromWord[i] == toWord[i]: continue else: difChar += 1 if difChar == 1: return True else: return False if target not in words: ret..

[프로그래머스] 43105. 정수 삼각형

Programmers - 43105. 정수 삼각형 접근1 Bottom-Up 방식 사용. 삼각형의 높이만큼 반복 돌리면서 리스트에 저장해나가며 밑으로 한 층씩 내려가면 될 듯? 맨 위를 1층이라고 하면 [[{1층-0번}], [{2층-0번}, {2층-1번}], [{3층-0번}, {3층-1번}, {3층-2번}]] {n층-n번} 에는 그 지점까지 도달할 수 있는 모든 경우의 수를 집합(set)으로저장. [[{7}], [{10}, {15}], [{18}, {16, 11}, {15}], [{20}, {25, 18, 23}, {19, 20, 15}, {19}]] 와 같은 느낌으로. def solution(triangle): dp = [[set([triangle[0][0]])]] for F in range(1, len..

[프로그래머스] 42895. N으로 표현

Programmers - 42895. N으로 표현 접근 일단, N을 1번 사용했을 때 ~ 8번 사용했을 때를 모두 순회하며 확인하면 될 것 같음. 일단 N = 3으로 예시를 들어서 한번 생각해 보자. N을 1번 사용했을 때 {3} N을 2번 사용했을 때 {33}, {3+3, 3-3, 3/3, 3*3} => {33, 6, 0, 1, 9} N을 3번 사용했을 때 여기부터 이제 사칙연산에 어떤 수를 사용하느냐에 따라 갈리는데 3, 3, 3을 사용 3+3과 3을 사용 3-3과 3을 사용 3/3과 3을 사용 3*3과 3을 사용 33, 3을 사용 33*3, 33-3, 33+3, 33/3, 3*33, 3-33, 3+33, 3/33 결국 N을 3번 사용할 때의 결과값은 N을 1번 사용했을 때 (+, -, *, /) N..

[프로그래머스] 42587. 프린터

프로그래머스 - 42587. 프린터 접근 그냥 데크에 넣고 priority가 최댓값인 놈을 만날때까지 돌리고 돌리다가 만나면 pop하고 횟수세고 끝. from collections import deque def solution(priorities, location): # target location 표시 prior = [[i, 0] for i in priorities] prior[location][1] = 1 deq = deque(prior) answer = 0 while True: if deq[0][0] == max(deq, key=lambda x: x[0])[0]: if deq[0][1] == 1: return answer + 1 else: deq.popleft() answer += 1 else: d..

[프로그래머스] 42586. 기능개발

Programmers - 42586. 기능개발 접근 그냥.. 큐에 넣고 한 턴에 한번씩 모든 index의 값 speed만큼 증가시키면서 0번 index가 100 이상이 되었을 때 한번에 몇 개 빼는지 기록. 간단쓰 from collections import deque def solution(progresses, speeds): deq = deque(progresses) deq_speed = deque(speeds) answer = [] while len(deq) != 0: for i in range(len(deq)): deq[i] += deq_speed[i] cnt = 0 while len(deq) > 0 and deq[0] >= 100: deq.popleft() deq_speed.popleft() cn..

[프로그래머스] 42584. 주식가격

Programmers - 42584. 주식가격 접근1 맘같아선 싹 다 리스트에 박아버리고 for문 돌리고 싶다. 한번 해볼까 def solution(prices): answer = [0]*len(prices) for i in range(len(prices)): for j in range(i): if answer[j] == 0: if prices[j] > prices[i]: answer[j] = i-j for i in range(len(answer) - 1): if answer[i] == 0: answer[i] = len(answer) - 1 - i return answer 네 당연히 잘 돌아가구요 존나 오래 걸립니다 접근2 from collections import deque def solution(pr..