백준 2495번 [연속구간](C++) -yes6686- 티스토리

백준 문제 풀이: 2495 (연속구간)

---

문제 링크: https://www.acmicpc.net/problem/2495

문제 설명:

세 개의 숫자가 입력으로 주어집니다. 각 숫자에 대해 같은 숫자가 연속으로 등장하는 **가장 긴 구간의 길이**를 구하세요. 숫자는 항상 **8자리**이며, 각 자리 숫자는 0부터 9까지입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    for (int i = 0; i < 3; i++) { // 세 개의 숫자를 처리
        string s;
        cin >> s; // 입력된 숫자 문자열
        int maxAns = 1; // 연속 구간의 최대 길이 초기값

        // 0부터 9까지 각 숫자에 대해 확인
        for (int t = 0; t <= 9; t++) {
            int cnt = 0; // 현재 숫자의 연속된 개수
            for (int j = 0; j < s.size(); j++) {
                if (s[j] - '0' == t) { // 현재 문자가 숫자 t와 같으면
                    cnt++;
                    maxAns = max(maxAns, cnt); // 최대값 갱신
                } else {
                    cnt = 0; // 연속되지 않으면 초기화
                }
            }
        }

        cout << maxAns << '\n'; // 결과 출력
    }
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 입력 처리: 세 개의 숫자(각각 8자리)를 입력받아 각 숫자에 대해 연속 구간을 계산합니다.
• 연속 구간 탐색:
  • 0부터 9까지 각 숫자 t에 대해 연속된 개수를 확인합니다.
  • 문자열의 각 문자 s[j]가 숫자 t와 같으면 cnt를 증가시킵니다.
  • 연속되지 않으면 cnt를 0으로 초기화합니다.
• 최대값 갱신: maxAns = max(maxAns, cnt)를 사용해 현재까지의 최대 연속 구간 길이를 기록합니다.

시간 복잡도 분석

• 입력 문자열의 길이는 8이며, 각 숫자(0~9)에 대해 순회하므로 **O(10 × 8)**입니다.
• 세 개의 숫자를 처리하므로 전체 시간 복잡도는 **O(3 × 10 × 8) = O(240)**입니다.

---

결과

각 숫자에 대해 연속된 같은 숫자의 최대 구간 길이를 출력합니다.

• 입력 예시:

  12345678  
  11223344  
  99999999

• 출력 예시:

  1  
  2  
  8

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!