BEEZI life

https://www.slideshare.net/SuhyunPark23/kucc-2022-4

문제

이렇게 numbers배열이 주어지면 각 원소들을 조합해서 가장 큰 수를 만드는 문제이다.

접근

처음 시도했던 접근 방법은 이렇다.
일단, 두 수를 비교했을 때 어떤 수가 앞에 와야 하는지 생각해봤다.

1. 맨 앞자리수가 커야 한다.
예를 들어서, 18과 2를 비교했을 때 만들 수 있는 조합은 182와 218인데
218이 더 큰 것을 보면 앞 자릿수가 커야 조합했을 때 큰 수 를 만들 수 있다.

2. 앞자리수가 같다면 마찬가지 논리로 뒷자리 수가 커야 한다.
예를 들어서, 28과 27을 비교했을 때 만들 수 있는 조합은 2827과 2728인데
2827이 더 큰 것을 보면 알 수 있다.

3. 모든 자리의 숫자가 같지만 자릿수가 다르다면, 자릿수가 같을 때까지 맨 앞의 수를 넣은 후 비교한다.
예를 들어서 382와 38을 비교했을 때,
382와 (38에 맨 앞 자릿수인 3을 붙인 383을 비교한다.
그렇게 하면 38382가 만들어지는데 이것은 다른 조합인 38238보다 더 큰 것을 알 수 있다.

4. 이렇게 해서도 모두 같으면 더 작은 수가 더 큰 조합을 만들 수 있다.
예를 들어서, 383과 38을 비교했을 때 만들 수 있는 조합은 38383과 38338인데
38383이 더 큰 것을 보면 수가 더 적은 38이 앞에 있는 상황인 것을 알 수 있다.

이렇게 해서 코드를 짜면 아래와 같다.

bool compare(const int& a, const int& b){
    string sa=to_string(a), sb=to_string(b);
    string tmp1=sa+sb, tmp2=sb+sa;
    return stoi(tmp1)>stoi(tmp2);
}

시행착오

하지만 이 코드에는 예외상황이 발생한다.

예를 들어서 [10,101,1]이 주어졌을 때 위의 논리대로 하면

1. 번으로는 모두 같고, 2. 번으로도 모두 같다.

이제 3. 번으로 비교하면 1 > (10 , 101) 순서가 된다.

이것을 4. 번으로 비교하면 1 > 10 > 101 이고, 이것으로 만든 수는 110101이 된다.

하지만, 실제로 가장 큰 수는 110110, 즉 1 > 101 > 10 순서가 된다.

깨달음

문제를 너무 복잡하게 생각했다.

이 문제는 여러 가지 수의 조합을 따져봤을 때, 가장 큰 조합을 만드는 것이다.

그렇다면 두 가지 수를 비교했을 때도 조합을 따져본 뒤, 가장 큰 조합을 만들 수 있는 배열을 만들어 주면 되는 것이다.

다시 위의 예를 들어서 101과 10을 비교한다고 했을 때

두 수로 만들 수 있는 조합 10110과 10101을 비교했을 때 10110이 더 크므로

101 > 10 순서를 만들어 주면 되는 것이다.

이것을 코드로 구현해보면 아래와 같다.

bool compare(const int& a, const int b){
    string sa=to_string(a), sb=to_string(b);
    if(sa.length()==sb.length()) return a>b;
    while(sa.length()!=sb.length()){
        if(sa.length()>sb.length()) sb.push_back(sb.front());
        if(sa.length()<sb.length()) sa.push_back(sa.front());
    }
    if(stoi(sa)==stoi(sb)) return a<b;
    return stoi(sa)>stoi(sb);
}

이렇게 하면 모든 배열을 가장 큰 수의 조합으로 만들어 줄 수 있다.

단 한 가지 예외 사항이 있는데 [0,0]이 주어졌을 경우에는 00이 출력되지만 답은 0이다.

이것을 예외 처리해주면 정답 코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(const int& a, const int& b){ /* 위와 같음 */ }

string solution(vector<int> numbers) {
    string answer = "";
    sort(numbers.begin(), numbers.end(), compare);
    if(numbers[0]==0) return "0";
    for(int i=0; i<numbers.size(); i++){
        answer+=to_string(numbers[i]);
    }
    return answer;
}

앞으로

문제가 주어졌을 때, 문제를 곧이곧대로 보는 방법도 시도해보는 연습을 해야겠다.

반열림구간 [start, end)에서의 quick sort template

// reference를 불러와서 실제 배열에도 swap의 결과를 반영한다.
void swap(int& a, int& b){
  int tmp=a;
  a=b;
  b=tmp;
}

void qsort(vector<int>& arr, int start, int end){
  // 분할된 원소가 0개이거나 1개일때까지 함수 호출
  // start+1==end일 때, 원소의 개수는 1개
  if(start+1>=end) return;

  int pivot=start; 
  // 값 설정 기준 : 첫번째 원소

  int bigger=start+1; 
  // bigger : pivot보다 큰 원소를 찾는 index
  // 값 설정 기준 : pivot + 1

  int smaller=end-1; 
  // smaller : pivot보다 작은 원소를 찾는 index
  // 값 설정 기준 : 마지막원소

  // `bigger`와 `smaller`이 교차할때 까지 pivot보다 크거나 작은 원소들을 서로 교환한다.
  while(bigger<=smaller){
    // end는 아무 원소도 가리키지 않으므로 end보다 작아야한다.
    // bigger이 가리키는 원소가 pivot이 가리키는 원소보다 작으면 계속 bigger을 키운다.
    while(bigger<end && arr[bigger]<=arr[pivot]) ++bigger;

    // smaller은 나중에 pivot과 swap해야하기 때문에 pivot의 index인 start와 같으면 안된다.
    // 역시, smaller이 가리키는 원소가 pivot이 가리키는 원소보다 크면 계속 smaller을 줄인다.
    while(start<smaller && arr[pivot]<=arr[smaller]) --smaller;

    // bigger과 smaller이 교차하면 종료한다.
    if(bigger>=smaller) break;

    // 교차하지 않았다면 서로가 가리키는 원소를 swap하고 다시 반복한다.
    swap(arr[bigger], arr[smaller]);
  }
  // 교차했다면 pivot과 smaller가 가리키는 원소를 서로 교환한다.
  // 이렇게 하면 pivot 왼쪽에는 pivot보다 작은것, 오른쪽에는 pivot보다 큰것이 위치한다.
  swap(arr[smaller], arr[pivot]);

  // pivot을 기준으로 오른쪽과 왼쪽으로 나눠서 다시 정렬을 수행한다.
  qsort(arr, smaller+1, end);
  qsort(arr, start, smaller);
}

Class 3의 문제를 모두 풀었다.

여기에서 기초적인 지식들을 많이 얻고 부족한 점들을 많이 보완할 수 있었다.

배운것 : map, set, 기초적인 문자열 다루기, Floyd-Warshall
보완한 점 : 재귀, 분할정복, 그래프문제

추가로 최근에 풀어본 프로그래머스 실력체크 Level 2도 첨부한다.

다음목표 : Class 4, Level 3

이 문제를 풀 때 쉽게 생각할 수 있는 풀이는

음수*음수->양수
양수*양수->양수

이렇게 묶어서 합을 최대로 만드는것이다.

조금 더 생각하면,
음수의 개수가 홀수개일 때,
-3, -2, -1 을 (-3 * -2) + -1로 묶을 수 있다.
여기서 0이 1개이상일경우
-3, -2, -1, 0을 (-3 * -2) + (-1 * 0)로 묶어서 -1을 없애줄 수 있다.

여기까지는 생각하기 쉽지만 한가지 간과한 것이 있다.

1은 무엇과 곱해도 손해이다. 무조건 더하는것이 낫다.
4, 3, 2, 1-> (4 * 3) + (2 * 1) = 14
                 -> (4 * 3) + 2 + 1 = 15

0과 함께 있는 경우에도 마찬가지이다.
4, 3, 1, 0-> (4 * 3) + (1 * 0) = 12
                 -> (4 * 3) + 1 + 0 = 13

이 문제를 [백준 1202] 보석도둑에서의 lower_bound를 이용한 풀이와 비슷하게 시도해보고자 한다.

lower\_bound(x): x이상의 수 중 최솟값 인데

순회강연의 문제에서는 각 강연의 endline이 주어지고, 그 endline안에만 강연을 할 수 있다.

즉 day=2일때, endlined이 2이하인 강연만 할 수 있어서 정확히 lower_bound의 정의에 반대이다.

여기서 중요한것이 정확히 lower_bound의 반대라는 점인데,

그렇다면 각 케이스에서 가장 큰 endline을 maxEndline이라고 했을 때,

endline = maxEndline - endline;

이 상태에서는 "lower_bound(x'): x'이하의 수중 최댓값"이 된다.

따라서, day=2일때, lower_bound(day)의 결과는 endline이 2 이하인 강연 중 비용이 가장 큰 것의 index가 나오게 된다.

이 풀이는 뭔가 머릿속으로는 이해가 되는데, 말로 하려니깐 정의자체가 어려운것같다.

#include <bits/stdc++>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpii;

// INT_MAX = 2^31 ~= 2.1e9
// LLONG_MAX = 2^63 ~= 9.2e18

const int MAX=(int)1e4;
pii lecture[MAX+5]; // <비용, 기간>
multiset<int> day;

int main(){
  int n;
  scanf("%d", &n);

  int nDay=0;
  for(int i=0; i<n; i++){
    scanf("%d %d", &lecture[i].first, &lecture[i].second);
    if(lecture[i].second>nDay) nDay=lecture[i].second;
  }
  for(int i=0; i<n; i++){
    lecture[i].second=nDay-lecture[i].second;
  }
  for(int i=0; i<nDay; i++) day.insert(i);

  sort(lecture, lecture+n, greater<pii>()); // 비용이 큰 순으로 정렬을 한다.

  ll answer=0;
  for(int i=0; i<n; i++){ // i는 강연의 순번, 비용이 높은것이 먼저 나온다.
    auto iter=day.lower_bound(lecture[i].second);
    if(iter!=day.end()){
      // 값을 찾았다면 비용을 더해주고, 해당 날은 제거한다.
      answer+=lecture[i].first;
      day.erase(iter);
    }
  }
  printf("%lld", answer);
  return 0;
}

이 문제는 어렵지 않은 하드코딩 문제이지만, 디버깅을 하는 과정에서 항상 놓치고 있던 것을 머릿속에 각인시키고자 글을 쓴다.

전략

내가 문제에 사용한 전략은 아래와 같다.

1. 모든 원소마다 19개의 테트로미노의 최댓값을 비교한다.

2. 테트로미노의 시작점은 최대한 좌측 상단에 있는 정사각형이다.

3. 시작점으로부터 가장 왼쪽에 있는 정사각형과의 거리에 따라서 type을 정한다.

    ->가장 왼쪽에 있는 사각형의 index가 0보다 작지 않게 하기 위해서

4. 모든 원소에 초깃값으로 매우 큰 음수값을 넣어서 경계를 신경 쓰지 않도록 한다.

이러한 전략을 적용한 테트로미노 19개의 모양은 아래와 같다.

위와 같은 전략을 사용하여 코딩을 했을 때, 대부분의 경우는 옳은 답이 나온다.

디버깅

하지만, 4번의 전략으로 오른쪽, 아래쪽 경계를 신경쓰지 않았기 때문에
주어진 배열의 크기인 n,m이 최대치인 500일 경우, 경계를 넘는 값을 참조하여 틀린 값들이 나왔다.

예를 들어, 아래와 같은 배열이 주어졌을 때

경곗값을 검사하지 않았기 때문에, 테트로미노가 아래와 같이 위치하는 경우도 생겼다.

이러한 경우들을 방지하기 위해서 처음에 잡아놓는 배열의 크기를 503(최대로 참조할 수 있는 범위) 로 늘렸고,

503의 index까지 초깃값을 -4000으로 세팅해주었다.

코드

#include <bits/stdc++.h>
#define MAX 500

using namespace std;
int a[MAX+2][MAX+2];

int type0(int i, int j){
  // 해당 행/열 반대방향으로 블럭이 없는경우
  int maxCount=0;
  int cnt;
  
  //1
  cnt = a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
  if(maxCount<cnt) maxCount=cnt;

  //2
  cnt = a[i][j]+a[i][j+1]+a[i][j+2]+a[i][j+3];
  if(maxCount<cnt) maxCount=cnt;

  //3
  cnt = a[i][j]+a[i+1][j]+a[i+2][j]+a[i+3][j];
  if(maxCount<cnt) maxCount=cnt;

  //4
  cnt = a[i][j]+a[i+1][j]+a[i+2][j]+a[i+2][j+1];
  if(maxCount<cnt) maxCount=cnt;

  //5
  cnt = a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j];
  if(maxCount<cnt) maxCount=cnt;

  //6
  cnt = a[i][j]+a[i][j+1]+a[i+1][j+1]+a[i+2][j+1];
  if(maxCount<cnt) maxCount=cnt;

  //9
  cnt = a[i][j]+a[i+1][j]+a[i+1][j+1]+a[i+1][j+2];
  if(maxCount<cnt) maxCount=cnt;

  //10
  cnt = a[i][j]+a[i][j+1]+a[i+1][j]+a[i+2][j];
  if(maxCount<cnt) maxCount=cnt;

  //11
  cnt = a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j+2];
  if(maxCount<cnt) maxCount=cnt;

  //12
  cnt = a[i][j]+a[i+1][j]+a[i+1][j+1]+a[i+2][j+1];
  if(maxCount<cnt) maxCount=cnt;
  
  //15
  cnt = a[i][j]+a[i][j+1]+a[i+1][j+1]+a[i+1][j+2];
  if(maxCount<cnt) maxCount=cnt;

  //16
  cnt = a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j+1];
  if(maxCount<cnt) maxCount=cnt;
   
  //19
  cnt = a[i][j]+a[i+1][j]+a[i+1][j+1]+a[i+2][j];
  if(maxCount<cnt) maxCount=cnt;

  return maxCount;
}

