백준 1181번 <단어 정렬> - C++

 

하... 개빡친다

실5치고 개쉬워보이는데? 로 호기롭게 도전했다가 1시간 20분동안 뚜드려맞았다.. 사고과정 점검해보자

 

처음 생각

테스트 케이스 n개

길이순으로 정렬
  - 길이저장배열을 둘까?
  - 그냥 sort 해버리면?
      - 길이 상관없이 사전순으로 저장된다
  - 길이에 대해 정렬하면서, 문자열도 같이!
  
길이 같을 땐 사전순
  - len 배열을 순회하면서, 길이가 같은 지점 chk

중복되는 원소 제거

easy한데? 로 생각했다

그런데 상상치도 못한 문제가 있었다. 기존에 작성한 코드에서는, 테스트 개수 n개의 길이가 모두 같으면 정렬 안 하고 슝 넘어가버린다. ▶▶▶ 나비효과 ▶▶▶ 출력할 때 앞의 원소랑 비교하며 중복을 제거하는 식으로 했는데, 모든 문자열의 길이가 같아버리면 정렬이 안 되니까!!! 출력할 때도 당연히 스킵당한다

      5
      a
      b
      c
      a
      b
      이면 정렬을 수행 안 하기 때문에 배열에 그대로 남아있고, 모든 원소는 직전의 원소와 다르니 중복 제거 없이 전부 출력된다

폐급짓을 해버렸다.

 

배열로 시작했는데 벡터는 쓰고싶지 않았다.(사실 쓸 줄도 모른다. 내일은 벡터 기본문제 풀 거다)

그래서 떠올린 방법이 바로바로! 일단 입력을 받은 배열에 대해, 그냥 sort를 진행한다. 사전순으로 진행되기에, 우리의 의도와는 맞지 않는다. 그치만 이렇게 진행하면 문자 하나끼리는 다닥다닥 붙는다. 이대로 버블정렬 수행하면 제자리에 잘 맞아 들어간다. 정렬된 배열에 대해 길이를 저장하는 len배열도 새로 세팅해준다.

#include <algorithm>
#include <iostream>
#include <math.h> //C
#include <cmath> //C++
#include <string>

using namespace std;

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


  int n;
  cin >> n;
  int len[20000] = {};
  string arr[20000];
  for(int i=0;i<n;i++){
    cin >> arr[i];
  }

  sort(arr, arr+n);
  for(int i=0;i<n;i++){
    len[i] = arr[i].length();
  }
  
  for(int j=0; j<n-1;j++){
    for(int i=0;i<n-j-1;i++){
      if(len[i] > len[i+1]){ 
        swap(len[i], len[i+1]); 
        swap(arr[i], arr[i+1]);
      }
    }
  }

  //cout << '\n' << '\n';
  
  // for(int i=0;i<n;i++){
  //   cout << arr[i] << " ";
  // }
  //cout << '\n';
  
  int cnt=0;
  for(int i=0;i<n-1;i++){
    if(len[i] == len[i+1]) {
      cnt ++;
      }
    else {
      //cout << "now i is " << i << ", cnt is " << cnt << '\n';
      //cout << "from " << i-cnt << " to " << i << '\n';
      sort(arr + (i - cnt), arr + i+1); cnt=0;}
  }
  

  
  //cout << '\n';
  cout << arr[0] << '\n';
  for(int i=1; i < n;i++){
    if(arr[i-1] != arr[i]) 
      cout << arr[i] << '\n';
  }
  return 0;
}

코드가 너무 치덕치적 짜여있다. 내 짬에 효율 따질 건 아니지만, 너무 더럽긴 하다

 

코드설명(없으면 내가 다시봐도 이해 못할 듯)

  int n;
  cin >> n;
  int len[20000] = {};
  string arr[20000];
  for(int i=0;i<n;i++){
    cin >> arr[i];
  }

  sort(arr, arr+n);
  for(int i=0;i<n;i++){
    len[i] = arr[i].length();
  }

배열의 원소를 하나씩 입력받고, 사전순으로 정렬(sort함수 사용)한다. 이후 정렬된 배열에 대해 각 원소의 길이를 저장한다.

 

  for(int j=0; j<n-1;j++){
    for(int i=0;i<n-j-1;i++){
      if(len[i] > len[i+1]){ 
        swap(len[i], len[i+1]); 
        swap(arr[i], arr[i+1]);
      }
    }
  }

버블정렬을 수행한다. 바로 뒤의 원소와 자신의 원소를 비교하면서, 내(현재)가 더 길이가 길면 뒤에 친구랑 값을 바꾼다. 물론 len배열도 업데이트 해줘야 한다.

.

  int cnt=0;
  for(int i=0;i<n-1;i++){
    if(len[i] == len[i+1]) {
      cnt ++;
      }
    else {
      //cout << "now i is " << i << ", cnt is " << cnt << '\n';
      //cout << "from " << i-cnt << " to " << i << '\n';
      sort(arr + (i - cnt), arr + i+1); cnt=0;}
  }

문제의 치덕치덕 부분이다. 배열 전체를 돌면서, 지금 원소랑 다음 원소의 길이가 같으면 cnt를 1씩 증가시킨다. 그게 아니라면, 그 구간을 정렬한다.

 

무슨 말이냐면,

1 1 1 2 2 2 2 4 4

이렇게 정렬돼 있을 때,

i = 0, len[0]=1, len[1]=1 → cnt = 1

i = 1, len[1]=1, len[2]=1 → cnt = 2

i = 2, len[0]=1, len[1]=2 이땐 길이가 다르지!! 그러니까 실제 배열에서 0번째부터 1번째 원소만 정렬을 해준다.

길이순으로는 이미 정렬이 되어있기 때문에, 길이가 똑같은 구간을 사전순으로 정렬해준다는 뜻이다.

sort(arr + (i - cnt), arr + i+1); cnt=0;}

 

arr + i - cnt니까 arr[0]을 의미, arr + i + 1은 arr[3]을 의미한다. 즉, 0~2번째 인덱스 값을 정렬하라는 소리다. 이러면 맞아떨어진다.

 

  cout << arr[0] << '\n';
  for(int i=1; i < n;i++){
    if(arr[i-1] != arr[i]) 
      cout << arr[i] << '\n';
  }
  return 0;

중복을 제거하는 부분이다. 여기도 역시 치덕치덕하다

맨 첫 번째 원소는 앞에 뭐가 없으니 무조건 출력해 준다. 1번째 인덱스부터 비교를 시작한다. 지금 나랑 앞에 니랑 비교했을 때! 다른 값이면 출력한다. (=같은 값이면 아무것도 안 한다 = 중복 제거!) 이것을 끝까지 수행한다. 끝

 

새로운 개념에 대해 배우기 싫다고 흐린눈했더니, 대참사가 날 뻔했다. 내일은 반드시 벡터에 대해서 공부해서 벡터 기본문제를 다루겠다. 그리고 이후 의식적으로 벡터로 문제를 해결해 보려 노력하겠다. 이상