IGT의 RGB에 관한 필기시험 문제

제목: 하나의 문자열은'R','G','B'로만 구성되어 있는데 어떻게 모든'R'을 앞에 나타내고 모든'G'가 중간에 있고 모든'B'가 마지막에 있습니까?
요구 사항: 요구 공간의 복잡도는 O (1) 이고 문자열 그룹을 한 번만 훑어볼 수 있습니다
사고방식: 세 개의 커서 i, j, k 유지
i는 시작을 가리키고 j는 끝을 가리키며 각각 R, B를 삽입하는 데 쓰인다
k는 역주행에 사용되며 R이 발견되면 앞의 i가 가리키는 대상과 교환하고 i가 뒤로 이동한다.B가 발견되면 뒤에 있는 j가 가리키는 대상과 교환하고 j가 앞으로 이동합니다
k와 j가 만나면 멈춘다

  
  
  
  

   
   
   
   
#include<iostream>  
   
   
   
   
using namespace std;  
   
   
   
   
void f(char * str)  
   
   
   
   
{    
   
   
   
   
    int length=strlen(str);  
   
   
   
   
    int i=0;  
   
   
   
   
    int j=length-1;  
   
   
   
   
    int k=0;  
   
   
   
   
    while(k<=j)  
   
   
   
   
    {  
   
   
   
   
    //   R ，  i  ，i  ；  
   
   
   
   
        if(str[k]=='R')  
   
   
   
   
        {  
   
   
   
   
            char tmp=str[i];  
   
   
   
   
            str[i]=str[k];  
   
   
   
   
            str[k]=tmp;  
   
   
   
   
            i++;  
   
   
   
   
          
   
   
   
   
        }  
   
   
   
   
        // B ，  j ，j   
   
   
   
   
        else if(str[k]=='B')  
   
   
   
   
        {  
   
   
   
   
            char tmp=str[j];  
   
   
   
   
            str[j]=str[k];  
   
   
   
   
            str[k]=tmp;  
   
   
   
   
            j--;  
   
   
   
   
        }  
   
   
   
   
        else 
   
   
   
   
            k++;  
   
   
   
   
    }  
   
   
   
   
}  
   
   
   
   
 
   
   
   
   
void main()  
   
   
   
   
{  
   
   
   
   
    char str[]="GRGBRBGBBRRGBRBG";  
   
   
   
   
    cout<<str<<endl;  
   
   
   
   
 
   
   
   
   
    f(str);  
   
   
   
   
    cout<<str<<endl;  
   
   
   
   
}