코딩 테스트 기록 23회차 - 고난이도 양치기 (해시2)

요즘 고난이도 문제로 양치기를 하는데 역시 진작 했어야 했나 싶다. LV 1, 2에서 놀다가 2, 3에서 놀려니까 생각보다 첫 대면인 문제들은 문제 유형을 알고 푸는데도 시간이 걸리는 경우가 꽤 있었다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

걸린 시간: 48분 5초

문제 내용: 토핑 종류가 공정하게 분배되도록 케이크를 자르는 경우의 수가 몇 가지인지를 출력하는 문제이다.

 

내가 쓴 코드

이건 내가 맨 처음 접근했던 방식이다. 토핑의 종류를 세기 위해 양쪽에서 카운트를 세면서 중앙으로 오고 있는데 이 접근으로 가다가 약 40분 정도를 쓰고서야 뭔가 잘못된 것을 깨닫고 방법을 바꿨다. 이래서 첫 접근이 중요하다. 첫 접근이 잘 안되면 뭔가 잘못 되었다는 것을 좀 빠르게 깨달을 수 있어야 하는데 지금 그것도 잘 안되고 있긴 하다. 하나의 꽂히면 거기에 매몰되느라...

#define _GLIBCXX_ASSERTIONS

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

/*
토핑 종류 분류 -> 해시 테이블
토핑 종류 - 키
1분 55초
*/

int solution(vector<int> topping) {
    int answer = 0;
    unordered_map<int> cake1;
    unordered_map<int> cake2;

    int i = 0;
    int j = topping.size() - 1;

    int cake1_count = 0;
    int cake2_count = 0;

    while (i < j)
    {
        if (cake1.find(topping[i]) == cake1.end())
        {
            cake1.insert(topping[i]);
            cake1_count = 0;
        }
        else
        {
            ++cake1_count;
        }

        if (cake2.find(topping[j]) == cake2.end())
        {
            cake2.insert(topping[j]);
            cake2_count = 0;
        }
        else
        {
            ++cake2_count;
        }

        if (cake1.size() == cake2.size())
        {
            ++i;
            --j;
        }
        else if (cake1.size() < cake2.size())
        {
            ++i;
        }
        else
        {
            --j;
        }
    }

    if (cake1.size() != cake2.size())
    {
        return 0;
    }

    if (i > j)
    {
        --i;
        ++j;
    }

    bool has_cake1_topping = cake1.find(topping[i]) != cake1.end();
    bool has_cake2_topping = cake2.find(topping[j]) != cake2.end();

    if (has_cake1_topping && has_cake2_topping)
    {
        answer = cake1_count + cake2_count + 1;
    }
    else if (!has_cake1_topping && !has_cake2_topping)
    {
        answer = 0;
    }

    cout << cake1_count << " " << cake2_count << endl;

    for (const auto& iter : cake1)
    {
        cout << iter << " ";
    }

    cout << endl;

    for (const auto& iter : cake2)
    {
        cout << iter << " ";
    }

    return answer;
}

 

이게 내가 수정한 코드이다. 훨씬 깔끔하고 직관적이다. 순처적으로 자른 부위를 기준으로 다른 쪽 접시에 담는 것처럼 넘기면서 서로 비교하는 것 같지 않은가? (참고로 cake1은 unordered_set이 더 적절했던 것 같다.) 이제 문제 지문을 보자.

• 두 조각으로 잘라서 동생과 한 조각씩: 자르는 행위는 한 번 일어나며, 그 위치 하나가 두 조각의 상태를 결정하기 때문에 투포인터를 쓸 이유가 없었다. 두 조각, 토핑의 종류를 센다는 발상에서 나도 모르게 투포인터를 잡았는데 AI는 양끝 투포인터의 신호는 "정렬된 배열에서 두 원소의 조건"이라고 말한다.
• 롤케이크에는 여러가지 토핑들이 "일렬로 올려져" 있습니다: 일력로 올려져 있다는 부분에서 정렬 여부에 대해서 생각해볼 필요가 있다. 일렬로 올려져 있는 상태에서 케이크에 손을 대지 않고 자르는 행위만 할 수 있다면 케이크 배열의 원소 순서에 손을 대면 안되니 정렬은 하면 안된다는 것을 알 수 있다.
• 그들은 롤케이크의 크기보다 롤케이크 위에 올려진 토핑들의 종류에 더 관심이 많습니다: 종류에 대한 이야기가 나오면 일단 해시 테이블을 찍으면 얼추 맞는다. 지문에서 롤케이크의 크기는 중요하지 않다고 이야기하고 있으니 이 또한 강력한 증거로 뒷받침된다.
• 공평하게 자르는 방법의 수를 return: 투포인터를 쓰면 안되는 것을 알아채야 했던 지점이 또 있었다. 자른다는 행위를 코드로 어떻게 구현할 수 있는지도 직관적으로 더 잘 생각해봤으면 너무나 쉽게 풀 수 있던 문제였다.

