[김태원 알고리즘] 역수열 (그리디)

사용 언어: Python3

문제

풀이

내 풀이

N = int(input())
lst = list(map(int, input().split())) # 역수열

orig = [] # 원수열
for i in range(N, 0, -1):
    orig.insert(lst[i-1], str(i)) # insert(idx,val): idx번째에 val 추가
    
print(" ".join(orig))

• orig라는 원수열을 담을 리스트를 선언한다.
• 역수열(lst)의 맨 “마지막” 원소부터 순회하면서 원수열에 원소를 하나씩 추가한다.
  • 역수열: 5 3 4 0 2 1 1 0
    • 8을 orig의 0번째에 추가 (원수열: 8)
    • 7을 orig의 1번째에 추가 (원수열: 8 7)
    • 6을 orig의 1번째에 추가 (원수열: 8 6 7)
    • 5을 orig의 2번째에 추가 (원수열: 8 6 5 7)
    • 4을 orig의 0번째에 추가 (원수열: 4 8 6 5 7)
    • 3을 orig의 4번째에 추가 (원수열: 4 8 6 5 3 7)
    • 2을 orig의 3번째에 추가 (원수열: 4 8 6 2 5 3 7)
    • 1을 orig의 5번째에 추가 (원수열: 4 8 6 2 5 1 3 7)

다른 풀이 - 1

N = int(input())
lst = list(map(int, input().split())) # 역수열

orig = [0] * N # 원수열
for i in range(1, N+1): # 1부터 N까지의 수를 차례로 넣기
    cnt = 0
    for j in range(N):
        # 0을 카운트하고 그 다음 빈칸(=0)을 찾아 넣기 (이미 차지하고 있으면(=0이 아니면) 안됨)
        if orig[j] == 0:
            cnt += 1
        if cnt == lst[i-1] + 1: # 그 다음 0인 칸에 넣기
            orig[j] = i
            break

for x in orig:
    print(x, end=" ")

• orig라는 원수열을 담을 리스트를 선언한다.
• 원수열을 0으로 초기화한 뒤 1부터 N까지의 수를 차례로 추가한다.
  • 이때 빈칸(=0)을 카운트하여 빈칸을 역수열 값만큼 확보한 뒤에 다음 빈칸에 추가해야한다!
  • 역수열: 5 3 4 0 2 1 1 0
  • 원수열: 0 0 0 0 0 0 0 0
    • 0을 5번 카운트 한 뒤 1을 다음 빈칸에 추가 (원수열: 0 0 0 0 0 1 0 0)
    • 0을 3번 카운트 한 뒤 2를 다음 빈칸에 추가 (원수열: 0 0 0 2 0 1 0 0)
    • 0을 4번 카운트 한 뒤 3를 다음 빈칸에 추가 (원수열: 0 0 0 2 0 1 3 0)
      • 🌟 빈칸이 아니면 추가히지 못한다! 건너뛰고 다음 빈 칸을 만나면 추가한다.
    • 0을 0번 카운트 한 뒤 4를 다음 빈칸에 추가 (원수열: 4 0 0 2 0 1 3 0)
    • 0을 2번 카운트 한 뒤 5를 다음 빈칸에 추가 (원수열: 4 0 0 2 5 1 3 0)
    • 0을 1번 카운트 한 뒤 6를 다음 빈칸에 추가 (원수열: 4 0 6 2 5 1 3 0)
    • 0을 1번 카운트 한 뒤 7를 다음 빈칸에 추가 (원수열: 4 0 6 2 5 1 3 7)
    • 0을 0번 카운트 한 뒤 8를 다음 빈칸에 추가 (원수열: 4 8 6 2 5 1 3 7)

다른 풀이 - 2

바로 위와 같은 로직인데 구현이 다른 버전이다!

N = int(input())
lst = list(map(int, input().split())) # 역수열

orig = [0] * N # 원수열
for i in range(N):
    for j in range(N):
        if lst[i] == 0 and orig[j] == 0: # 이미 차지하고 있으면(=0이 아니면) 안됨
            orig[j] = i+1
            break
        elif orig[j] == 0:
            lst[i] -= 1 # 0일 때 하나씩 감소 (0을 카운트하기 위해)

for x in orig:
    print(x, end=" ")

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기