본문 바로가기

코딩테스트 문제풀이83

[LeetCode] 1. Two Sum LeetCode1. Two SumArray Hash Map 기술 인터뷰에서도 자주 다루는 유형이다.처음에는 가볍게 풀었지만 Beats38.07%가 나와서 다른 방식으로 풀어 Beats100.00%를 만들 수 있었다.    Problem 문제는 정수가 담긴 1차원 리스트가 주어졌을 때,리스트안의 두 수의 합이 target의 값과 동일할 때 해당 값들의 인덱스를 리스트형식으로 반환하라는 내용이다. 부가적으로 O(n2)의 시간복잡도보다 더 효율적으로 짜보라는 코멘트가 있다.   Approach일반적으로 두 가지 방식이 있다. 1. 2중 반복문을 사용하여 브루트포스 형식으로 모든 경우의 수를 구하는 경우2. hashmap을 사용하여 보수를 이용하여 구하는 경우 1번의 경우 O(n2)의 시간복잡도를 가지게 되어서.. 2024. 11. 7.
[LeetCode] 7. Reverse Integer LeetCode 7번 Reverse Integer String 문제 정수를 뒤집는 문제 과정 정수를 문자열로 변환후 뒤집기 마지막 값이 -이면 (음수이면) 맨 앞으로 바꿔줌 정수의 범위 체크 후 넘어가면 0 리턴 소스코드 class Solution: def reverse(self, x: int) -> int: data = str(x)[::-1] if data[-1] == "-": data = "-" + data[:-1] if int(data) 2**31 - 1: return 0 return int(data) 통과 // 2023-07-31 스터디 과제 2023. 8. 8.
[LeetCode] 6. Zigzag Conversion LeetCode 6번 Zigzag Conversion String 문제 문자열 s가 주어졌을 때, 이를 지그재그 방향으로 나열한 문자열을 출력하는 문제 과정 문자열 방향을 정할 변수(direct)와 인덱스 값을 설정할 변수(cnt)가 필요하다. 문자열 s를 순회하면서 인덱스가 마지막이거나 처음일 경우에 방향을 바꿔준다. 방향에 따라 정방향이면 인덱스에 +1, 역방향이면 인덱스에 -1을 해준다. numRows만큼 선언해둔 2차원 배열(data)에 값을 저장하고 이를 문자열로 붙여서 출력해주면 된다. 소스코드 class Solution: def convert(self, s: str, numRows: int) -> str: answer = "" data = [[] for _ in range(numRows)] .. 2023. 8. 8.
[LeetCode] 5. Longest Palindromic Substring LeetCode 5번 Longest Palindromic Substring String, DP, 확장 문제 유명한 팰린드롬 문제 팰린드롬(palindrome)이란? 'aba', 'eye' 처럼 거꾸로 읽어도 똑같은 문장이나 단어를 뜻한다. 과정 주어진 문자열s를 특정 기준에 따라 분리하고 별도로 팰린드롬인지 판별하는 함수를 만들어 분리된 문자열이 팰린드롬인지 체크하였다. 1. check_palindrome() 함수 해당 문자열이 팰린드롬이지 판별하는 함수이다. 1-1) 매개변수로 잘려진 문자열s가 들어오는 경우 def check_palindromic(s): mid = len(s) // 2 if len(s) % 2 == 0: # 짝수 reversed_s = reversed(list(s[mid:])) rev.. 2023. 7. 31.
[LeetCode] 3. Longest Substring Without Repeating Characters LeetCode 3번 Longest Substring Without Repeating Characters string 문제 이 문제는 반복되는 알파벳이 나오지 않는 가장 큰 문자열을 반환하는 문제이다. 코테에서 보통 1번에 나오는 문자열관련 문제들과 유사했다. 과정 1) 처음에는 모든 경우를 구하기 위해서 2중 반복문을 사용했었다. # case 986) Time Limit Exceeded Error!! class Solution: def lengthOfLongestSubstring(self, s: str) -> int: answer = 0 for i in range(len(s)): num = [] cnt = 0 for j in range(i,len(s)): if s[j] in num: num = [s[j.. 2023. 7. 31.
[LeetCode] 2. Add Two Numbers LeetCode 2번 Add Two Numbers math, LinkedList 문제 반대의 값이 저장된 두 개의 LinkedList가 주어지고 원래 두 정수의 합을 다시 LinkedList로 반환하는 문제이다. 1번 예제를 보면 342 + 564 = 807이고 이를 역순한 708이 답이다. 오랜만에 보는 LinkedList 문제였다. 3번 예제 같은 경우엔 9999999 + 0009999 = 10009998 이 되고 이를 역순한 89990001이 답이 되는 것 제약사항은 다음과 같다. 과정 처음에 문제를 읽어봤을 때 무슨 소리인지.. 여러번 봤는데 이해하고 나면 단순한 문제임을 알 수 있다. 합산을 하는 과정은 주어진 LinkedList인 l1과 l2를 처음부터 차례대로 더하면 된다. 왜냐하면 어차피 .. 2023. 7. 31.
[백준] 1453 1로 만들기 백준 1453번 1로 만들기 DP [문제] 기본적인 DP(동적계획법) 문제 오랜만에 풀게되서 dp를 생각하지 못했고 dp개념을 다시 공부한 후 풀었다. 핵심은 1,2,3번으로 나온 연산의 최소횟수를 구하는 것 [과정] dp - BottomUp 풀이 / for문 사용 다른 하나는 재귀를 사용하는 TopDown 풀이가 있는데 이 문제에서는 BottomUp풀이를 사용했다. n에 변수 입력받기 dp배열을 0이 (x+1)개 있는 리스트로 초기화 dp[1]은 0이고 1이 1로 되는데 필요한 연산은 0회라는 뜻 즉, 이후에 dp[2]는 2가 1이 되는데 필요한 최소 연산 횟수인 1이 될 것 2부터 n+1까지 반복 dp[i]=dp[i-1]+1 : d[i]는 숫자 i가 1이 되는데 걸리는 최소한의 연산 횟수를 저장 i에.. 2023. 5. 12.
[프로그래머스] k진수에서 소수 개수 구하기 프로그래머스 2022 KAKAO BLIND RECRUITMENT k진수에서 소수 개수 구하기 구현 ※ 카카오 공식 해설 https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/ 2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설 지난 2021년 9월 11일 토요일 오후 2시부터 7시까지 5시간 동안 2022 KAKAO BLIND RECRUITMENT 1차 코딩 테스트가 진행되었습니다. 테스트에는 총 7개의 문제가 출제되었으며, 개발 언어는 C++, Java, JavaScript, K tech.kakao.com [문제] 10진수를 k진수로 변환하고 그 안에서 소수의 개수를 구하는 문제 제한사항에서 n의 .. 2023. 5. 9.
반응형

티스토리툴바