[코딩테스트] [10597] 순열장난 & [2661] 좋은수열

순열장난

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

256 MB

5883

1876

1376

30.742%

문제

kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다.

그런데 sujin이 그 파일의 모든 공백을 지워버렸다!

kriii가 순열을 복구하도록 도와주자.

입력

첫 줄에 공백이 사라진 kriii의 수열이 주어진다.

kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다.

출력

복구된 수열을 출력한다. 공백을 잊으면 안 된다.

복구한 수열의 경우가 여러 가지 일 경우, 그 중 하나를 출력한다.

문제 풀이

이 문제는 1부터 N까지수 로 이루어진 무작위 순열이다

이때 공백이 모두 제거된 상태이고 중복되는 숫자가 없도록 순열을 복구해야 한 다.

또한, 정답이 여러 개라면 한 개만 출력하면 된다.

문제 분석

이 문제에서는 N이 무슨 값인지 알려주지 않았다.

그래서 유추를 해야 하는데 문자열의 길이가 9이하인 수는 숫자의 개수가 될 것이고 왜냐하면 1의 자리이니깐

1~9 (문자의 길이) == 숫자의 개수

10 이상 (문자열의 길이 - 9(1의 자리 숫자 개수) / 2 + 9(1의 자리 숫자 개수)

예시 13자리의 길이인 경우

(13 - 9(1의 자리 숫자 개수) ) / 2 + 9(1의 자리 숫자 개수) == 11

[1: 11] 범위 숫자로 구성

Base Case

index가 입력된 값과 같아지면 더 이상 검사할 필요가 없기에 종료를 해야 한다.

이 때 공백을 추가하기 위해 for-each문을 사용하여 순차적으로 공백과 함께 추가하여 출력한다.

• 정수로 파싱 중인 문자의 인덱스가 끝에 도달 했을 때
• 파싱에 성공한 정수를 출력하고 프로그램 종료

public static void solve(int index) {
	if (index >= input.length) {
		for (Integer integer: answer) {
			System.out.print(integer + " ");
		}
		System.out.println();
		System.exit(0);
	}
}

Recursive Case

일의 자리와 십의 자리를 구분하여서 출력하면 된다.

두개의 조건을 구하는 경우(일의 자리, 십의 자리)

• 현재의 인덱스 위치에서 1개의 숫자로 정수를 생성
• 현재의 인덱스 위치에서 2개의 숫자로 정수를 생성

// 일의 자리 숫자
int target1 = atoi(input, index + 1);

answer.add(tareget1);
solve(index + 1);

// 십의 자리 숫자
int target2 = atoi(input, index + 2);

answer.add(tareget2);
solve(index + 2);

Backtrack

순열이기에 중복 검사를 하는 변수를 만들어 중복 방지를 한다.

N보다 큰 수가 생기면 범위를 초과하기에 방지해주자.

그리고 십의 자리를 검사할때 index + 1이 입력받은 문자열의 크기와 같고 크다면 오류가 발생한다.

• 생성하려는 정수가 이전에 사용된 적이 있는 경우
• N보다 큰 정수를 생성하려는 경우
• 생성하려는 정수가 원본 문자열 인덱스를 초과하는 경우

if (target <= n && check[target1] == 0 ) // 순열이기에 중복 검사, N보다 작은지 검사
if (index + 1 >= input.length) return; // 원본 문자열 인덱스보다 초과한 경우

전체코드

import java.util.*;

class Main {
    static char[] input;
    static int n = 0;
    static int[] check = new int[101];
    static List<Integer> answer = new ArrayList<>();
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        input = sc.next().toCharArray();
        n = input.length > 9 ? 9 + (input.length - 9) / 2 :input.length;
        
        solve(0);
    }

    static void solve(int index) {
        if (index >= input.length) {
            for (Integer a : answer) {
                System.out.print(a + " ");
            }
            System.exit(0);
        }

        int target1 = alphabetToInt(input, index, 1);
        if(target1 <= n && check[target1] == 0) {
            check[target1] = 1;
            answer.add(target1);
            solve(index + 1);
            check[target1] = 0;
            answer.remove(answer.size() - 1);
        }

        if (index + 1 >= input.length) return;

        int target2 = alphabetToInt(input, index, 2);
        if(target2 <= n && check[target2] == 0) {
            check[target2] = 1;
            answer.add(target2);
            solve(index + 2);
            check[target2] = 0;
            answer.remove(answer.size() - 1);
        }
        
    }

    static int alphabetToInt(char[] input, int start, int length) {
        int result = 0;
        for(int i = start; i < start + length; i++) {
            result *= 10;
            result += input[i] - '0';
        }        
        return result;
    }
}

