백준 5555번 [반지](C++) -yes6686- 티스토리

백준 문제 풀이: 5555 [반지]

---

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

문제 설명:

반지 문자열과 특정 문자열이 주어졌을 때, 반지 문자열을 두 번 이어붙인 뒤 특정 문자열이 포함되는지를 확인합니다. 여러 개의 반지 문자열 중 특정 문자열이 포함된 반지의 개수를 출력합니다.

---

문제 해결 코드

// 백준 5555 - 반지
#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string target; // 찾을 문자열
    cin >> target;

    int n; // 반지 개수
    cin >> n;

    int count = 0; // 포함된 반지 개수

    while (n--) {
        string ring;
        cin >> ring;

        // 반지 문자열을 두 번 이어붙임
        ring += ring;

        // 이어붙인 문자열에 target이 포함되면 count 증가
        if (ring.find(target) != string::npos) {
            count++;
        }
    }

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

---

코드 설명

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

• 핵심 알고리즘:
  • 반지 문자열을 두 번 이어붙여서 원형 문자열의 순환을 처리합니다.
  • find 함수로 이어붙인 문자열에 특정 문자열이 포함되는지 확인합니다.
• 구현 세부사항:
  • 반지 문자열의 원형성을 처리하기 위해 ring += ring을 사용하여 문자열을 두 번 이어붙입니다.
  • find는 특정 문자열이 포함된 위치를 반환하며, 포함되지 않은 경우 string::npos를 반환합니다.
• 시간 복잡도 분석:
  • 반지 문자열 길이를 m, 찾을 문자열 길이를 k라 할 때, find의 복잡도는 O(m).
  • 반지가 n개 주어지므로 전체 시간 복잡도는 O(n ⋅ m).

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

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