[Baekjoon] 11656 접미사 배열(파이썬/자바스크립트/NodeJS)

이번 문제는 아래 링크에서 풀어볼 수 있습니다.

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

---

정답 코드

나의 답안

import sys

data = sys.stdin.readline().rstrip()


def mySolution(data):
    result = list()

    for i in range(len(data)):
        tmp = ""
        for j in range(i, len(data)):
            tmp += data[j]
        result.append(tmp)

    result.sort()

    for i in result:
        print(i)


mySolution(data)

슬라이싱 활용

import sys

data = sys.stdin.readline().rstrip()


def answer1(data):
    result = []

    for i in range(len(data)):
        result.append(data[i:])

    for i in sorted(result):
        print(i)


answer1(data)

자바스크립트/NodeJS Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim();

const solution1 = (data) => {
    let result = [];

    for (let i in data) {
        let tmp = '';
        for (let j = i; j < data.length; j++) tmp += data[j];
        result.push(tmp);
    }

    for (let i of result.sort()) console.log(i);
};

console.log('solution1');
solution1(input);

const solution2 = (data) => {
    let result = [];
    for (let i in data) result.push(data.split('').splice(i).join(''));
    result.sort().forEach((el) => console.log(el));
};

console.log('solution2');
solution2(input);

---

문제 풀이

 입력 받은 문자열을 for 반복문으로 순회하며 i번 인덱스부터 끝까지 정답 리스트에 붙여 넣고 순서대로 출력하면 되는 문제이다. 관건은 리스트에 붙여 넣는 문자열의 길이를 어떻게 순차적으로 줄여나가는가 하는 점이다.

 나의 경우 이중 for문을 활용했는데 다른 사람들의 답안을 찾아보니 문자열 슬라이싱을 활용하면 훨씬 더 간단하게 구현이 가능했다. 어떻게든 잘라놓은 문자열을 모아둔 정답 리스트를 sorted 메서드 혹은 sort 메서드를 활용해 출력하면 된다.

 sorted 메서드와 sort 메서드의 큰 차이점은 원본 리스트를 수정하느냐 하는 점이다. sort 메서드는 원본 리스트 자체를 정렬하는 메서드이고 sorted 메서드는 매개변수로 입력 받은 리스트를 정렬한 새로운 리스트를 반환하는 메서드이다.

---

함께 보기

https://o-sae.tistory.com/77

[백준][파이썬] 11656. 접미사 배열

https://blockdmask.tistory.com/466

[python] 파이썬 정렬 sorted 함수 정리 및 예제