<알고리즘 문제풀이&연습>/[C++] 백준, 프로그래머스 등등

[백준 1120] 문자열

BlockDMask 2017. 11. 14. 16:42
반응형
  • 안녕하세요. 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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//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;
}
 
cs
  • class (o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//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;
}
 
 
cs


4. 인증

  • class (x)

  • class (o)


반응형