백준 4378번 [트ㅏㅊ;](C++) -yes6686- 티스토리

백준 문제 풀이: 4378 [트ㅏㅊ;]

---

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

문제 설명:

키보드가 오른쪽으로 한 칸씩 밀려 입력된 문자열을 복구하는 문제입니다. 입력된 문자의 바로 왼쪽에 있는 문자를 찾아 원래의 문자열을 출력해야 합니다.

• 입력: 여러 줄의 문자열이 주어집니다.
• 출력: 각 문자의 바로 왼쪽에 있는 문자를 찾아 복구된 문자열을 출력합니다.
• 공백 문자는 그대로 유지합니다.

---

문제 해결 코드

#include <iostream>
#include <string>
using namespace std;

// 키보드 행 정의
string str[4] = { 
    "`1234567890-=", 
    "QWERTYUIOP[]\\", 
    "ASDFGHJKL;'", 
    "ZXCVBNM,./" 
};

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

    string s;
    // 여러 줄 입력 처리
    while (getline(cin, s)) {
        for (int t = 0; t < s.size(); t++) {
            if (s[t] == ' ') {
                // 공백은 그대로 출력
                cout << s[t];
                continue;
            }

            // 문자의 바로 왼쪽 문자 찾기
            bool found = false;
            for (int i = 0; i < 4; i++) { // 각 행 탐색
                for (int j = 0; j < str[i].size(); j++) {
                    if (s[t] == str[i][j]) {
                        cout << str[i][j - 1]; // 바로 왼쪽 문자 출력
                        found = true;
                        break;
                    }
                }
                if (found) break; // 문자를 찾으면 더 이상 탐색하지 않음
            }
        }
        cout << '\n'; // 한 줄 처리 후 개행
    }

    return 0;
}

---

코드 설명

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

• 핵심 알고리즘:
  • 키보드의 각 행을 문자열 배열 str에 저장합니다.
  • 입력 문자열의 각 문자를 탐색하며, 키보드 배열에서 해당 문자의 바로 왼쪽 문자를 찾아 출력합니다.
• 구현 세부사항:
  • getline을 사용해 여러 줄 입력을 처리합니다.
  • 문자 ' ' (공백)는 예외적으로 그대로 출력합니다.
  • 키보드 배열을 탐색하며 문자를 찾고, 해당 문자의 왼쪽 문자(str[i][j - 1])를 출력합니다.
  • 문자를 찾은 후 불필요한 탐색을 막기 위해 break를 사용합니다.
• 시간 복잡도 분석:
  • 각 문자를 키보드 배열에서 탐색하는 과정은 O(1)입니다.
  • 문자열의 길이를 m이라 하면, 전체 시간 복잡도는 O(n ⋅ m)입니다. 여기서 n은 입력 줄의 개수입니다.

---

결과

입력된 문자열에서 오른쪽으로 밀린 문자를 복구해 원래 문장을 정확히 출력합니다.

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