좋은수열

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

128 MB

17304

8576

6612

50.251%

문제

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

• 33
• 3323
• 2121
• 123123213

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.

입력

입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

출력

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

문제 풀이

이 문제는 길이가 N인 순열 중 같은 수열이 두 번 이상 반복하는 수열을 제외한 후 가장 작은 수열을 찾는 문제이다.

문제 요약

• 숫자 1, 2, 3으로만 이루어지는 수열
• 임의의 길이로 인접한 두개의 부분 수열이
  • 같으면 나쁜 수열
  • 같지 않으면 좋은 수열
   

• 길이가 N인 좋은 수열 중 가장 작은 수를 찾는 것
  • 1 ≤ N ≤ 80

나쁜 수열 판별 법

• 가장 뒤에 숫자를 추가 할 때 마다 검사를 하는 것.
• 인접한 부분 수열이 2번 등장해야 하므로 {마지막 인덱스 + 1 } / 2 까지 검사해야함.
  • 즉, 수열의 끝 부분에서 길이 i (1부터 (endIndex+1)/2까지)인 인접한 두 부분 수열이 같은지 확인

for (int i = 1; i <= (endIndex + 1) / 2; i++) {
	boolean isSame = true;
	for (int j = 0; j < i; j++) {
		if (numbers[endIndex - j] != numbers[endIndex - i - j]) {
			isSame = false;
			break;
		}
	}
}

Base Case

• 생성하는 수열의 길이가 N에 도달
  • 1 → 2 → 3 순으로 수열 생성을 시도하여 가장 먼저 발견될 수열이 오름차순으로 가장 빠른 수열

if (endIndex == n) {
	for (int i = 0; i < n; i++) {
		System.out.print(numbers[i]);
	}
	return true;
}

Recursive Case

• 기존에 생성한 수열의 가장 마지막에 ‘1’, ‘2’, ‘3’을 각각 추가하며 재귀 수행
• 재귀 함수가 boolean 타입을 반환하는 이유는 최초로 조건을 만족하는 경우가 가장 작은 수 일 때 즉시 종료하기 위해서이다..

Backtrack

• 마지막 인덱스에 추가한 숫자가 나쁜 수열을 만들면 중단.

for (int i = 1; i <= 3; i++) {
	numbers[endIndex] = i;
	if (!isBad(endIndex)) {
		if (solve(endIndex + 1)) return true;
	} 
}

전체 코드

import java.util.*;

class Main {
    static int n;
    static int[] result = new int[80];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        solve(0);
    }
    
    static boolean solve(int endIndex) {
        if (n == endIndex) {
            for (int i = 0; i < n; i++) {
                System.out.print(result[i]);
            }
            return true;
        } else {
            for (int i = 1; i <= 3; i++) {
                result[endIndex] = i;
                if (!isBad(endIndex)) {
                    if (solve(endIndex + 1)) return true;
                }                
            }
        }
        return false;
    }
    
    static boolean isBad(int endIndex) {
        for (int i = 1; i <= (endIndex + 1) / 2; i++) {
            boolean isSame = true;
            for (int j = 0; j < i; j++) {
                if (result[endIndex - j] != result[endIndex - i - j]) {
                    isSame = false;
                    break;
                }
            }
            if (isSame) return true;
        }
        return false;
    }
}