[LeetCode] Word Search
문제링크 문제 설명 Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters o...
[LeetCode] Longest Palindromic Substring
문제 설명
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Example 3:
Input: s = "a"
Output: "a"
Example 4:
Input: s = "ac"
Output: "a"
Constraints:
1 <= s.length <= 1000sconsist of only digits and English letters (lower-case and/or upper-case),
Sol
옛날옛날 학부 1학년 처음 들었던 C언어 전공수업에서 처음으로 챌린징(?) 했던 녀석이 바로 이 Palindrome 이었던 기억이 납니다. 그리고 시간이 흘러 알고리즘 인터뷰를 준비하거나, 코테를 준비하면서도 잊을만할때 찾아오는 주제이기도 하네요. ㅎㅎ 다행인 건 이제는 어렵다는 느낌보단 반갑다는 느낌이 들 정도로 미운정이 들었나 봅니다 : )
이 문제에서는 먼저, 입력된 s가 1글자로 이루어져 있을 경우, 바로 s를 반환시켜 버렸습니다.
이제 Palindrome이 짝수의 길이로 생성될 수도 있고, 홀수의 길이로 생성될 수도 있기 때문에,
경우의 수를 나누어 풀이를 진행했습니다.
물론, 짝수인 경우와 홀수인 경우를 확인하여 결국 가장 긴 palindrome을 answer로 반환합니다!
-
위와 같이, idx 위치를 기준으로, 짝수인경우엔 그냥 idx 전까지와 idx부터를 나누어 palindrome인지를 확인하면 됩니다.
-
홀수길이의 palindrome을 확인하고자 하면, idx 위치는 제외하고 양 옆을 분할하여 palindrome인지 여부를 확인하였습니다.
아래 코드를 통해 확인해 봅시다.
Code
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) == 1:
return s
s = list(s)
# 짝수
idx, n, answer = 1, 0, ''
while idx < len(s):
a, b = s[:idx], s[idx:]
a.reverse()
l = min(len(a), len(b))
tmp = ''
for i in range(l):
if a[i] != b[i]:
break
else:
tmp = a[i] + tmp + b[i]
if len(tmp) > n:
answer = tmp
n = len(answer)
idx += 1
# 홀수
idx = 1
while idx < len(s):
a, b = s[:idx], s[idx+1:]
a.reverse()
l = min(len(a), len(b))
tmp = s[idx]
for i in range(l):
if a[i] != b[i]:
break
else:
tmp = a[i] + tmp +b[i]
if len(tmp) > n:
answer = tmp
n = len(answer)
idx += 1
if answer == '':
return s[0]
return answer
2021
[LeetCode] Letter Combinations of a Phone Number
문제링크 문제 설명 Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answe...
[프로그래머스] 기지국 설치
문제링크 문제 설명 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기...
[백준] 괄호 제거
문제링크 괄호 제거 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 2016 680 ...
[LeetCode] Longest Palindromic Substring
문제링크 문제 설명 Given a string s, return the longest palindromic substring in s. Example 1: Input: s = "babad" Output: "bab" Note: "aba" is also a valid ans...
[프로그래머스] 거리두기 확인하기
문제링크 문제 설명 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 대기실은 5...
[프로그래머스] 불량 사용자
문제링크 문제 설명 개발팀 내에서 이벤트 개발을 담당하고 있는 “무지”는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자...
[프로그래머스] 보석쇼핑
문제링크
[프로그래머스] 문자열 압축
문제링크 문제 설명 데이터 처리 전문가가 되고 싶은 “어피치”는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되...
[LeetCode] Container With Most Water
문제링크 Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpo...
[LeetCode] Trapping Rain Water
문제링크 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Exam...
[LeetCode] Median of Two Sorted Arrays
문제링크 Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time c...
[LeetCode] First Missing Positive
문제링크 Given an unsorted integer array nums, find the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses co...
[백준] 나무 자르기
문제링크 나무 자르기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 72052 20773 ...
[프로그래머스] 광고삽입
문제링크 문제 설명 카카오TV에서 유명한 크리에이터로 활동 중인 죠르디는 환경 단체로부터 자신의 가장 인기있는 동영상에 지구온난화의 심각성을 알리기 위한 공익광고를 넣어 달라는 요청을 받았습니다. 평소에 환경 문제에 관심을 가지고 있던 “죠르디”는 요청을 받아들였고 광고효과...
[LeetCode] Climbing Stairs
문제링크 Easy You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you ...
[프로그래머스] 거스름돈
문제링크 문제 설명 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 ...
[LeetCode] Unique Paths
문제링크 A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any p...
[LeetCode] 3Sum
문제링크 Medium Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + ...