백준 #1138 - [S2] 한 줄로 서기

(python3)

1138번: 한 줄로 서기

 

(시간초과) 풀이 1. 모든 순열을 만들고 체크하기

perm 함수에서 모든 순열을 만듭니다. 순열은 재귀로 만들었습니다.

순열이 완성되었을 때 is_correct 함수로 이 순열이 주어진 조건과 같은지 확인합니다.

같으면 출력하는 형식으로 코드를 짜봤는데 시간초과..입니다.

N = 10 이 최대 입력이라 10! 이면 괜찮을지도? 라는 생각이었는데, 컴퓨터가 8~9부터 힘겨워하더라구요

 

코드

import sys
from copy import deepcopy
def solution(input) :
    def is_correct(L,check,N) :
        tall_cnt = [0]*(N+1)
        for i in range(N) :
            cnt = 0
            for t in L[0:i] :
                if L[i] < t : cnt+=1
            tall_cnt[L[i]] = cnt
        return check == tall_cnt[1:]

    def perm(L,n,N,check) :
        if n >= N :
            if is_correct(L,check,N) :
                print(' '.join([str(c) for c in L]))
            return
        for i in range(1,N+1) :
            if i not in L :
                L[n] = i
                perm(deepcopy(L),n+1,N,check)
    
    N = int(input().strip())
    check = list(map(int,input().split()))
    perm([0]*N,0,N,check)
input = sys.stdin.readline
solution(input)

 

풀이 2. 나보다 큰 수가 들어갈 공간 비워두기

"내 앞에 나보다 큰 수가 몇 개인지"가 키가 작은 순서대로 들어옵니다.

나보다 큰 수가 들어갈 공간을 그만큼 비워두고 자리를 잡으면 됩니다.

예를들어 아래 입력의 경우

7
6 1 1 1 2 0 0

처음에는 빈공간만 7개를 배치합니다.

[0,0,0,0,0,0,0]

1은 자기보다 큰게 앞에 6개 들어가야합니다. 0을 6개 비워놓고, 그 다음 0의 위치에 1을 넣습니다,

[0,0,0,0,0,0,1]

2는 자기보다 큰게 앞에 1개 들어가야합니다. 0을 1개 비워놓고, 그 다음 0의 위치에 2를 넣습니다.

[0,2,0,0,0,0,1]

3도 마찬가지로 넣으면

[0,2,3,0,0,0,1]

이걸 반복해서 채워넣을 수 있습니다.

 

코드

import sys
from copy import deepcopy
def solution(input) :
    N = int(input().strip())
    L = list(map(int,input().split()))
    ans = [0]*N
    for i in range(N) :
        cnt = 0
        for a in range(N) :
            if ans[a] == 0 :
                cnt+=1
                if cnt > L[i] : # 조건만큼 빈공간을 비운 후 그 다음에 만난 빈공간에 배치하기
                    ans[a] = i+1
                    break
    print(' '.join([str(i) for i in ans]))

input = sys.stdin.readline
solution(input)

 

(추천) 풀이 3. 큰 수부터 넣기

다른 분의 코드를 참고했습니다.

큰 수부터 넣으면 insert로 밀어넣으면 됩니다!

"나보다 큰 수는 이미 다 배치된 상태" 이기 때문에 내 앞에 조건대로 칸수를 비우고 inset로 밀어넣을 수 있습니다.

 

코드

import sys
input = sys.stdin.readline

N = int(input().strip())

arr1 = list(map(int,input().split()))

arr2 = []
for i in range(N,0,-1):
    arr2.insert(arr1[i-1],i)

print(' '.join([str(i) for i in arr2]))

 

 

my solved.ac :

solved.ac