숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다.
다음은 나쁜 수열의 예이다.
다음은 좋은 수열의 예이다.
길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.
입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.
첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.
7
1213121
일단 조건은, 반복적 규칙이 연속적으로 나와서는 안 된다.
12312323을 군집화하면, (123)(123)23, 1231(23)(23)이라는 2가지 경우의 수가 있다.
부분을 보자. 123123
123 / 123
Left: 123, Right: 123
("123" == "123") == true
23 / 13
Left: 23, Right: 13
("23" == "13") == false
좋은 수열은 substring에서 중간을 기준으로 서로 가장 같은 길이의 서브스트링을 추출해 좌측과 우측이 동일한 l == r인 것이 존재하지 않아야 한다는 것이다.
그리고 이러한 비교는 재귀적으로 돌아갈 것이다.
123 -> 12, 23 -> (1,2), (2,3)과 같은 형태이다.
조금 더 비유적으로 설명해보자. 좋은 막대, 나쁜 막대라고 해 보자.
좋은 수열의 검증 방법을 생각해 보자. 문자열의 끝부터 최소 길이부터 비교해 보도록 하자.
-> idx[6] == 2, idx[7] == 3
Left: 2, Right: 3
( "2" == "2" ) == false
| index | 0 | 1 | 2 | 3 | '4' | '5' | "6" | "7" |
|---|---|---|---|---|---|---|---|---|
| value | 1 | 2 | 3 | 1 | 2 | 3 | 2 | 3 |
'Left': 23, "Right" : 23
( “23” == “23” ) == true
Left: 1 Right: 2 Left: 2 Right: 1 Left: 1 Right: 2 Left: 1 Right: 3 어떤 것도 좌우가 일치하지 않는다.
Left: 12 Right: 13
Left: 3 Right: 1
Left: 21 Right: 31
Left: 1 Right: 2
Left: 21 Right: 31
그리고 유의할 점은, 재귀 호출은 순차적으로 출력되지 않으므로 로깅으로 흐름을 따라가는 것이 제한적이다.
9
Left: 1 Right: 2
Left: 2 Right: 1
Left: 1 Right: 2
Left: 1 Right: 3
Left: 12 Right: 13
Left: 3 Right: 1
Left: 21 Right: 31
Left: 1 Right: 2
Left: 13 Right: 12
Left: 121 Right: 312
Left: 2 Right: 1
Left: 31 Right: 21
Left: 213 Right: 121
Left: 1 Right: 2
Left: 1 Right: 3
Left: 12 Right: 13
Left: 131 Right: 213
Left: 2 Right: 3
Left: 31 Right: 23
Left: 213 Right: 123
Left: 3 Right: 1
Left: 12 Right: 31
Left: 131 Right: 231
Left: 1213 Right: 1231
Left: 1 Right: 2
Left: 23 Right: 12
Left: 1 Right: 3
Left: 23 Right: 13
Left: 312 Right: 313
Left: 2131 Right: 2313
Left: 3 Right: 2
Left: 12 Right: 32
Left: 131 Right: 232
Left: 1213 Right: 1232
Left: 1 Right: 3
Left: 3 Right: 2
Left: 21 Right: 32
Left: 2 Right: 3
Left: 1 Right: 3
121312313
이와 같이 로그를 갖는다. 일부 순서가 뒤바뀌곤 한다.
for(int i = 1; i <= len / 2; i++) 지점에서 등호를 써야 적확 answer != “” (혹은!answer.equals(“”)) 에서 논리 부정을 누락하면 안 된다. 오탈자나 나기 좋은데, 만약 부등호가 아니라면 알고리즘 수행이 되기도 전의 첫번째 호출에서 아무 동작도 하지 않고 함수가 끝난다.
import java.io.*;
import java.util.*;
public class Main {
static String answer = "";
static int maxCheckNumber = 3;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int len = Integer.parseInt(br.readLine());
String s = "";
createString(s, len);
bw.write(answer);
bw.flush();
}
static boolean checkValidString(String s) {
int len = s.length();
for(int i = 1; i <= len / 2; i++) {
int size = len - i * 2;
String suffix1 = s.substring(len - i, len);
String suffix2 = s.substring(len - 2 * i, len - i);
if (suffix1.equals(suffix2)) {
return false;
}
}
return true;
}
static void createString(String s, int len) {
if(!checkValidString(s)) return;
if(!answer.equals("")) return;
if(s.length() >= len) {
answer = s;
}
for(int i = 1; i <= maxCheckNumber; i++) {
createString(s+Integer.toString(i), len);
}
}
}
Java에서 등호를 이용한 스트링 비교는 권장되지 않는다. equals 등을 이용하여 비교하는 것이 보편적이다.
function inputLength() {
let fs = require('fs')
let input = fs.readFileSync('/dev/stdin').toString().trim();
return Number(input);
}
let answer = "";
let n = 0;
let maxCheckNum = 3;
function verify(s) {
for(let i = 1; i <= s.length / 2; i++) {
let size = s.length - i * 2;
if(s.slice(size, size+i) === s.slice(size+i, size+i*2)) {
return false;
}
}
return true;
}
function goodString(s) {
if(!verify(s) || answer !== "") {
return
}
if(s.length === n) {
answer = s
return
}
for(let i = 1; i <= maxCheckNum; i++) {
goodString(s+i)
}
}
function main() {
n = inputLength()
goodString("")
console.log(answer)
}
main()
=== 비교를 통해 Type Coersion을 방지한다. 또한, slice 지점을 지정하는 것은 Go같으나 그 호출방식은 전통적인 Java, C++에 가깝다.
class problem2661:
def __init__(self):
self.answer = False
self.l = 0
def inputLength(self):
self.l = int(input())
def verify(self, s):
for i in range(1, int(len(s) / 2) + 1):
size = len(s) - i *2
if s[size: size+i] == s[size+i: size+i*2]:
return False
return True
def goodString(self, s):
if not self.verify(s) or self.answer:
return
if len(s) >= self.l:
self.answer = True
print(s)
return
for i in range(1,4):
self.goodString(s+str(i))
if self.answer:
return
def main(self):
self.inputLength()
self.goodString("")
if __name__ == "__main__":
p = problem2661()
p.main()
파이썬 풀이는 현대적이고 자연어에 가까운 언어라는 특성이 잘 반영된다. 파이썬은 초기 학습 곡선이 좋으나 후반부 학습 곡선이 대체로 확 가팔라진다. self를 이용한 클래스 구현은 직관적이고 이해하기 편하다. or, not, in-range 등의 자연어에 가까운 언어 특성은 파이썬이 이토록 빠르게 확산되는 원동력이었다. Go가 만약 이러한 키워드들을 지원했다면 파이썬의 아성을 넘볼 수 있었을까 상상해 본다.
package main
import "bufio"
import "os"
import "strconv"
import "strings"
type createGoodString interface {
input()
goodString(string)
verify(string) bool
}
const MAX_CHECK_NUM = 3
type solve2661 struct {
l int //length
answer bool
iostr *bufio.ReadWriter
}
func (prob *solve2661) input() {
prob.iostr = bufio.NewReadWriter(bufio.NewReader(os.Stdin), bufio.NewWriter(os.Stdout))
var buf []byte = make([]byte, 2)
_, err := prob.iostr.Read(buf)
if err != nil {
panic(err)
}
prob.l, err = strconv.Atoi(strings.TrimRight(string(buf), "\n"))
if err != nil {
panic(err)
}
}
func (prob *solve2661) verify(s string) bool {
for i := 1; i <= len(s) / 2; i++ {
size := len(s) - i * 2;
if s[size: size+i] == s[size+i: size+i*2] {
return false
}
}
return true
}
func (prob *solve2661) goodString(s string) {
if !prob.verify(s) || prob.answer {
return
}
if len(s) >= prob.l {
prob.answer = true
prob.iostr.WriteString(s)
prob.iostr.Flush()
return
}
for i := 1; i <= MAX_CHECK_NUM; i++ {
prob.goodString(s+strconv.Itoa(i))
if prob.answer {
return
}
}
}
func main() {
p := new(solve2661)
p.input()
p.goodString("")
}
여기서는 final recursion을 bool type으로 관리했고, 인터페이스를 활용해 코드를 정리했다. C++보다도 메모리 절약적이며 성능 역시 근소한 차이인 868-872KB, 4ms의 성능을 보였다. GC가 있는 매니지드 언어에서 이 정도의 성능을 낼 수 있다는 점이 주목할 점이다. 생산성 중심의 현대 언어다운 빠르고 쉬운 슬라이싱과 단순한 문법으로 스크립트 짜듯 작성 가능하다.
#include<iostream>
#include<string>
using namespace std;
#define MAX_CHECK_NUM 3
bool check_valid(string s) {
int len = s.length();
for(int i = 1; i <= len /2 ; i++) {
int size = len - i * 2;
if(s.substr(size,i) == s.substr(size+i,i)) return false;
//len = 7
//if i == 1: len - 2 == 5 , len - 2 + 1 == 6. compare idx5 and idx6
// if i == 2: len - 4 == 3 as len 2, len - 4 + 2 == 4 as len 2. comparing idx[3-4], idx[5,6]
// .. continues
}
return true;
}
void createString(string s, string &answer, int len) {
if(!check_valid(s)) return;
if(answer.length()) return;
if(s.length() >= len) {
answer = s;
return;
}
for(int i = 1; i <= MAX_CHECK_NUM; i++) {
createString(s+to_string(i), answer, len);
if(answer.length()) return;
}
}
int main() {
string s = "", answer = "";
int len = 0;
cin >> len;
createString(s, answer, len);
cout << answer;
return 0;
}
단순하고 고전적인 풀이다. 고전 C++의 틀을 벗어나지 않았다(또한 그것이 의도이다).