[알고리즘] 백준알고리즘 11656번 접미사 배열

안녕하세요 감자 코딩 & 감자 개발자입니다. 이번에 살펴볼 문제는 11656번 문제입니다. 바로 접미사 배열을 활용하는 문제인데요. 문자열을 토큰을 잘 잘라내어 정렬까지 할 수있냐하는 문제입니다. 

문제 링크

https://www.acmicpc.net/problem/11656

---

접미사 배열 성공

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초 256 MB 4372 2701 2192 63.555%

문제

접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다.

baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다.

문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다.

출력

첫째 줄부터 S의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

예제 입력 1 

baekjoon

예제 출력 1 

aekjoon

baekjoon

ekjoon

joon

kjoon

n

on

oon

---

이번문제는 얼마나 내가 C++ 잘 함수를 알고있느냐에 따라 구현하는 시간도 달라질것이고, 푸는 방식도 달라진다고 생각을 했습니다. 그럼 바로 문제풀이에 들어가보죠.

문제 해결 방식

1) 접미사 배열이란? 문자열의 S의 모든 접미사를 사전순으로 정렬해놓은 배열이라고 합니다.

 말 그대로 입력한 문자열이 접미사를 사전순으로 정렬하라는 문제입니다. 그 문자열은 소문자이여야 한다고하네요.

(S <=1000 범위)입니다.

2) 일단 가장 먼저 문자열 string을 입력을 받습니다.

그리고 접미사로 만들기위해서는 

예를 들어 제가 string값을 baekjoon이라고 입력을했다고 가정하겠습니다.

접미사를 만들기위해서는 이렇게 문자열을 잘라내야하겠지요? 이상태에서 사전순으로 정렬을 해야된다는 말입니다.

baekjoon
aekjoon
ekjoon
kjoon
joon
oon
on
n

이것을 사전순으로 정렬을 하게 된다면 ?

aekjoon
baekjoon
ekjoon
joon
kjoon
n
on
oon

이형태가 나와야합니다. 그렇다면? 사전순으로 정렬하려면 맨앞에 있는 값에 따라 a-z까지의 순으로 정렬이 될수 있겠군요.

3)입력받은값들을 저는 C++에 함수인 strsub함수를 사용하려고 합니다.

strsub(a,b)함수에 대해서 간략히 말씀드리자면

a = 시작하는 문자열 인덱스

b = 마지막 문자열 인덱스

이렇게 문자열을 내가 원하는대로 잘라낼 수 있습니다.

지금 우리가 잘라내는 형식으로 자르기 위해서는

* 시작지점 0으로 부터 string size만큼(값 변동)  

* 마지막 지점 string size만큼(값 변동X) 이 되어야합니다. 

이렇게 잘라진값들을 이제 string 배열에다가 저장을 하였습니다. 

4) 그리고 이제 사전순으로 정렬을 해보아야겠죠? 어떻게 하시고싶으신가요? 저는 c++에서 제공하는 sort함수를 사용하려고 합니다. 뭐 직접 구현해도 되지만, C++에서 편하게 제공해주는게 있기때문에 사용을 하였구요. 직접 정렬을 해주셔도 됩니다만, 전 편하게 가겠습니다.

sort(a,b)함수에 대해서 간략히 말씀드리면 

a =시작점, 시작하는 문자열 주소(포인터점)

b = 도착점, 시작하는 문자열 주소 + 입력받은 문자열의 개수 로 지정을 해주게 되면 현재시작하는 주소점에서 부터 입력받은 문자열을 비교하여 사전순으로 정렬하게 됩니다. 저는 string 배열을 만들어서 그 안에 저장하였습니다. 

5) 마지막으로 정렬된 배열을 출력해주면 문제풀이는 끝이나게됩니다. 쉽쥬?

---

코드 리뷰 

//

//  11656(접미사배열).cpp

//  beakjoon_algorithm

//

//  Created by kgh on 22/12/2018.

//  Copyright © 2018 kgh. All rights reserved.

//

#include <stdio.h>

#include <iostream>

#include <algorithm>

using namespace std;

int main(void){

    

    string str;

    string result[1000];

    cin >> str;

    // substr을 사용하여 하나씩 늘려가면서 접미사 저장

    for(int i=0; i<str.size(); i++){

        result[i] = str.substr(i,str.size());

    }

    // #include <algorithm>, sort()함수의 첫번째 파라미터 = 시작점 포인터지점(주소) , 두번째 파라미터 = 도착지 포인터지점(주소)+문자열개수(str.size)

    sort(result,result+str.size());

    

    // 저장된 접미사값 sort된값을 사용하여 정렬

    for(int i=0; i<str.size(); i++){

        cout << result[i] << endl;

    }

    

}

---

substr()함수로 접미사를 저장시켜주고, sort()함수로 사전순으로 정렬을 해주고, 마지막으로 출력까지 시켰습니다. C++함수를 얼마나 아느냐에따라 구현시간이 달라질 수있었던 문제였고, C언어에서 자주 쓰이던 string Tokenizer를 C++에서는 쉽게 사용이 가능하다고 생각을 했습니다. C,C++은 항상어렵습니다 

이상 감자 코딩 & 감자개발자 11656접미사 배열 리뷰를 마치겠습니다.

감사합니다 :)