[백준] 1431. 시리얼 번호 (C++)

1431번: 시리얼 번호

Bubble Sort를 사용해 풀이하였다.

// 글자의 자리 수 합을 구하는 함수 
int s_number(string s) 
{
  int num = 0;

  for(int i=0; i<s.size(); i++)
  {
    if(48 <= s[i] && s[i] <= 57)
      num += s[i] - 48;
  }

  return num;
}

int main()
{
  int n; // 초기 입력 n
  string s;
  vector<vector<string>> store_s ; //문자열들을 저장하는 2차원 벡터
  vector<vector<int>> store_n ; //문자열들의 자리수 합을 저장하는 2차원 벡터

  for(int i=0; i<50;i++) //2차원 벡터 생성
  {
    vector<string> v1;
    vector<int> v2;
    store_s.push_back(v1);
    store_n.push_back(v2);
  }

  cin >> n; 
  for(int i=0; i<n; i++)
  { 
    cin >> s;
    store_s[s.size()-1].push_back(s); // 시리얼번호 저장 
    store_n[s.size()-1].push_back(s_number(s)); 
    // 시리얼 번호에 해당하는 자리수합 저장
  }



  
   for(int i=0; i<50; i++) //글자 길이가 50까지 이므로 50번 반복
    // Bubble Sort로 글자수에 따른 시리얼 번호 정렬
    for(int j=0; j<store_s[i].size(); j++)
    { 
      for(int k=0; k<store_s[i].size()-j-1; k++)
      { 
        string temp;
        int tmp;
        // 조건 2번에 따른 정렬
        if(store_n[i][k] > store_n[i][k+1])
        { 
          // 위치한 시리얼의 위치를 바꾼다
          temp = store_s[i][k]; 
          store_s[i][k] = store_s[i][k+1]; 
          store_s[i][k+1] = temp;
          // 위치한 시리얼의 자리수 합을 바꾼다
          tmp = store_n[i][k]; 
          store_n[i][k] = store_n[i][k+1]; 
          store_n[i][k+1] = tmp;
        }
        // 조건 3번에 따른 정렬
        else if(store_n[i][k] == store_n[i][k+1] && store_s[i][k] > store_s[i][k+1])
        // 위치한 시리얼의 위치를 바꾼다
        // 자리수 합은 같으므로 바꿀 필요는 없다 
        {
          temp = store_s[i][k]; 
          store_s[i][k] = store_s[i][k+1]; 
          store_s[i][k+1] = temp;
        }
        
      } 
    }


 // 출력
  for(int i=0; i<50; i++)
      for(int k=0; k< store_s[i].size(); k++)
        cout << store_s[i][k] << endl;
  

	return 0;
}