#define _GLIBCXX_ASSERTIONS

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
    
    unordered_map<int, int> cake1;
    unordered_map<int, int> cake2;
    
    for (int i = 0; i < topping.size(); ++i)
    {
        ++cake2[topping[i]];
    }
    
    for (int i = 0; i < topping.size(); ++i)
    {
        ++cake1[topping[i]];
        --cake2[topping[i]];
        
        if (cake2[topping[i]] == 0)
        {
            cake2.erase(topping[i]);
        }
        
        if (cake1.size() == cake2.size())
        {
            ++answer;
        }
    }
    
    return answer;
}

 

https://school.programmers.co.kr/learn/courses/30/lessons/152996

프로그래머스

걸린 시간: 1시간 시간 초과

문제 내용: 사람들의 몸무게나 나열된 배열을 주고 시소의 어디에 앉을 수 있는지 경우의 수를 제공하고 시소가 평형을 이루는 경우의 수를 출력하는 문제이다.

 

내가 쓴 코드

이 역시 첫 접근이 잘못 되었었다. 해시 테이블을 쓸지, 배열을 쓸지 선택하는 과정을 떠나서 애초에 찾아야 하는 몸무게의 비율이 1:2, 2:3, 3:4였는데 코드를 보면 1:2, 1:3, 1:4를 찾고 있다. 또한 중복되는 키에 대해서도 처리를 한답시고 뭔가 추가적인 연산을 하느라 실행 시간 초과가 떠서 결국에는 문제를 풀지 못했다. 근데 신기한 건 그 와중에 시간 초과 빼고는 테스트 케이스가 전부 통과하더라. 애초에 답 자체를 잘못 찾고 있었는데 말이다.

#define _GLIBCXX_ASSERTIONS

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
왜 반환값이 long long이지? weights의 길이는 10만이다.
쉽게 생각하면 2, 3, 4를 각 원소에 곱하고 어딘가에 있는지 없는지 검사.
-> 해시 테이블
있으면 카운트, 없으면 저장
3분 39초

지금 보니 같은 원소가 있고, 다른 물체가 무게가 다른 경우를 의도한 것 같다.
키-값을 통해 해당 무게를 가진 물체의 갯수를 구현하면 쉬울 것 같다.
8분 54초

중복되는 원소는 vector로 구분한다. vector에는 인덱스를 넣고 원소 수는 size로 도출.
다시 생각해보니까 set으로 구분하는 게 더 나을 것 같다. 중복 원소가 자동 제거다.
다시 생각해보니까 vector가 나을 거 같다.
다시 보니까 둘 다 필요해 보인다.

왜 시간초과지?
50분
*/

long long solution(vector<int> weights) {
    long long answer = 0;
    unordered_map<int, vector<int>> seesaw_friend;

    for (int i = 0; i < weights.size(); ++i)
    {
        int count_2m = seesaw_friend[weights[i] * 2].size();
        int count_3m = seesaw_friend[weights[i] * 3].size();
        int count_4m = seesaw_friend[weights[i] * 4].size();

        unordered_set<int> us;

        for (int j = 0; j < count_2m; ++j)
        {
            us.insert(seesaw_friend[weights[i] * 2][j]);
        }

        for (int j = 0; j < count_3m; ++j)
        {
            us.insert(seesaw_friend[weights[i] * 3][j]);
        }

        for (int j = 0; j < count_4m; ++j)
        {
            us.insert(seesaw_friend[weights[i] * 4][j]);
        }

        answer += us.size();

        seesaw_friend[weights[i] * 2].push_back(i);
        seesaw_friend[weights[i] * 3].push_back(i);
        seesaw_friend[weights[i] * 4].push_back(i);
    }

    return answer;
}

 

