pascal 1431번 시리얼 번호 (백준)

var n,i,j,k,g,x,y,w:int64;a,b:array[0..49]of int64;s:array[0..49]of string;z:string;
begin
readln(n);
n-=1;
for i:=0 to n do readln(s[i]); //문자열 n개 입력 받고 문자열 배열에 저장
for i:=0 to n do begin //문자열 한개씩 길이와, 숫자의 합을 구해줌
 a[i]:=length(s[i]); //길이
 b[i]:=0; //숫자의 합을 담을 배열을 초기화
 for j:=1 to a[i] do if (s[i][j]>='0') and (s[i][j]<='9') then b[i]+=ord(s[i][j])-48; //숫자라면 그 값을 누적해줌
end;

//shell sort
g:=(n+1) div 2;
while(1=1) do begin
if(g mod 2)=0 then g+=1;
for i:=g to n do begin
x:=a[i];y:=b[i];z:=s[i];j:=i-g;
while j>=0 do begin
w:=0;
if a[j]>x then w:=1 //앞에 있는 것이 더 길이가 길다면
else if a[j]=x then begin  //길이는 같고
 if b[j]>y then w:=1 //앞에 있는 것이 더 숫자의 합이 크다면
 else if b[j]=y then begin //숫자의 합도 같고
  for k:=1 to a[j] do begin //문자들을 한개씩 비교 (차이가 발생할때 까지)
   if s[j][k]>z[k] then begin w:=1;break;end //만약 앞에 있던 문자열의 문자가 더 사전순으로 뒤에 있다면
   else if s[j][k]<z[k] then break; //만약 앞에 있던 문자열의 문자가 더 사전순으로 앞에 있다면 swap을 하지 않음. 종료.
  end;
 end;
end;
if w=1 then begin a[j+g]:=a[j];b[j+g]:=b[j];s[j+g]:=s[j];end  //만약 swap (w=1) 해야한다면 swap
else break; //그렇지 않다면 반복 종료
j-=g; //swap 한 경우 더 앞에있는것을 탐색하러 감
end;
a[j+g]:=x;b[j+g]:=y;s[j+g]:=z; //shell sort에서 중요한 부분
end;
if g=1 then break; 
g:=g div 2;
end;

for i:=0 to n do writeln(s[i]); //결과 출력
end.

 

풀이 : 구현, 정렬

 

1. 문자열을 입력받고, 각 문자열의 길이, 숫자의 합을 구했습니다.

2. shell sort을 정렬 기준에 맞추어 정렬했습니다.

2.1 길이  (작은것이 앞으로)

2.2 길이가 같다면 숫자의 합 (작은것이 앞으로)

2.3 위의 두 조건이 모두 같다면 사전순 상 더 작은것이 우선이 되도록

3. 정렬한 결과를 반복문으로 출력했습니다.