[파이썬 알고리즘 인터뷰] 코딩테스트 문제풀이

팰린드롬이란 앞으로 읽어도 뒤로 읽어도 같은 문자의 순서가 되는 단어 또는 문장이다. 우리말로는 '회문'이라고 하며 대표적인 문장으로는 '소주 만 병만 주소'와 같은 문장이 이에 해당된다. 지금 사용할 펠린드롬은 "A man, a plan, a canal: Panama

문자열을 반대로 하는 함수를 작성합니다. 입력 문자열은 문자 배열로 제공됩니다. 단 리턴없이 리스트 내부를 스스로 조작해야한다.예 1:Input: s = "h","e","l","l","o"Output: "o","l","l","e","h"예 2:Input: s = "H"

배열이 제공됩니다. 각 로그는 첫 번째 단어가 식별자인공간 구분된 단어 문자열입니다.로그의 두 가지 유형이 있습니다.문자 로그: 모든 단어 (식별자를 제외한)는 소문자 영어 문자로 구성됩니다.숫자 로그: 식별자를 제외한 모든 단어는 숫자로 구성됩니다.다음 로그를 다시

금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며 구두점 또한 무시한다.입력: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = "hit

문자열의 배열을 받아, anagrams를 그룹화하라.Anagram은 일반적으로 모든 원본 문자를 정확히 한 번 사용하여 다른 단어 나 구의 문자를 재배열하여 형성 된 단어 또는 문구입니다.예 1:Input: strs = "eat","tea","tan","ate","na

가장 긴 팰린드롬 부분 문자열을 출력하라.예 1:Input: s = "babad"Output: "bab"Note: "aba" 또한 정답이다. expand라는 함수를 만든다. 조건으로는 left가 0보다 크고 right는 문자열보다 작다. 그리고 sleft와 sright

Your input 2,7,11,15target: 9Expected 0,1브루트포스: 모든 조합을 더해서 일일이 확인하는 무차별 대입 방식2+7, 2+11, 2+15와 같이 마지막 요소들까지 모두 차례대로 비교해 가며 타겟값이 나올때 까지 반복한다.이 경우 풀이 시간

문제의 그림에서는 최대 높이가 3이다. 높이가 더 높아도 상관은 없지만 최대 높이까지 각각 좌우 기둥을 최대높이 left_max, right_max가 현재 높이와의 차이만큼 물높이 volume을 더해나간다.낮은 쪽은 항상 물이 채워질 것이고 좌,우 끝에서 가장 높은 기

배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라.편의를 위해 먼저 정렬을 해서 조금이라도 문제를 간소화 시킨다. 그리고 각각의 3포인터가 이동을 하면서 0인 값을 찾아내는데 중복된 값은 건너뛰어야 하기 때문에 3포인터에 중복된 값은 건너 뛰는 fo

배열중 2개의 min(a,b)를 만들어 합이 제일 큰 수를 출력하라.1,4,3,2의 배열이 있고 이중 2개씩 뽑아 min(a1,b1) min(a2,b2)를 만들어 나온 두 수의 합이 제일 큰 수를 출력하라라는 문제이다.문제를 처음 보고 생각했을 때는 복잡한 문제로 보였

배열을 입력받아 outputi가 자신을 제외한 모든 요소의 곱셉 결과가 되도록 출력하라.단, 복잡도는 O(n)이고 나눗셈은 사용하면 안된다.나눗셈을 하지 말라고 한 이유는 미리 주어진 값들을 모두 곱하고 각각 자신을 나눠서 풀이하면 바로 답이 나오기 때문에 그런 것이

한번의 거래로 낼 수 있는 최대의 이익을 계산하라.기대값이 5인 이유는 1일 때 사서 6에 팔면 5의 이익이 가장 크기 때문이다.가장 간단한 방법은 브루트 포스로 사고 팔고를 반복하여 최대의 이익을 내는 값을 뽑아 내면 되는 방식이다.하지만 이방식은 타임아웃으로 풀리지

