우노

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42883 풀이 문제에 따르면, 입력 numbers에 대해서 해당 문자열이 가장 큰 수를 만들게끔 k개를 빼야 합니다. 예제 입력을 살펴보겠습니다. numbers = "4177252841", k = 4 어떻게 가장 큰 수를 만들 수 있을까요? 먼저, 일단 숫자가 나오면 스택에 저장합니다. 그리고 그 숫자보다 큰 숫자가 나오면 스택에 저장했던 수를 빼보면 어떨까요? 자 시작해봅시다. 처음 숫자인 4를 넣습니다. stack = ["4"] ( k = 4 ) 그 후 1을 넣습니다. 1은 스택에 마지막으로 저장된 4보다 작기 때문에 뺄 필요가 없습니다. stack = ["4", "1"] ( k = 4..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42586 풀이 작업이 끝나기까지 남은 일수를 모두 큐에 넣은 뒤, 큐에서 요소들을 하나씩 빼며, 현재 요소가 이전에 뺏던 요소들 중에 가장 큰 값인지 확인합니다. 가장 큰 값이라면 새로운 배포 일정을 추가합니다. 가장 큰 값이 아니라면 마지막 배포 일정에 현재 기능의 개수를 추가합니다. 따라서, 큐가 [5, 10, 1, 1, 20, 1]로 이루어져있다면 결과로 [1, 3, 2]가 됩니다. 예외 케이스로, progresses [95, 94]와 speeds [3, 3]가 있습니다. 코드 from collections import deque def solution(progresses, speed..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42746 풀이 permutations 함수를 사용하면 시간초과가 발생합니다. 해당 문제의 핵심은, 숫자들을 문자열들로 변환한 뒤 내림차순 정렬했을 때, 3이 30보다 앞에 있어야한다는 것입니다. [’9’, ‘5’, ‘34’, ‘3’, ‘30’] 따라서, 각 문자열들을 3번 반복한 문자열들로 변환한 뒤, 내림차순 정렬합니다. [999, 555, 343434, 333, 303030] 각 문자열들을 3번 반복하는 이유는, numbers의 숫자들은 0 이상 1,000 이하로 이루어져있기 때문에, 각 문자열들을, 1000을 넘지 않는 가능한 최대 자리수까지 채워서 비교하기 위함입니다. 코드 def ..

문제 설명 여섯 가지 괄호 '(', ')', '{', '}', '[', ']'로 이루어진 문자열이 바르게 닫힌 문자열인지 알아보려 합니다. 바르게 닫힌 문자열이라는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로, '[' 문자로 열렸으면 반드시 짝지어서 ']' 문자로, '{' 문자로 열렸으면 반드시 짝지어서 '}' 문자로 닫히는 문자열입니다. 또한, 괄호 쌍 안에는 다른 괄호 쌍이 들어갈 수 있습니다. 예제 입력 및 출력은 아래와 같습니다. “{{}}” 또는 “({})[]” 는 바르게 닫힌 괄호입니다. “[)”, “]()[”..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=python3 문제 설명 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어, "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요. 제한사항 문자열 s의 길이 : 10..

문제 링크 https://www.acmicpc.net/problem/16719 풀이 정답을 출력할 배열을 만듭니다. 입력 문자열을 통해 아래 알고리즘을 진행합니다. 입력 문자열에서 가장 작은 알파벳을 선택합니다. 해당 알파벳을 정답 배열에 추가합니다. 정답 배열의 모든 알파벳들을 취합해 출력합니다. 해당 알파벳을 기준으로 뒷 문자열을 입력 문자열로 정해, 위 알고리즘을 반복합니다. 해당 알파벳을 기준으로 앞 문자열을 입력 문자열로 정해, 위 알고리즘을 반복합니다. 현재 알파벳을 기준으로 뒷 문자열부터 확인한 뒤, 앞 문자열을 확인하는 이유는, 현재 알파벳이 입력 문자열에서 가장 작은 알파벳이기 때문에, 현재 알파벳이 가장 앞에 와야 가장 작아지기 때문입니다. 세부 알고리즘은 아래 예제 코드와 같습니다. ..

문제 링크 https://www.acmicpc.net/problem/14719 풀이 투 포인터 알고리즘을 사용해 해결할 수 있으며, 세부 알고리즘은 아래 예제 코드를 읽으며 이해하시면 도움이 될 것 같습니다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) height = list(map(int, sys.stdin.readline().split())) # 가장 왼쪽 블록과 오른쪽 블록의 인덱스 저장 left, right = 0, len(height) - 1 # 가장 왼쪽 블록의 개수와 가장 오른쪽 블록의 개수로 초기화 left_max, right_max = height[left], height[right] # 고인 물의 개수 result = 0 ..

문제 링크 https://www.acmicpc.net/problem/2457 풀이 회의실 배정 문제의 변형판입니다. 먼저, 입력 날짜가 1월 1일이면 101, 12월 31일이면 1231처럼, 월에 100을 곱해줘서 일이랑 더해줍니다. 꽃이 피는 날짜, 꽃이 지는 날짜순으로 오름차순 정렬합니다. 정원의 마지막 꽃이 지는 날짜 end_date를 3월 1일로 초기화합니다. 모든 꽃들을 탐색합니다. 남아있는 꽃들 중, 꽃이 피는 날짜가 end_date 이전이며, 가장 느리게 지는 꽃을 찾습니다. 확인한 꽃들은 탐색 배열에서 제거합니다. 가장 꽃이 느리게 지는 날짜를 end_date로 수정합니다. 정원의 마지막 꽃이 지는 날짜가 12월 1일 이상이 됐거나, 현재 확인할 꽃의 시작 날짜가 정원의 마지막 꽃이 지는 ..

문제 링크 https://www.acmicpc.net/problem/1958 풀이 2차원 DP 테이블을 사용한 LCS 문제와 동일한 방식으로, 3차원 DP 테이블을 사용해서 해결할 수 있습니다. 기본적인 LCS 알고리즘은 해당 포스트에선 생략하겠습니다. 코드 작성은 쉬울 수 있으나, 시각적으로는 잘 그려지지 않는 것 같습니다. 코드 import sys # 각 문자열 입력 first = sys.stdin.readline().rstrip() second = sys.stdin.readline().rstrip() third = sys.stdin.readline().rstrip() # DP 테이블 초기화 dp = [[[0] * (len(third)+1) for _ in range(len(second)+1)] fo..

문제 링크 https://www.acmicpc.net/problem/2169 풀이 특정 좌표로 갈 수 있는 방법은 아래와 같습니다. 위에서 오는 것 왼쪽에서 오는 것 오른쪽에서 오는 것 5x5 샘플 데이터를 통해 좌표 값들을 업데이트해보겠습니다. 먼저, 첫 번째 행은, 왼쪽에서 오른쪽로 진행하는 경우 밖에 없으므로, 각 좌표까지의 최대 가치를 먼저 업데이트할 수 있습니다. 이제 나머지 행들을 순서대로 탐색하며 좌표값들을 업데이트해야합니다. 이때, 각 행들을 두 가지 임시 배열(왼쪽 → 오른쪽으로 진행 시 구해진 최댓값, 오른쪽 → 왼쪽으로 진행 시 구해진 최댓값)로 표현한 뒤, 두 임시 배열을 비교함으로써, DP 테이블의 각 좌표를 최대값으로 업데이트할 수 있습니다. 왼쪽 → 오른쪽으로 진행될 경우, 임..