코딩노트

LECTURE - 알고스팟

문제 : https://algospot.com/judge/problem/read/LECTURE

시간 제한 : 5초

메모리 제한 : 65536 kb

 

 이 문제는 각 2글자 짜리 단어들로 끊어서 배열에 저장한 후 이를 모두 정렬해서 해결 할 수 있습니다. 이 풀이는 너무 간단하므로 따로 2글자씩 끊어서 저장하는 과정을 사용하지 않은 풀이를 설명합니다. 

 그러기 위해서는 아래의 테크닉을 이해할 필요가 있습니다.

 두 글자짜리 단어  w1과 w2를 비교하는 방법은 각 단어의 첫 글자를 비교하고, 첫 글자가 동일하면 두 번째 글자를 비교해야합니다. 이런 과정은 쓸대없이 코드가 길어지게 하므로, char가 1바이트임을 이용하여 간단하게 수식으로 비교하는 방법을 알아봅시다.

int main(){
    string w1 = "ab";
    string w2 = "ac";
    
    /* 방법 1 */
    if(w1[0] < w2[0] || //첫 글자가 다르거나 
        (w1[0] == w2[0] && w1[1] < w2[1]) ) //첫 글자는 같은데 두번째가 다르면
    {
        //w1이 w2보다 사전순으로 앞선다.
    }
    
    /* 방법 2 */
    int iw1 = (w1[0] << 8) + w1[1];
    int iw2 = (w2[0] << 8) + w2[1];
    if(iw1 < iw2)
    {
        //w1이 w2보다 사전순으로 앞선다. 
    }
}

 어차피 각 char 문자는 1byte의 정수값을 가지고, 이 값의 대소관계는 알파벳의 대소관계와 같습니다. 그러므로 두 글자를 바이트로 변환해서 이어붙이게 되면, 한 번에 두 글자의 값을 통해 대소관계를 비교할 수 있습니다.

 

 

[풀이]

 문자열의 최대길이는 1000입니다. 즉 길이 2짜리 단어가 500개 들어올 수 있다는 뜻입니다.

 단어의 수 N = 500, 단어의 길이 L = 2라고 두면, 총 500개의 단어를 정렬해야하고 두 단어를 비교할 때에는 최대 L번의 비교가 필요합니다.

 즉 만약 느린 정렬들(버블정렬, 삽입정렬 등)을 사용해도 O(N*N*L) = 약 50만 이하의 연산이 나오므로 충분히 가능합니다. 현재 알고있는 정렬기법이 느린 정렬밖에 없어도 풀 수 있게 됩니다. 아래의 코드는 버블 정렬을 이용하여 해결 한 코드입니다. 

#include<string>    //string사용법은 검색..
#include<algorithm> //swap()이 정의되어있음 
using namespace std;
void sort_lecture(string &s)
{
    int n = s.length();
    for(int i=0; i<n; i+=2)
    {
        for(int j=0;j<(n-i-1);j+=2)
        {   //두 글자를 한 정수로 묶어버리기
            //char은 8비트, int는 32비트여서 가능
            //'a'와 'b'를 이어붙인 "ab"는 (('a'<<8) + 'b')
            int front = (s[j] << 8) + s[j+1]; //앞의 두 글자
            int back = (s[j+2] << 8) + s[j+3];//뒤의 두 글자
            if( front > back) //이어 붙였으므로 사전순으로 비교 가능
            {
                swap(s[j], s[j+2]);
                swap(s[j+1], s[j+3]);
            }
        }
    }
}

 

 사실 이 문제는 N이 500이하이기에 O(N*N)의 시간복잡도를 가지는 정렬로도 풀 수가 있었습니다.

 만약 N이 커지게 된다면 결국 정렬을 O(N*logN) 정렬 알고리즘들 이나 혹은 O(NL)을 가지는 Radix Sort를 사용해야 합니다. 이 문제를 Merge Sort를 이용해 구현해보시길 추천해드립니다. 아주 직관적이고 이 문제에 적용하기 좋은 정렬 알고리즘입니다. 단, 이 문제가 2글자씩 묶여서 움직이는 특성상 조금 개량이 필요합니다. 위키피디아 등 자료등을 참고하여 머지소트를 이해하시고, 이 문제에 맞게 개량해보시길 바랍니다.

 어려우신 분은 아래의 저의 코드를 참고하시길 바랍니다.

#include<string> //string을 위해
using namespace std;

string temp; //merge sort에 필요한 buffer
void ms_lecture(string &s, int l, int r)
{
    if( l+1>= r ) return; //1단어만 있는 경우 비교할 필요 없다.
    int mid = (l+r)/2 ;   //중간 지점을 계산한다.
    if( (mid&1) == 0 ) 
        mid --; //중간 지점은 항상 홀수여야 한다. (단어가 2글자)
    ms_lecture(s, l, mid); //왼쪽 반을 정렬
    ms_lecture(s, mid+1,r);//오른쪽 반을 정렬 
    int lp=l, rp=mid+1, i=l; //정렬된 두 파트를 합치는 작업
    while(lp < mid && rp < r)
    {
        int lword = (s[lp] << 8) + s[lp+1]; //앞의 두 글자 
        int rword = (s[rp] << 8) + s[rp+1]; //뒤의 두 글자
        if(lword<=rword)
        {
            temp[i++]=s[lp++];
            temp[i++]=s[lp++];
        }else
        {
            temp[i++]=s[rp++];
            temp[i++]=s[rp++];
        }
    }
    while(lp<=mid) temp[i++] = s[lp++];
    while(rp<=r) temp[i++] = s[rp++];
    //버퍼에 저장된 결과를 실제 문자열에 반영한다.
    for(i=l;i<=r;i++)
        s[i] = temp[i];
}

void sort_lecture(string &s)
{ // 이 함수를 호출합니다.
    temp.resize(s.length());
    ms_lecture(s, 0, s.length()-1);
    temp.clear();
}

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
코딩몬스터
현재 버전
선택 버전
graphittie 자세히 보기