연결 리스트가 팰린드롬 구조인지 판별하라.리스트 변환가장 간단한 방법은 리스트로 변환하여 pop()을 사용하는 것이다.q.pop(0) != q.pop():로 팰린드롬인지 검사하고 빠져나올 수 있다.데크를 이용한 최적화if q.pop(0) != q.pop():를 사용하여

정렬되어 있는 두 연결 리스트를 합쳐라책의 문제 설명이랑 영상을 한참 보고도 90%는 이해했는데 혼자 다시 해보면 또 헷갈렸던 문제다. 코드는 무척이나 간단한데 그 안에서 일어나는 스왑이 많이 헷갈렸다.근데 다른 인터넷 설명 찾아보니 되게 간단하게 나왔던...우선 코드

연결리스트를 뒤집어라다음 노트 next와 현재 노드를 계속해서 재귀 호출하면서 node가 none이 될때 까지 반복하면서 마지막에는 연결리스트가 거꾸로 연결된다.1번과 똑같이 next.node를 prev리스트로 계속 연결하면서 끝날 때 까지 반복한다.둘다 시간은 크게

문제: 역순으로 저장된 연결리스트의 숫자를 더하라.간단하게 생각한 방법은 연결리스트를 문자열로 이어서 숫자로 변환하고 덧셈을 한 뒤에 다시 연결리스트로 바꾸는 방법인데 문제 의도가 이런 변환 후 또 변환하는 방법은 의도 한 것은 아닐 것 같지만 일단 따라해 봤다.15번

문제: 연결리스트를 입력받아 페어 단위로 스왑하라.간단하게 노드 구조는 그대로고 값만 변경하는 방법이다. 하지만 이 방법은 실용성이 떨어진다고 한다. 연결리스트들은 보통 복잡한 여러가지의 값들의 구조체로 되어 있고 거기서 값만 바꾸는 것은 어렵기 때문(?)이라고 한다.

문제: 홀수 노드 다음에 짝수 노드가 오도록 재구성하기, 조건: 공간복잡도 O(1), 시간 복잡도O(n)책에는 쉽게 풀 수 있을 것 같은 문제지만 이라는데... 난 전혀 쉬워보지이 않는데... 나만 그런 것인가...? 우선 코드부터 보자.코드를 보고 설명을 보니 딱 와

문제: 괄호로 된 입력값이 올바른지 판결하라(같은 괄호들로 열고 닫히는지 검사하는 문제)(,,{는 스택에 push하고 ),,}를 만날 때 스택에서 pop한 결과가 매핑테이블 결과와 매칭이 되는지 확인을 해서 존재하지 않으면 푸시하고 팝했을 때 일치하지 않으면 false

문제: 중복된 문자를 제외하고 사전식 순서로 나열하라 1. 재귀를 이용한 분리 사전식으로 순서를 나열한다는 뜻이 중복을 제거하고 남은 알파벳들을 순서대로 바꿔 사전식으로 나타낸다는 것이 아니다. 자리의 위치는 바꿀 수 없다.

매일화씨 온도 리스트 T를 입력받아 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지 출력하라.73도에서 하루만 기다리면 74, 74에서 하루 기다리면 75, 75에서 4일 기다려야 76, 71에서 2일 기다려야 72 ... ... 으로 진행된다.빗물 트래킹저럼 이

큐를 이용해 다음 연산을 지원하는 스택을 구현하라.push(x): 요소 x를 스택에 삽입한다.pop(): 스택의 첫 번째 요소를 삭제한다.top(): 스택의 첫 번째 요소를 가져온다.empty(): 스택이 비어있는지 여부를 리턴한다.MyStack stack = new

두 개의 스택만 사용하여 첫 번째 아웃(FIFO) 큐에서 첫 번째 대기열을 구현합니다. 클래스 구현:MyQueuevoid push(int x) 요소 x를 큐 뒤쪽으로 푸시합니다.int pop() 큐 의 전면에서 요소를 제거하고 반환합니다.int peek() 큐 의 전면