[백준] 1701번 - Cubeditor / 골드 2 / 파이썬 풀이

2022. 3. 23. 13:00·알고리즘 공부

문제 링크

https://www.acmicpc.net/problem/1701

 

1701번: Cubeditor

Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한

www.acmicpc.net

 

시간 제한 : 0.5 초

메모리 제한 : 128 MB

 

문제 요약

  • 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열만 검색이 가능하게끔 하는 에디터.
    ex) abcdabc -> abc 는 검색 가능 / abcd는 한번만 나오므로 검색 불가.
  • abcabcabc에서 abc는 세 번, abcabc는 두 번, abcabca는 한 번만 나오는 걸로 카운트.
    두 번 이상 나오는 문자열 중 길이가 가장 긴 것은 abcabc가 됨.

  • 문제 : 두 번 이상 나오는 부분 문자열 중에서 길이가 가장 긴 문자열의 길이를 구하는 프로그램 작성.

 

입력

예제 입력1

abcdabcabb

예제 입력2

abcdefghijklmn

예제 입력3

abcabcabc

 

출력

예제 출력1

3

예제 출력2

0

예제 출력3

6

풀이

"팁 한마디"

def make_table(patten):
    length = len(patten)
    table = [0] * len(patten)		# pattern이라는 문자열에서 가장 긴 반복문자열의 길이를 저장하기 위한 table 선언
    j = 0
    for i in range(1, length):		# pattern의 길이만큼 for문 실행.
		# i를 1부터 시작함으로써, pattern에서의 두번째 문자부터 비교.
        while j > 0 and patten[i] != patten[j]:		# 반복문자열이 끝났음을 확인한다면
            j = table[j - 1]		# 반복문자열의 패턴 바로 전 인덱스부터 다시 j를 설정.
        if patten[i] == patten[j]:	
            j += 1
            table[i] = j	
    return max(table)


if __name__ == "__main__":
    s = input()		# 문자열 입력 받음
    result = 0

    for idx in range(len(s)):
        sub_str = s[idx:len(s)]		# idx라는 인덱스부터 시작하는 s의 부분 문자열 sub_str 선언
        result = max(result, make_table(sub_str))

    print(result)

 

참고

https://dirmathfl.tistory.com/308

https://peisea0830.tistory.com/65​

 

[Python 3] BOJ - 1701 "Cubeditor"

 # 문제 링크 : https://www.acmicpc.net/problem/1701 1701번: Cubeditor 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점..

peisea0830.tistory.com

 

'알고리즘 공부' 카테고리의 다른 글

[백준] 1102번 - 발전소 / 골드 1 / 파이썬 풀이  (0) 2022.04.13
[백준] 1949번 - 우수마을 / 골드 2 / 파이썬 풀이  (0) 2022.04.12
[백준] 1111번 - IQ Test / 골드 2 / 파이썬 풀이  (0) 2022.03.22
[백준] 1525번 - 퍼즐 / 골드 2 / 파이썬 풀이  (0) 2022.02.28
[백준] 1202번 - 보석 도둑 / 골드 2 / 파이썬 풀이  (0) 2022.02.24
'알고리즘 공부' 카테고리의 다른 글
  • [백준] 1102번 - 발전소 / 골드 1 / 파이썬 풀이
  • [백준] 1949번 - 우수마을 / 골드 2 / 파이썬 풀이
  • [백준] 1111번 - IQ Test / 골드 2 / 파이썬 풀이
  • [백준] 1525번 - 퍼즐 / 골드 2 / 파이썬 풀이
코_노
코_노
일상의 불편함을 기술로서 해결하기 위해 노력하는 IT 엔지니어입니다. Contact point) jjh3706@gmail.com
  • 코_노
    코딩하는 주노 이야기
    코_노
  • 전체
    오늘
    어제
    • 코딩 이야기 (121)
      • DB (35)
        • SQL Server (MSSQL) (27)
        • MongoDB (2)
        • Hadoop Ecosystem (0)
        • SQLP 공부 (2)
      • 데이터 엔지니어링 (0)
        • Spark (0)
      • Middleware (21)
        • 웹서버 (7)
        • WAS (6)
        • WSGI (3)
        • 기타 (5)
      • OS (10)
        • Linux (7)
        • Windows (3)
      • Network (8)
      • Cloud (1)
        • AWS (1)
      • DevOps (8)
        • Container & K8S (0)
        • Github (3)
        • Ansible (2)
        • Terraform (3)
      • Security (3)
      • Observability (5)
      • CS 지식 | 기초 용어,개념 (7)
      • Python (1)
        • Flask (0)
      • Java (7)
        • JPA (0)
      • 안드로이드 (1)
      • 알고리즘 공부 (14)
  • 블로그 메뉴

    • 홈
    • 코딩 이야기
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    DBA
    SSMS
    jvm 실행 옵션
    SQL Server 2019 Restore
    SQL Server 2019
    MongoDB Sharding
    백준 골드2
    백준 골드 2
    SAS
    백준 파이썬
    db
    SAS 아키텍처
    백준 python
    백준
    Windows AD
    백준 알고리즘
    백준 골드4
    SAS Intelligence Platform
    MSSQL
    SQL Server
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.6
코_노
[백준] 1701번 - Cubeditor / 골드 2 / 파이썬 풀이
상단으로

티스토리툴바