백준 27930번 [당신은 운명을 믿나요?](C++) -yes6686- 티스토리

백준 문제 풀이: 27930 [당신은 운명을 믿나요?]

---

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

문제 설명:

주어진 문자열 s에서 "KOREA" 또는 "YONSEI"라는 단어가 순서대로 등장하는지를 판단하는 문제입니다. 두 단어 중 먼저 완성되는 단어를 출력합니다.

주어진 문자열을 순회하며 "KOREA" 또는 "YONSEI"의 각 문자를 순서대로 맞추는 방식으로 해결할 수 있습니다.

---

문제 해결 코드

// C++로 구현된 코드
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    string s;
    cin >> s; // 입력 문자열
    
    string s1 = "KOREA";
    string s2 = "YONSEI";
    
    int k1 = 0, k2 = 0; // 각 단어에서 매칭된 문자 인덱스
    
    for (int i = 0; i < s.size(); i++) {
        // "KOREA" 단어 매칭
        if (s[i] == s1[k1]) {
            k1++;
        }
        // "YONSEI" 단어 매칭
        if (s[i] == s2[k2]) {
            k2++;
        }
        // "KOREA"가 먼저 완성되면 출력
        if (k1 == s1.size()) {
            cout << s1;
            return 0;
        }
        // "YONSEI"가 먼저 완성되면 출력
        if (k2 == s2.size()) {
            cout << s2;
            return 0;
        }
    }
    
    return 0;
}

---

코드 설명

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

• 핵심 알고리즘:
  • 입력 문자열을 순회하면서 "KOREA"와 "YONSEI"의 문자를 순서대로 매칭합니다.
  • 두 단어 중 하나가 먼저 완성되면 해당 단어를 출력하고 종료합니다.
• 구현 세부사항:
  • 두 단어의 매칭 상태를 각각 k1와 k2 변수로 관리합니다.
  • 입력 문자열의 각 문자를 검사하며, 현재 매칭 상태와 비교해 인덱스를 증가시킵니다.
  • 매칭이 완료되면 결과를 출력하고 즉시 프로그램을 종료합니다.
• 시간 복잡도 분석:
  • 입력 문자열의 길이를 n이라 하면, 문자열을 한 번 순회하므로 시간 복잡도는 O(n)입니다.
  • 두 단어의 길이는 상수로 간주할 수 있으므로 추가적인 시간 복잡도는 무시 가능합니다.

---

결과

입력된 문자열에서 "KOREA"와 "YONSEI" 중 먼저 완성되는 단어를 올바르게 출력합니다.

해당 문제에 대한 다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!