백준알고리즘 11656번 접미사 배열 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 11656
• 문제명: 접미사 배열
• 언어: C#
• 분류: 문자열, 정렬
• 비고: 

 

문제

접미사 배열은 문자열 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의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

 

풀이

접미사에서 문자열의 맨 뒤는 항상 고정적으로 나온다. 따라서 i번째 위치부터 시작해 (전체 길이 - i)번째 위치를 Substring() 함수에 넣으면 접미사를 쉽게 추출할 수 있다.

추출한 접미사들을 오름차순으로 정렬할 때는 OrderBy() 함수를 이용하면 된다.

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

// 문자열 입력을 받는다
string s = sr.ReadLine();
// 접미사를 저장할 배열
string[] suffix = new string[s.Length];

// 접미사 추출
for (int i = 0; i < s.Length; i++)
    suffix[i] = s.Substring(i, s.Length - i);
// 접미사 출력
foreach (string output in suffix.OrderBy(x => x))
    sw.WriteLine(output);

sr.Close();
sw.Close();

 

후기

이 문제는 너무나도 순조롭게 풀려서 놀랐다. 심지어 내림차순 정렬이 되게 코드를 작성한 것을 오름차순 정렬로 정정하는 과정도 너무 간단하게 해결되었다. 정답도 손쉽게 나오면서 고구마를 먹다가 사이다를 마시는 느낌을 받았다. 실력 발휘가 잘 된 듯하다. 좀더 어려운 문제도 이렇게 잘 풀리기를 원하고 있다.