int type1(int i, int j){
  int maxCount=0;
  int cnt;
  //8
  cnt = a[i][j]+a[i+1][j]+a[i+2][j]+a[i+2][j-1];
  if(maxCount<cnt) maxCount=cnt;

  //13
  cnt = a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j-1];
  if(maxCount<cnt) maxCount=cnt;

  //14
  cnt = a[i][j]+a[i+1][j]+a[i+1][j-1]+a[i+2][j-1];
  if(maxCount<cnt) maxCount=cnt;

  //17
  cnt = a[i][j]+a[i+1][j]+a[i+1][j-1]+a[i+2][j];
  if(maxCount<cnt) maxCount=cnt;

  //18
  cnt = a[i][j]+a[i+1][j]+a[i+1][j-1]+a[i+1][j+1];
  if(maxCount<cnt) maxCount=cnt;

  return maxCount;
}

int type2(int i, int j){
  int cnt = a[i][j]+a[i+1][j]+a[i+1][j-1]+a[i+1][j-2];
  return cnt;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  for(int i=0; i<=MAX+2; i++){
    for(int j=0; j<=MAX+2; j++){
      // 최솟값을 미리 넣어놓기
      a[i][j]=-5000;
    }
  }

  int n, m;
  cin>>n>>m;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin>>a[i][j];
    }
  }

  int maxCount=0;
  int cnt;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cnt=type0(i,j);
      if(maxCount<cnt) maxCount=cnt;

      if(j-1>=0){
        cnt=type1(i,j);
        if(maxCount<cnt) maxCount=cnt;
      }

      if(j-2>=0){
        cnt=type2(i,j);
        if(maxCount<cnt) maxCount=cnt;
      }
    }
  }
  cout<<maxCount;
  return 0;
}

100솔, 골드5 달성기념!