ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 5658.보물상자 비밀번호
    알고리즘/SW Expert Academy 2020. 6. 18. 01:29

    이번에 풀어볼 문제는 보물상자 비밀번호이다.

    난이도는 쉬운편에 속한다. 그 이유는 착각하더라도 우선 예외처리를 쉽게 수정할 수 있었고

    정답률을 믿진 않지만 정답률도 61%로 높았으며 실제 문제를 읽으면서도 쉽다는 걸 느낄 수 있었다.

     

    SW Expert Academy

    SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

    swexpertacademy.com

    # 나의 풀이 설계는 다음과 같다.

    1. 각각의 면에 몇개의 문자가 올 수 있는지 우선 파악한다.

     

    2. 중복되지않은 deque를 만들어서 중복을 비교 후 중복되지 않으면 deque에 넣고 중복되면 duplicate값을 +1 해준다.

       => 만약 4번 연속되게 ( duplicate값이 4가 된다면 ) 중복이 된다면 탐색을 멈춘다.

       => 하지만 그 전에 한 번이라도 중복되지 않은 값을 발견한다면 duplicate변수를 0으로 초기화하고 계속 탐색한다.

     

    3. 탐색이 끝나면 오름차순으로 정리한 뒤, 숫자의 갯수 - K를 해서 K번째로 큰 수를 찾으면 된다.

     


     

    이 문제에서 내가 처음 실수했던 것은 바로 구할 수 있는 모든 수를 구하지 않고

    그냥 중복되지 않은 값이 K만큼 나왔다면 탐색을 종료 한 것이다.

    하지만 이 문제는 나올 수 있는 모든 값을 구해야 했기 때문에 그렇게 구하면 당연히 틀린다.

     

    나는 2번 Test Case를 적용하다가 꺠달았다.

    => 결과적으로는 어떻게 보면 문제는 풀었지만 설계는 실패했다.

        문제가 쉽다고 설계를 소홀이하면 발생하는 일인 것 같다.

        쉽게 수정이 가능했어서 다행이지 아니였으면 하루종일 했을지도 모르겠다.. 주의하자..

     


     

    < Code 설명 >

    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
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103

    #pragma
     warning(disable:4996)
    #include <iostream>
    #include <deque>
    #include <algorithm>
     
    using namespace std;
     
    int T, N, K;
     
    deque<char>str;
    deque<string>cmp;
     
     
    int hex_to_int(string hex_str){ // 16진수를 10진수로 바꿔주는 함수
        deque<int>int_str; 
        for (int i = 0; i < hex_str.size(); i++)
            if (hex_str[i] >= 65 && hex_str[i] <=70// 문자가 대문자일 경우 A ~ F
                int_str.push_back(hex_str[i] - 55);
            else if (hex_str[i] >= 48 && hex_str[i] <= 57// 문자가 숫자일 경우 0 ~ 9
                int_str.push_back(hex_str[i] - 48);
        
        int int_num = 0;
        int j = 1;
     
        for (int i = hex_str.size()-1; i >=0 ; i--){
            int_num += int_str[i] * j;
            j *= 16// 16진수의 특성대로 만들어줌
        }
        return int_num; // 10진수값 리턴
    }
     
    void change(deque<char>&q){ // 시계방향으로 돌림
        q.push_front(q.back());
        q.pop_back();
    }
     
    bool check_cmp(deque<string>&com, string str_ori){
        int flag = true;
        for (int i = 0; i < com.size(); i++){
            if (com[i] == str_ori){ // 같은게 있으면
                flag = false// 거짓
                break;
            }
        }
        return flag;
    }
     
    void init(){ // 초기화 함수
        str.clear();
        cmp.clear();
    }
     
    int main() {
        freopen("5658.txt""r", stdin);
        cin >> T;
        for (int z = 1; z <= T; z++){
            cin >> N >> K;
            init();
            char tmp;
            for (int i = 0; i < N; i++){
                cin >> tmp;
                str.push_back(tmp);
            }
     
            int div = N / 4// 각각의 면에 몇개의 숫자가 배치될지 정함
            
            string tmp_str;
            bool flag = true;
            int dup = 0// 중복숫자
            while (true){ // 계속돌림
                for (int i = 0; i < N; i++){
                    //cout << str[i] << " ";
                    tmp_str += str[i]; // 문자를 연결해서 문자열 만들기
                    if (tmp_str.size() % div == 0){ //문자열의 길이가 한쪽 면에 올 수 있는 길이가 되면
                        //cout << "\n";
                        if (!cmp.empty()){ // 비교 dequq가 비어있지 않았다면
                            if (check_cmp(cmp, tmp_str)){ // 참일 경우 같은 내용이 없다는 의미
                                cmp.push_back(tmp_str); //비교 deque에 없다면 넣어줌
                                dup = 0// 중복숫자 초기화
                            }
                            else
                                dup+=1// 중복숫자 +1;
                        }
                        else if (cmp.empty()) // 비교 dequeu가 비어있다면
                            cmp.push_back(tmp_str); // 그냥 넣어줌
     
                        tmp_str.clear(); // 중복 확인 후 비교 문자열 초기화
                    }
                    if (dup==div){ // 중복숫자가 연속해서 4개 나온다면
                        flag = false// 그만 탐색하겠다는 flas값 조절
                        break;
                    }
                }
                if (!flag) // 그만탐색
                    break;
                change(str); // 시계방향으로 문자열 돌림
            }
            sort(cmp.begin(), cmp.end()); // 오름차순으로 정리
            cout << "#" << z << " " << hex_to_int(cmp[cmp.size()-K]) << "\n"// 전체 값에서 -K 한 값이 K번째로 큰 값이므로
     
        }
        return 0;
    }
    cs

    '알고리즘 > SW Expert Academy' 카테고리의 다른 글

    2115.벌꿀채취  (0) 2020.06.23
    4008.숫자 만들기  (0) 2020.06.19
    5658.보물상자 비밀번호  (0) 2020.06.18
    1767.프로세서 연결하기  (0) 2020.06.16
    5650.핀볼 게임  (0) 2020.06.14
    5656.벽돌깨기  (0) 2020.06.12

    댓글 0

Designed by Tistory.