[백준 1120] 문자열

• 안녕하세요. BlockDMask 입니다.

• "C 스타일을 C++ 로 바꾼다" 가 아니라....

• "C++ 스럽게, OOP 스럽게 코딩한다." 라는게 흠..

• 여기서 클래스를 만들고 객체를 생성하는게 맞는건가?

• 이렇게 짧은 문제에서도 확장성을 생각해서 코드를 짜는게 맞는건가?

• 여러 생각이 들면서

• 문제를 풀어도

• 코드를 계속계속 살펴보게되네요;;

• 아무튼 오늘의 문제 풀어봤습니다.

0. 제목

• 백준 1120 문자열

• BOJ 1120 문자열

• C, C++ 문자열

1. 문제 설명

• 길이가 N으로 같은 문자열 X와 Y가 있을때, 

• 두 문자열 X와 Y의 차이는 X[i] != Y[i] 인 i의 개수 이다.
  
  

• 예를 들어, X="jimin", y="minji" 이면, 둘의 차이는 4 이다.

• 두 문자열 A와 B가 주어진다.

• 이 때, A의 길이는 B의 길이보다 작거나 같다.

• 자 이제 A의 길이가 B의 길이가 같가질 때 까지 다음과 같은 연산을 할 수 있다.
  1) A의 앞에 아무 알파벳이나 추가한다.
  2) A의 뒤에 아무 알파벳이나 추가한다.
  이 때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

• 입력
  첫째 줄에 A와 B가 주어진다.
  A와 B의 길이는 최대 50이다.
  A의 길이는 B의 길이보다 작거나 같다.
  모든 문자는 알파벳 소문자로만 이루어져 있다.

• 출력
  첫째 줄에 문제의 정답을 출력한다.

2. 풀이 과정

• 얼핏 보면 A의 앞뒤에 무언가를 추가 하면서 비교해야한다고 생각 할 수 있는데,

• 어짜피 추가 하게되면 추가한 부분은 B와 같도록 추가 하지 않습니까?

• 그러면 추가하는 것 보다는
  작은 문자열 덩어리를 
  큰 문자열의 일부와 비교하면서 
  그때의 최소를 구하면 됩니다.

• 이런식으로..
  

3. 소스 코드

• class (x)

//https://www.acmicpc.net/problem/1120
//BOJ_1120_charString
//길이를 맞춰야하는줄 알았지만 잘 보면
//길이 필요없고 작은 문자열을 이동하면서 큰 문자열과 다른거 몇개인지 최소값 구하는 문제였습니다.
 
#include <iostream>
#include<string>
#include<algorithm>
#define MAX_LEN 50
using namespace std;
 
int getDiffCount(string &str_short, string &str_long){
    int gap = (int)str_long.size() - (int)str_short.size() +1;
    int result = MAX_LEN + 1;
    
    for(int i=0; i<gap; i++){
        int tmp =0;
        
        for(int j=0; j<str_short.size(); j++){
            if(str_short[j] != str_long[j+i]) tmp++;
        }
        result = min(result, tmp);
        
    }
    return result;
}
 
//짧은 문자열을 첫번째 파라미터로
int solution(string& s1, string& s2){
    if(s1.size() < s2.size()){
        return getDiffCount(s1,s2);
    }else{
        return getDiffCount(s2,s1);
    }
}
 
 
int main(void){
    string s1, s2;
    cin >> s1 >> s2;
    cout << solution(s1, s2) << endl;
    return 0;
}
 

• class (o)

//https://www.acmicpc.net/problem/1120
//BOJ_1120_charString
//길이를 맞춰야하는줄 알았지만 잘 보면
//길이 필요없고 작은 문자열을 이동하면서 큰 문자열과 다른거 몇개인지 최소값 구하는 문제였습니다.
 
#include<iostream>
#include<string>
using namespace std;
 
class myString{
 
private:
    const int maxLen = 50;  //문자열 최대 길이
    string s;
    int size;
 
public:
    myString(){}
    ~myString(){}
 
    void setStr(string str){
        s = str;
        size = (int)str.size();
    }
    char getChar(int idx) const{
        return s[idx];
    }
    int getSize() const{
        return size;
    }
 
    //차이를 계산해서 최소 count 반환, other이 무조건 길다.
    int getDiffCount(myString& other) const{
        int result= maxLen + 1;
 
        int gap = other.getSize() - this->getSize() +1;
 
        for(int i=0; i<gap; i++){   //몇번 비교 할건지
            int tmp=0;
            for(int j=0; j<this->getSize(); j++){   //다른 부분있는지
                if(this->getChar(j) != other.getChar(j+i))tmp++;
            }
            result = min(result, tmp); //최소값
 
        }
        return result;
    }
};
 
//내부의 문자열이 짧은 객체가 본인의 메소드를 호출
int solution(myString& s1, myString& s2){
    if(s1.getSize() < s2.getSize()){
        return s1.getDiffCount(s2);
    }else{
        return s2.getDiffCount(s1);
    }
}
 
int main(void){
    myString arr[2];
    for(int i=0; i<2; i++){
        string str;
        cin >> str;
        arr[i].setStr(str);
    }
 
    cout << solution(arr[0], arr[1]) << endl;
    return 0;
}
 
 

4. 인증

• class (x)
  

• class (o)
  

• 문제 출처 : https://www.acmicpc.net/problem/1120

• 감사합니다.