Algorithm/Problem Solving

문제 이해 나는 처음에 이 문제가 뭔 소릴 하는 건지.. 도통 이해가 안 됐다 😥 근데 나같은 사람이 많았던 건지 이 문제에는 힌트가 있다. 요 힌트를 한 번 따라가보도록 하자. 스택에 push하는 순서는 반드시 오름차순을 지킨다고 한다. 그렇다면 순서가 이렇게 되는 것이다!! 먼저 4까지 냅다 쌓는다. 쌓고나서 pop을 한다. 그러면 1, 2, 3만 남아있다. 수열의 다음수가 3이고 스택의 맨 위에 있는 요소가 3이므로 그냥 pop을 해준다. 그 다음수는 6이기때문에 5, 6을 push해준다. 쌓고나서 다시 수를 비교해가면서 pop을 한다. 이때, 만약 1, 2, 3, 4가 쌓여있는 상태에서 2를 꺼내려고 하면 후입선출인 스택의 원리에 따라 수열을 출력할 수 없으므로 NO를 출력하면 된다. (혹시 스택..

✔ 문제 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. ✔ 입력 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) ✔ 출력 좋은 수의 개수를 첫 번째 줄에 출력한다. ✔ 입출력 예제 > 10 > 1 2 3 4 5 6 7 8 9 10 8 ✔ 시간 제한 이 문제의 시간 제한은 2초입니다. N개의 숫자 각각이 좋은 수인지 확인해야하므로 기본적으로 시간 복잡도가 O(N)이기 때문에 좋은 수 확인 알고리즘은 시간 복..

✔ 문제 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000)개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오. ✔ 입력 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 1..

문제 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라 입출력 예 풀이 1 : 이중 for문 문제를 처음 봤을 때 딱 생각나는 가장 간단하고 쉬운 방법은 이중for문을 돌리는 것이다. class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + nums[j] == target: return [i, j] 이 경우, 시간 복잡도는 O(n^2). 풀이 2 : enumerate, in 이용 이 문제를 풀면서 처음 enumerate에 대해 알게되었다. enumerate는 인덱스와 원소의 쌍을 돌려..

문제 금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며, 구두점(마침표, 쉼표) 또한 무시한다. 입출력 예 입력 paragraph = "Bob hit a ball, the hit BALL flew far after it was hit." banned = ["hit"] 출력 >> "ball" 풀이 re.sub(패턴(정규식), 바꿀 문자열, 문자열, 바꿀 횟수) 바꿀 횟수가 생략이면 찾은 문자열을 모두 치환 정규식에서 ^는 not, \w는 단어 문자를 뜻함. 따라서 re.sub(r'[^\w]', ' ', paragraph) 위의 코드는 단어 문자가 아닌 모든 문자를 공백으로 치환하는 것을 말한다. 문자가 아닌 것을 모두 공백으로 치환한 뒤에는, 공백을 기준으로 spli..

문제 로그를 재정렬하라. 기준은 다음과 같다. 1. 로그의 가장 앞 부분은 식별자다. 2. 문자로 구성된 로그가 숫자 로그보다 앞에 온다. 3. 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순으로 한다. 4. 숫자 로그는 입력 순서대로 한다. 입출력 예시 입력 logs = ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"] 출력 >> ['let1 art can', 'let3 art zero', 'let2 own kit dig', 'dig1 8 1 5 1', 'dig2 3 6'] 풀이 문자로 구성된 로그가 숫자로 구성된 로그보다 앞에 온다. 숫자로 구성된 로그는 입력 순서대로 둬야한다. 이 ..

문제 주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다. 팰린드롬이란 앞뒤가 똑같은 단어나 문장을 말한다. 입출력 예제 1. 입력 "A man, a plan, a canal: Panama" 출력 >> True 2. 입력 "race a car" 출력 >> False 풀이 이 문제에서는 눈에 띄는 조건이 두 개 있다. 1. 대소문자를 구분하지 않는다. 2. 영문자와 숫자만을 대상으로 한다. 예를 들어 입력 예제1에서 공백을 포함한 모든 특수문자를 제거한 상태에서, 소문자형태인 amanaplanacanalpanama를 거꾸로 뒤집은 것과 비교를 해야할 것이다. (대문자로 바꾸어 해도 상관 없다.) 내 풀이는 다음과 같다. 입력받은 문자열을 s라고 할 때, s에..

문제 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 순위당첨 내용 1 6개 번호가 모두 일치 2 5개 번호가 일치 3 4개 번호가 일치 4 3개 번호가 일치 5 2개 번호가 일치 6(낙첨) 그 외 로또를 구매한 민우는 당첨 번호 발표일을 학수고대하고 있었습니다. 하지만, 민우의 동생이 로또에 낙서를 하여, 일부 번호를 알아볼 수 없게 되었습니다. 당첨 번호 발표 후, 민우는 자신이 구매했던 로또로 당첨이 가능했던 최고 순위와 최저 순위를 알아보고 싶어 졌습니다. 알아볼 수 없는 번호를 0으로 표기하기로 하고, 민우가 구매한 로또 번호 6개가 44, 1, 0, 0, 31 25라고 가정해보겠습니다. 당첨 ..