가장 긴 팰린드롬 (2중 for문 인덱스, 투포인터, 문자열 길이)

2023. 8. 3. 18:15·Coding Test/programmers
728x90

https://school.programmers.co.kr/learn/courses/30/lessons/12904

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

풀이

1. 2중 for문 완전 탐색

Time: 3926.56 ms

def solution(s):
    answer = 0
    
    for i in range(len(s)):
        for j in range(i+1,len(s)+1):
            if s[i:j]==s[i:j][::-1]:
                answer=max(answer, len(s[i:j]))

    return answer
"abacde"

a
ab
aba
abac
abacd
abacde
b
ba
bac
bacd
bacde
a
ac
acd
acde
c
cd
cde
d
de
e

 

2. 투포인터 홀수, 짝수 길이 나눠서

Time: 238.34 ms

def solution(s):
    answer = 0

    if s == s[::-1]:
        return len(s)

    def pail(i, j):
        while i >= 0 and j < len(s) and s[i] == s[j]:
            i -= 1
            j += 1
        return len(s[i+1:j])

    for i in range(len(s)):
        answer = max(answer, pail(i, i+1), pail(i, i+2))

    return answer
"abacde"

ab
aba
ba
a
ac
c
cd
d
de
e

 

3. 2중 for문 투포인터

Time: 0.85 ms

def solution(s):
    answer = 0

    for i in range(len(s)):
        for j in range(len(s), i, -1):
            if j - i < answer: 
                break

            if s[i:j] == s[i:j][::-1]:
                answer=j-i
                break

    return answer
"abacde"

abacde
abacd
abac
aba
bacde
bacd
bac
acde
acd
cde

 

4. 문자열 길이 긴 것부터 시작 인덱스 나눠서

Time: 0.01 ms

def solution(s):
    for i in range(len(s),0,-1): # 문자열 길이 긴 것 부터
        for j in range(len(s)-i+1): # 문자열 시작 인덱스
            if s[j:j+i] == s[j:j+i][::-1]:  
                return i
"abacde"

abacde
abacd
bacde
abac
bacd
acde
aba

 

 

더보기

 

2023.06.07 - [🩷 Algorithm PS/Math] - [1747] 소수&팰린드롬

 

[1747] 소수&팰린드롬

1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을

karla.tistory.com

 

2023.05.22 - [🩷 Algorithm PS/Implementation & String] - [17609] 회문 (유사회문, 투 포인터)

 

 

[17609] 회문 (유사회문, 투 포인터)

17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 분석

karla.tistory.com

2023.05.24 - [🩷 Algorithm PS/Implementation & String] - 격자판 회문 수

 

격자판 회문 수

문제 1부터 9까지의 자연수로 채워진 7*7 격자 격자판 위에서 가로방향 또는 세로방향으로 길이 5자리 회문 수가 몇 개 있는지 출력 빨간색처럼 구부러진 경우(87178)는 회문수로 간주하지 않습니

karla.tistory.com

2023.05.22 - [🩷 Algorithm PS/Implementation & String] - 회문 문자열 검사

 

회문 문자열 검사

문제 앞에서 읽을 때나 뒤에서 읽을 때나 같은 경우(회문 문자열)이면 YES를 출력하고 회문 문자열이 아니면 NO를 출력 첫 줄에 정수 N(1

karla.tistory.com

 

 

 

728x90
저작자표시 비영리 변경금지 (새창열림)
'Coding Test/programmers' 카테고리의 다른 글
  • 숫자 카드 나누기 (최대공약수)
  • 가장 큰 정사각형 찾기 (DP)
  • 점 찍기 (피타고라스)
  • 배달 (플로이드 워셜)
Karla Ko
Karla Ko
𝘾𝙤𝙣𝙩𝙞𝙣𝙪𝙤𝙪𝙨𝙡𝙮 𝙄𝙢𝙥𝙧𝙤𝙫𝙞𝙣𝙜, 𝘾𝙤𝙣𝙨𝙩𝙖𝙣𝙩𝙡𝙮 𝘿𝙚𝙫𝙚𝙡𝙤𝙥𝙞𝙣𝙜 𝙔𝙚𝙨!
    250x250
  • Karla Ko
    karlaLog
    Karla Ko
  • 전체
    오늘
    어제
    • Total (467)
      • Spring (19)
      • JPA (4)
      • Cloud & Architecture (15)
        • Kubernetes (5)
        • Docker (3)
        • MSA (2)
        • GCP (1)
        • AWS (4)
      • Devops (1)
      • Message Queue (4)
        • Kafka (2)
        • RabbitMQ (2)
      • Git (4)
      • DB (4)
      • Java (9)
      • Python (4)
      • CS (11)
        • OS (8)
        • Network (2)
        • Algorithm (1)
      • Coding Test (392)
        • programmers (156)
        • Graph (43)
        • DP (37)
        • Search (31)
        • Tree (13)
        • Data Structure (26)
        • Combination (12)
        • Implement (18)
        • Geedy (23)
        • Sort (7)
        • Math (21)
        • geometry (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    재귀
    최대공약수
    Algorithm
    트리
    LIS
    최소신장트리
    덱
    알고리즘
    자료구조
    조합
    힙
    DFS
    DP
    큐
    구현
    백준
    정렬
    프로그래머스
    구간합
    최단거리
    월간코드챌린지
    다익스트라
    그래프
    플로이드워셜
    그리디
    BFS
    스택
    동적계획법
    이분탐색
    파이썬
  • hELLO· Designed By정상우.v4.10.3
Karla Ko
가장 긴 팰린드롬 (2중 for문 인덱스, 투포인터, 문자열 길이)
상단으로

티스토리툴바