이 영역을 누르면 첫 페이지로 이동
포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

페이지 맨 위로 올라가기

포렌식 & 개발 이야기 - Forensics & Development

Pental - Forensics / iOS / Windows / Android / Kakaotalk / Telegram / Etc

백준 16472 - 고냥이 (파이썬)

  • 2025.03.17 01:04
  • Programming/백준
글 작성자: pental

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

풀이

1️⃣ 문제 접근

  • N 개 이하의 종류의 문자로 이루어진 가장 긴 연속 부분 문자열을 찾아야 한다..
  • 투 포인터 (start, end) 를 활용하여 슬라이딩 윈도우 방식으로 해결할 수 있다.

2️⃣ 알고리즘 흐름

  1. 초기 세팅
    1. count 배열을 사용하여 각 문자의 개수를 저장한다.
    2. num_types를 사용하여 현재 윈도우 내 문자의 종류 개수를 저장한다.
    3. start와 end 두 개의 포인터를 활용하여 윈도우 크기를 조정한다.
  2. 슬라이딩 윈도우 실행
    1. end 포인터를 확장하면서 문자 개수를 업데이트한다.
    2. num_types가 N 이하일 경우, answer 값을 갱신한다.
    3. num_types가 N을 초과하면 start 포인터를 이동하여 윈도우를 조정한다.

시간복잡도 분석

  • end 포인터가 문자열 끝까지 이동하면서 O(N)
  • start 포인터도 최대 N번 이동하면서 O(N)
  • 전체 시간 복잡도: O(N)
  • 슬라이딩 윈도우를 사용하여 한 번의 순회만으로 문제를 해결하므로 효율적

코드

# 백준 16472 - 고냥이
# 분류 : 투포인터

N = int(input())
S = input()

count = [0] * 26
num_types = 0

start = 0
end = 0
count[ord(S[0])- ord('a')] = 1
num_types = 1

answer = 0
while start < len(S) and end < len(S) :
    if num_types <= N :
        answer = max(answer, end - start + 1)
        end += 1
        if end < len(S) :
            count[ord(S[end]) - ord('a')] += 1
            if count[ord(S[end]) - ord('a')] == 1 :
                num_types += 1
    else :
        start += 1
        count[ord(S[start - 1]) - ord('a')] -= 1
        if count[ord(S[start - 1]) - ord('a')] == 0 :
            num_types -= 1

print(answer)

 

저작자표시 비영리 (새창열림)

'Programming > 백준' 카테고리의 다른 글

백준 31823 - 악질 검거 (파이썬)  (0) 2025.03.18
백준 16466 - 콘서트 (파이썬)  (0) 2025.03.17
백준 23305 - 수강변경 (파이썬)  (0) 2025.03.16
백준 31923 - 마라탕후루 (파이썬)  (0) 2025.03.16
백준 31844 - 창고지기 (파이썬)  (0) 2025.03.16

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • 백준 31823 - 악질 검거 (파이썬)

    백준 31823 - 악질 검거 (파이썬)

    2025.03.18
  • 백준 16466 - 콘서트 (파이썬)

    백준 16466 - 콘서트 (파이썬)

    2025.03.17
  • 백준 23305 - 수강변경 (파이썬)

    백준 23305 - 수강변경 (파이썬)

    2025.03.16
  • 백준 31923 - 마라탕후루 (파이썬)

    백준 31923 - 마라탕후루 (파이썬)

    2025.03.16
다른 글 더 둘러보기

정보

포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

  • 포렌식 & 개발 이야기 - Forensics & Development의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

카테고리

  • Category (443) N
    • Forensics (104)
      • Magnet AXIOM (28)
      • Digital Forensics Informati.. (9)
      • Iphone Forensics (23)
      • DFC (7)
      • 디지털포렌식전문가2급 자격증 (10)
      • FTK ACE 자격증 (7)
    • 이것저것 (7)
      • Ubuntu (6)
      • 디스코드 봇 (4)
      • Volatility GUI (2)
    • CTF (32)
      • NEWSECU (14)
      • CTF-d (5)
      • Puzzel - Network Forensics (2)
      • Security Traps (2)
      • system32.kr (5)
      • HMCTF (4)
    • Programming (252) N
      • C (10)
      • Python (11)
      • 백준 (198) N
      • 프로그래머스 (32)
    • 그냥 개발 및 잡담 (16)
      • Docker (2)
      • Google Cloud (3)
      • OS 개발 (3)
    • Best of Best (20)

최근 글

인기 글

댓글

공지사항

아카이브

태그

  • 디지털포렌식
  • pental
  • axiom
  • 백준
  • 파이썬
  • 포렌식
  • Forensics
  • 프로그래머스
  • 전체 보기…

정보

pental의 포렌식 & 개발 이야기 - Forensics & Development

포렌식 & 개발 이야기 - Forensics & Development

pental

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © pental.

티스토리툴바