결국 AI에게 답을 물었고 이 코드는 그렇게 나온 코드이다. 애초에 중복값을 찾는답시고 중첩 반복을 돌릴 필요가 아예 없었고 배열 자체를 해시로 쓰는 문제여서 해시 테이블을 따로 선언할 필요가 없었다. 이러한 내용들을 어디에서 단서를 얻어야 했는지 문제 지문을 보자.

• 2(m), 3(m), 4(m) 거리의 지점에 좌석 / 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면: 무게의 비율이 정해져 있고 해당값을 곱해서 누군가의 무게를 조회하는 방식이 사용된다. 2(m), 3(m), 4(m)라고 되어있는 것이 데이터의 "종류"라고 본다면 이 역시 해시 테이블을 쓴다고 짐작하는 것도 가능할 것이다. 이게 아니더라도 "조회"가 필요하다는 지점에서 후보군으로 생각할 수 있다.
• 시소 짝꿍이 몇 쌍 존재하는지 구하여: 여기서 쌍의 갯수를 구하는 과정은 누구와 누구의 쌍인지를 자세히 알 필요가 없다. 그저 몇 쌍인지 세는 것이라면 경우의 수로 갯수만 세서 곱하면 되는 것이다.
• 100 ≤ weights[i] ≤ 1,000: 원소의 범위가 수상할 정도로 좁다. 보통 일반적으로는 이렇게 좁은 구간이 나오는 경우가 잘 없다. 지문을 잘 읽었다면 해시 테이블이 필요하다는 발상이 가능하고 이렇게 구간이 좁다면 배열 자체를 해시 테이블로 쓰는 거 아닌가라는 의심을 할 수 있어야 한다.
• [100,180,360,100,270]: 이건 입출력의 예로 주어진 것인데 잘 보면 중복된 값을 허용하고 있다. 쌍의 수를 세는데 같은 값이 포함되어 있고 이에 따른 처리가 필요하다는 걸 알 수 있다. 같은 값끼리 몇 쌍이 나오는지를 따로 셀 필요가 있다는 것이고 여기에 순서를 고려하지 않으니 경우의 수를 세는 공식 nCm을 떠올려야 한다. 지금은 m=2니까 nC2 = n * (n - 1) / 2를 하면 된다. 앞으로 알고리즘 문제 풀이를 위해서 수학 공식도 여러 개 알아놔야겠다.
• long long solution(vector<int> weights): 반환형이 long long이다. 일반적으로 갯수를 세는 문제는 반환형이 int인 경우가 많은데 이건 그렇지 않다. 시간복잡도에 유의해야 할 것 같다는 생각이 본능적으로 들어야 한다. 시간복잡도 이야기를 한 김에 AI에 따르면 보통 코테에서 시간복잡도 제한을 이렇게 걸고 있다고 하니 이 제안을 참고하면 좋을 것 같다.
  • 원소의 수: ~20 / 시간복잡도 허용: 2^N
  • 원소의 수: ~500 / 시간복잡도 허용: N³
  • 원소의 수: ~5,000 / 시간복잡도 허용: N²
  • 원소의 수: ~10^6 / 시간복잡도 허용: N log N, N

#define _GLIBCXX_ASSERTIONS

#include <string>
#include <vector>

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    int arr[1001] = { 0 };
    
    for (int i = 0; i < weights.size(); ++i)
    {
        ++arr[weights[i]];
    }
    
    for (int i = 0; i < 1001; ++i)
    {
        if (arr[i] <= 0)
        {
            continue;
        }
        
        long long n1 = arr[i];
        long long n2 = arr[i] - 1;
        
        answer += n1 * n2 / 2;
        
        if (i * 2 < 1001)
        {
            n2 = arr[i * 2];
            answer += n1 * n2;
        }
        
        if (i * 3 % 2 == 0 && i * 3 / 2 < 1001)
        {
            n2 = arr[i * 3 / 2];
            answer += n1 * n2;
        }
        
        if (i * 4 % 3 == 0 && i * 4 / 3 < 1001)
        {
            n2 = arr[i * 4 / 3];
            answer += n1 * n2;
        }
    }
    
    return answer;
}