[백준] 11656번: 접미사 배열 (C)

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

11656번: 접미사 배열

문제

접미사 배열은 문자열 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

 

• 풀이
• 예상보다 훨씬 고통받은 문제였습니다.
  • 그 이유로는 첫번째로 제가 배열에 대한 개념이 부족했었고
  • 두번째로는 처음으로 접한 자료구조개념(?)이었던 것 같습니다. 문제를 푸는 과정 중 버블 정렬이라는 것을 공부했는데 설명을 보니까.. 뭐 그리 많이 쓰는 정렬방식은 아니라고 하네요.. 2학년때 자료구조 배우니까 나중에 좀 더 자세히 배울 수 있지 않을까 생각합니다.

 

• 단어를 배열 S에 입력받고 이차원 배열 arr에 각 접미사를 저장했습니다. 

 

• 예를 들어 banana라는 단어를 S에 입력했다면 arr 배열에는 
  • a      
  • n a
  • a n a
  • n a n a
  • a n a n a
  • b a n a n a
• 이런식으로 저장됩니다.

 

• 이제 각 접미사들을 알파벳 순으로 정렬해야합니다. 위 banana 같은 경우는 다음과 같습니다.
  • a
  • a n a
  • a n a n a
  • b a n a n a
  • n a
  • n a n a

 

• strcmp함수를 이용해서 배열 arr에서 각 행을 비교합니다. 
  • 만약 arr[n -1]에 있는 문자열이 arr[n]에 있는 문자열보다 크다면 ( > 1) arr[n-1]과 arr[n]을 스왑.
  • 크다라는 기준은 아스키코드.

 

• 여담
  • 이차원 배열이 다음과 같이 되어있을 때 (배열이름은 arr로 가정),

  • H	E	L	L	O
    H	E	L	L
    H	E	L
    H	E
    H

  • printf("%s", arr[2])를 하면 HEL 이 출력됩니다.  

    • H	E	L	L	O
      	E	L	L	O
      		L	L	O
      			L	O
      				O

    • 하지만 다음과 같이 되어있는 경우 printf("%s", arr[2])를 해도 LLO는 출력되지 않더군요 이차원 배열에서 세로 인덱스만 사용해서 출력할 경우, 각 줄의 0번째 index에는 어떤 값이 초기화 되어있어야 하는 것 같습니다.

 

 

 

 

 

본 게시물은 제가 공부한 내용을 올린 글이라 내용이 틀리거나 오류가 있을 수도 있습니다. 만약 그럴 시 jaewonahn1234@gmail.com으로 피드백해주시면 감사하겠습니다