[백준 BOJ] 11656번 접미사 배열 (C++/cpp)

문제 설명

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

11656번: 접미사 배열

 

접근 방법 - 문자열에 대한 정렬 기초 문제

백준의 11656번 문제는 문자열 정렬에 있어 기초적인 부분을 다루고 있는 문제이다.

해당 문제는, 입력받은 문자열의 접미사들에 대하여 정렬을 수행하여 순차적으로 출력해야 하는 문제이다.

접미사에 대한 개념을 모르더라도, 문제의 설명만 잘 읽어본다면 어떤 의미인지 얼추 알 수 있을 것이다.

필자는 해결하는 순서를 부분 문자열 만들기 -> 정렬 순으로 생각하였는데, 여기서 substr()이라는 함수를 사용하였다.

substr() 함수를 사용하는 방법은 아래와 같으니, 이러한 방법으로 해결할 때 참고하면 좋을 것이다.

st.substr(start_substring, length_substring);
// 자세한 사용법은 아래의 코드를 참고해보길 바란다.

문자열 함수와 정렬 함수를 어느 정도 다룰 수 있다면, 어렵지 않게 해결할 수 있을 것이라 예상된다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 접미사들을 저장할 배열(arr)을 전역 변수로 미리 선언해둔다.

 

2) 문자열(st)을 입력받는다.

 

3) st의 길이만큼 반복문을 실행하여 아래의 연산을 취한다.

(이때, 제어 변수 i는 0부터 시작하여 st.length() 값의 이전까지 하도록 한다.)

- substr()를 이용하여 st에 대한 부분 문자열(sub)을 생성하도록 한다.

- 저장된 sub를 arr에 저장하도록 한다.

(ex) 입력값이 "baekjoon"일 때 (length의 값은 8)
- i=0일 때, 인덱스 0부터 시작하여 길이가 8인 부분 문자열 생성 => beakjoon (arr[0]에 저장)
- i=1일 때, 인덱스 1부터 시작하여 길이가 7인 부분 문자열 생성 => eakjoon (arr[1]에 저장)
- i=2일 때, 인덱스 2부터 시작하여 길이가 6인 부분 문자열 생성 => akjoon (arr[2]에 저장)
...
- i=7일 때, 인덱스 7부터 시작하여 길이가 1인 부분 문자열 생성 => n (arr[7]에 저장)

 

4) 부분 문자열 저장을 모두 끝내었다면, sort()를 이용하여 arr에 대하여 정렬을 수행한다.

 

5) 반복문을 이용하여, 정렬이 완료된 arr의 값들을 순차적으로 출력한다.

 

6) 출력이 완료되었다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <algorithm>
#include <string>
#define endl '\n'
using namespace std;

//백준 11656번 코드
string arr[1001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	string st;
	cin >> st;

	for (int i = 0; i < st.length(); i++) {
		string sub = st.substr(i, st.length() - i);
		arr[i] = sub;
	}
	sort(arr, arr + st.length());

	for (int i = 0; i < st.length(); i++) {
		cout << arr[i] << endl;
	}
}

 

제출 결과

(2022.11.21 백준 11656번 문제 제출 결과)