백준 1158 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

포스팅 전에 소리 한 번만 지르고 시작하겠다.

 

악!

 

코드

n,m = map(int,input().split())

array= [i+1 for i in range(n)]

visited = [0 for i in range(n)]

memory=0

while sum(visited) != n :

    for i in range(n):

        memory += 1

        if (memory % m) == 0 and visited[i] == 0:

            visited[i] = 1

            print(i+1,end=', ')

    else:

        memory %= m

틀린코드다, 빈자리를 계산 안 하고 문제 풀었다.

 

빈자리 계산한 코드

n,m = map(int,input().split())

array= [i+1 for i in range(n)]

memory=0

result=[]

while sum(array):

    for i in range(n):

        if array[i] != 0 :

            memory += 1

        if (memory % m) == 0 and array[i] != 0:

            array[i] = 0

            result.append(i+1)

    else:

        memory %= m

print('<' +', '.join(str(i) for i in result) +'>')

악!

 

시간초과다.

 

ㅋㅋㅋㅋ 생각해보니 5000 5000을 입력값으로 받으면 최소 2500만 연산 수가 필요하고 연산마다 대략 9번 정도 연산이 필요하니, 최대 연산 수가 2억이 넘게 나온다. ( 이렇게 계산하는 게 맞나..?)

 

당~연히 시간초과지 2초 주는데

 

그럼 어떻게 해야하나.

 

코드

n,m = map(int,input().split())

array= [i+1 for i in range(n)]

memory = 0

result = []

while len(array) > 0:

    memory = (memory + (m-1)) % len(array)

    result.append(array.pop(memory))

print('<' +', '.join(str(i) for i in result) +'>')

훨씬 간결하고 시간복잡도 또한 적다.

 

나는 방문 배열을 만들어서 해결했는데, len(array)로 나눌 생각은 하지 못했다.

 

수학적 사고능력을 키워야겠다.

 

배운 점

1. "구분자". join(배열)로 값들 사이에 구분자를 넣어서 출력할 수 있다.