[인프런] 파이썬 알고리즘 문제풀이 입문 - 이분탐색 & 그리디 (수정중)

bee·2023년 4월 5일
python알고리즘인프런코딩테스트
0

Algorithm

목록 보기
4/8
post-thumbnail

1. 이분검색

임의의 N개의 숫자가 입력으로 주어진다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째 있는지 구하는 프로그램을 작성하시오. 단, 중복값은 존재하지 않는다.

## 내 풀이
def binary_search(target, array, s, e):
    array = array.sort()
    mid = (s+e)//2
    
    if s > e : # 애초에 성립 불가한 경우
        return None
    
    if array[mid] == target : # (1) 타겟값을 찾은 경우
        return mid
    
    elif array[mid] > target : # (2) 중간값이 타겟값보다 큰 경우
        return binary_search(target, array, start, mid-1)
        
    else: # (3) 중간값이 타겟값보다 작은 경우
        return binary_search(target, array, mid+1, end)
    
    
N, M = map(int, input().split())
array = list(map(int, input().split()))

res = binary_search(M, array, 0, N-1)

print(res+1)

8 32
23 87 65 12 57 32 99 81

TypeError: 'NoneType' object is not subscriptable
None 타입의 값에 인덱스로 접근하려해서 발생했다.

틀린이유 : 원인은 .sort() 함수 때문이었다.array.sort()는 array라는 리스트 자체를 정렬 변경하기 때문에 사실상 반환값이 None 이다. 반면에 sorted(array)는 array 리스트를 정렬한 새로운 리스트를 생성해서 반환해준다. 따라서 array.sort()로 하던지 아니면 array = sorted(array) 로 해야한다.

.sort()와 sorted(a)의 차이에 대해 좀 더 알아보자.

sorted(a)

sorted()는 파이썬의 내장함수이다. 내장함수란, 파이썬에서 기본적으로 제공해주는 함수(= 특정 작업을 수행하는 명령어)이다.
sorted(a)는 a라는 리스트를 정렬한 새로운 리스트를 생성한 후, 그것을 리턴한다. 즉, 리스트의 복사본을 만들어 정렬해주기 때문에 a에 직접적으로 영향을 주지 않는다.

a = [5, 3, 1, 2]
print(sorted(a))

[1, 2, 3, 5]

a.sort()

.sort는 메소드이다. 메소드가 내장함수와 다른점은, 특정 객체(object)에 적용되는 함수라는 것이다.
a.sort()는 a라는 리스트 자체를 정렬한다. 하지만 a라는 객체에 정렬이라는 행위 자체를 적용할 뿐, 리턴해주지 않기 때문에 None을 리턴한다. 즉, 원본을 직접 정렬해주기 때문에 a에 직접적으로 영향을 준다.

a = [5, 3, 2, 1]
print(a.sort())

None

a = [5, 3, 2, 1]

a.sort()
print(a)

[1, 2, 3, 5]


n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

lt = 0 # 시작점
rt = n-1 # 끝점

while lt <= rt :
	mid = (lt + rt)//2
    
    if a[mid] == m : # m을 찾은 경우
    	print(mid+1)
        break
        
    elif a[mid] > m : # 중간점이 m보다 큰 경우 (중간점 오른쪽 구역은 탐색할필요x)
    	rt = mid-1
    
    else : # 중간점이 m보다 작은 경우 (중간점 왼쪽 구역은 탐색할필요x)
    	lt = mid+1

8 32
23 87 65 12 57 32 99 81

3





2. 랜선자르기(결정 알고리즘)

길이가 제각각인 K개의 랜선이 있다. 랜선을 모두 N개의 같은 길이의 랜선으로 만들기 위해 K개의 랜선을 자르려고 한다. 랜선을 자를 때 손실되는 길이는 없고, 기존 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 cm 단위로 정수 길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다고 할 때, 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

## 내 풀이
K, N = map(int, input().split())
a = [int(input()) for _ in range(K)]

start = 0
end = max(a)

result = 0 # 구하고자 하는 값 : 최대 랜선 덩어리 길이

while start <= end:
    total = 0 # 잘린 랜선의 개수의 합
    mid = (start + end)//2
    
    
    for x in a :
        if x > mid :
            total += (x // mid) # 주어진 길이를 랜선 덩어리 길이로 나눈 몫이 개수가 됨
    
    # 잘린 랜선이 부족한 경우 (중간점의 왼쪽 구역 탐색)
    if total < N :
        end = mid - 1
    
    # 잘린 랜선이 충분한 경우 : total >= N (중간점의 오른쪽 구역 탐색)
    else:
        result = mid
        start = mid + 1

print(result)

4 11
802
743
457
539

200

나의 풀이 아이디어는 다음과 같다.

## 모범답안
# 현재 길이가 정답이 되는지 아닌지 판단하는 함수 생성
def Count(len):
    cnt = 0
    for x in Line:
        cnt += (x//len) # 개수의 누적값
    return cnt    
        
k, n = map(int, input().split())
Line = []
res = 0
largest = 0 # 길이가 가장 긴 랜선의 길이

for i in range(k):
    tmp = int(input())
    Line.append(tmp)
    largest = max(largest, tmp)
    
lt = 1
rt = largest

while lt <= rt :
    mid = (lt + rt) // 2 # 랜선의 길이
    
    if Count(mid) >= n :
        res = mid
        lt = mid + 1
        
    else: 
        rt = mid - 1
        
print(res)

4 11
802
743
457
539

200

이런 결정 알고리즘을 활용하는 문제에는 구하고자 하는 답이 특정 범위 안에 있다는 특징이 있다. 해당 범위 내에 있는 숫자를 중간값으로 정해놓고, 이분탐색을 통해 그 값이 답으로써 유효한지 유효하지 않은지를 확인하는 함수를 만든다. 함수를 거친 현재 값이 답으로써 유효하다면 범위를 좁혀나가면서 현재 값보다 더 최적의 값을 찾아나가는 방식으로 해결하면 된다.





# 3. 뮤직비디오(결정 알고리즘) > 가수의 라이브 DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때 라이브에서의 순서가 그대로 유지돼야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. 음반사에서는 낭비되는 DVD를 줄이기 위해 M개의 DVD에 모든 동영상을 녹화하기로 하고, 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기여야 한다. 
## 내 풀이

## 모범답안
# n개의 곡을 다 저장하려면 DVD가 몇장 필요한지 판단하는 함수 생성
def Count(capacity):
    cnt = 1 # 필요한 DVD 개수
    sum = 0 # 곡을 저장했을 때 누적된 시간

    for x in Music :
        if sum+x > capacity :
            cnt += 1
            sum = x
        else:
            sum += x
            
    return cnt


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

lt = 1
rt = sum(Music)

res = 0

while lt <= rt :
    mid = (lt+rt) // 2 # 필요한 DVD 한 장의 용량
    
    if Count(mid) <= m and mid > max(Music) : # 길이가 가장 긴 노래를 담을 수 있는 용량이 되어야함
        res = mid
        rt = mid - 1
    else :
        lt = mid + 1

print(res)




# 4. 마구간 정하기(결정 알고리즘) > N개의 마구간이 수직선상에 있고, 각 마구간은 x1, x2, x3 ... xN의 좌표를 가진다. 각 마구간에는 한 마리의 말만 넣을 수 있다고 한다. C마리의 말을 N개의 마구간에 배치했을 때, 가장 가까운 두 말의 거리가 최대가 될 때의 거리를 출력하는 프로그램을 작성하시오. 
## 내 풀이

## 모범답안

풀이 아이디어 :





5. 회의실 배정(그리디 알고리즘)

1 개의 회의실이 있는데, 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간들이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.

## 내 풀이
n = int(input())
time = [tuple(map(int, input().split())) for _ in range(n)]

cnt = 0

for s, e in range(time):
	

print(cnt)

일단 답도 내지 못했다. 

## 모범답안
n = int(input())
meeting = []

for i in range(n):
    s, e = map(int, input().split())
    meeting.append((s, e)) # tuple형태로 리스트에 추가
    
# 끝나는 시간 기준으로 정렬 . (x[1], x[0])은 정렬 순위
meeting.sort(key = lambda x : (x[1], x[0]))

et = 0 # 끝나는 시간 (기록용)
cnt = 0 # 회의 개수

for s, e in meeting :
    if s >= et : # 현재 회의의 끝나는시간(e)보다 다음회의의 시작시간(s)가 크거나 같을 경우
        et = e # et는 진행완료한 끝나는시간(e)이된다.
        cnt += 1 # 회의 개수 추가
        
print(cnt)

5
1 4
2 3
3 5
4 6
5 7

3

풀이 아이디어 : 회의가 끝나는 시간을 기준으로 정렬하기

보통의 그리디 문제는 대부분 "정렬"을 사용한다고 한다. 정렬 후 차례대로 선택하는 방식으로 해결해나가는 것이다. 이번 문제에서는 회의의 개수를 최대로 만드는 것이 관건이기 때문에 "회의가 끝나는 시간"을 기준으로 오름차순 정렬하는 것이 핵심 아이디어였다. 이 때, sort()에서의 key lambda를 사용해서 정렬 기준을 정해주는 과정이 필요했다.

meeting.sort(key lambda x : (x[1], x[0]))

기본 정렬에서는 x[0] 즉, 시작 시간을 기준으로 오름차순 정렬되기 때문에, key lambda를 사용해서 그 순서를 바꿔주면 정렬기준이 끝나는 시간 => 시작 시간으로 바뀐다.

정렬 이후에는 가장 빨리 끝나는 회의의 끝나는 시간과 그 다음 회의의 시작시간을 비교한다. 다음 회의의 시작시간이 끝나는 시간보다 크거나 같다면 해당 회의를 카운트한다.

코드 작동 원리는 다음과 같다.





6. 씨름 선수(그리디)

씨름 선수 선발 원칙은 "다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나 무거운 지원자만 뽑기로 했습니다."라고 한다. N명의 지원자가 지원했고, 감독은 각 지원자의 키와 몸무게 정보를 알고 있을 때, 씨름 선수로 뽑히는 최대 인원을 출력하는 프로그램을 작성하시오.

## 내 풀이
n = int(input())
player = [tuple(map(int, input().split())) for _ in range(n)]

w1 = 0 # 비교대상 : 다음 선수의 몸무게
cnt = 0 # 선수로 선발된 인원수

player.sort(reverse = True) # 기본정렬이 첫번째 요소 기준이기 때문에 순서 변경은 필요x

for h, w in player :
    if w > w1: # 현재 선수의 몸무게가 다음 선수의 몸무게보다 크다면
        w1 = w # 비교 대상을 현재 선수의 몸무게로 변경하고
        cnt += 1 # 선수로 선발한다 (인원수 추가)
        
print(cnt)

5
172 67
183 65
180 70
170 72
181 60

3

사실 처음에는 문제가 잘 이해되지 않았다 (이해보다도 문제 자체에 오류가 있는 것 같았음).
예제 설명에서 (183, 65), (180, 70), (170, 72)가 선발됩니다. (181, 60)은 (183, 65) 때문에 탈락하고, (172, 67)은 (180, 70) 때문에 탈락합니다. 라고 되어있는데, 나는 (172, 67)도 키로 보았을때는 (170, 72)보다 크니까 선수로 선발될 수 있지 않는가 의문이 들었다.
문제에서 요구하는 바는 내가 뽑히기 위해서는 나를 키와 몸무게로 모두 이기는 사람이 존재해선 안된다. 즉, 지원자 입장에서 모든 다른 지원자들과 비교했을 때 본인이 특정 지원자에게 키로 졌다면, 몸무게로는 반드시 이겨야 선수로 선발 가능하다. 를 의미하는 것 이었다.

풀이 아이디어 : 키를 기준으로 내림차순 정렬 후 현재 선수의 몸무게가 다음 선수의 몸무게보다 크다면 선수로 선발

자세히 보면 앞선 5번 문제와 풀이 방식이 거의 유사하다. 이런식으로 두개의 요소를 받아야 할 때, 기준을 정해서 한 요소를 정렬한 후 나머지 요소에 대해서 비교하는 방식으로 풀이한다.
내가 작성한 코드의 원리는 다음과 같다.

## 모범답안
n = int(input())
body = []
for i in range(n):
    h, w = map(int, input().split())
    body.append((h, w))
    
body.sort(reverse = True) # 키(h)기준 내림차순 정렬

largest = 0 # 몸무게최댓값을 찾기 위한 비교 대상
cnt = 0

for h, w in body :
    if w > largest :
        largest = w
        cnt += 1

print(cnt)

5
172 67
183 65
180 70
170 72
181 60

3

모범답안에서도 동일한 원리로 풀이했기 때문에 따로 설명은 하지 않겠다.





7. 창고정리

창고에 상자가 가로방향으로 일렬로 쌓여있다. 창고 높이 조정은 가장 높은 곳의 상자를 가장 낮은 곳으로 이동하는 것을 말한다. 가장 높은 곳이나 가장 낮은 곳이 여러곳이라면 그 중 아무거나 선택해서 이동하면 된다. 창고의 가로 길이와 각 열의 상자 높이가 주어질 때, m회의 높이 조정을 한 후 가장 높은 곳과 가장 낮은 곳의 차이를 출력하는 프로그램을 작성하시오.

## 내 풀이
l = int(input()) # 창고 가로 길이
box = list(map(int, input().split())) # 각 열의 상자 높이
m = int(input()) # 높이 조정 횟수

largest = -2147000000
smallest = 2147000000

diff = largest - smallest

while m == 0 :
    for i in range(l):
        if smallest >= box[i]:
            smallest = box[i]
        if largest <= box[i]:
            largest = box[i]
            
        smallest += 1
        largest -= 1 
        m -= 1

print(diff)

10
69 42 68 76 40 87 14 65 76 81
50

-4294000000

어디가 잘못됐는지도 모르지만 답이 아니라고는 생각했다. 답이 아닌걸 알면서도 계속 코드를 치고있는 나...
내가 의도한 바는 각각 최대높이, 최소높이의 비교대상을 정해서 1씩 증/감 후 1 iteration을 돌 때 마다 최대높이, 최소높이를 갱신하는 것이었다. 언제쯤 내가 의도한 바대로 코드를 작성할 수 있을까?

## 모범답안
L = int(input())
a = list(map(int, input().split()))
m = int(input())

a.sort()

for _ in range(m):
    a[0] += 1 # 가장 낮은 높이 1증가
    a[L-1] -= 1 # 가장 높은 높이 1감소
    a.sort() # 높이조정 1회 이후에는 제일 높은것과 낮은것이 변경될 수도 있기때문에 다시 정렬해준다.
    
print(a[L-1] - a[0])

10
69 42 68 76 40 87 14 65 76 81
50

20

풀이 아이디어 : 각 열의 상자 높이를 오름차순으로 정렬 후 높이조정과 동시에 다시 정렬하는 과정을 반복

이번 섹션에서의 핵심이 '정렬'이라는 것을 알고 있었다면 생각보다 간단하게 풀릴 문제였다. 나는 처음에 가장 높은 곳이나 가장 낮은 곳이 여러곳이면 그 중 아무거나 선택하면 된다.라는 말 때문에 어렵게 생각했었는데, 따지고보면 1 iteration을 돌고 다시 정렬하여 처음과 끝 요소끼리의 연산만 하면 같은 높이의 열이 여러개라도 상관 없게 된다.





8. 침몰하는 타이타닉 (그리디)

침몰하는 유람선 타이타닉에는 N명의 승객이 타고있다. 타이타닉에 있는 구명보트는 2명 이하로만 탑승 가능하고, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있다. N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력하는 프로그램을 작성하시오.

## 내 풀이
n, m = map(int, input().split())
weight = list(map(int, input().split()))

weight.sort() # 오름차순 정렬
cnt = 0 # 구명보트 개수


for i in range(n//2 + 1):
    if weight[0] + weight[-1] <= m : # 구명보트에 태울 수 있는 경우
        cnt += 1 # 구명보트 개수 추가
        weight.pop() # 가장 가벼운 사람의 몸무게 리스트에서 제거
        weight.pop(0) # 가장 무거운 사람의 몸무게 리스트에서 제거
    
    else : # weight[0]과 weight[-1]을 구명보트에 태울 수 없는 경우
        cnt += 1 # 구명보트 개수 추가 (가장 큰 값이 마지막 사람을 보트 하나에 따로 태움)
        weight.pop() # 가장 무거운 사람의 몸무게 리스트에서 제거
        
print(cnt)

5 140
90 50 70 100 60

3

풀이 아이디어 : 몸무게를 오름차순 정렬한 뒤, 가장 가벼운 사람의 몸무게(weight리스트의 첫번째 요소)와 가장 무거운 사람의 몸무게(weight리스트의 마지막 요소)의 합이 m kg초과라면 가장 무거운 사람의 몸무게를 리스트에서 제외한 후 반복문 돌기(이 때 가장 무거운 사람은 보트에 따로 태운 것으로 간주하기 때문에 보트 개수를 1개 추가한다.). 합이 m kg보다 작거나 같다면 두 사람의 몸무게를 리스트에서 제외한 후 반복문 돌기 (두 사람은 보트 탑승이 가능하므로 이 때도 보트 개수를 1개 추가한다.).

작성한 코드의 작동 원리는 다음과 같다.

## 모범답안 - 리스트 사용
n, m = map(int, input().split())
w = list(map(int, input().split()))
w.sort()

cnt = 0

while w:
    
    # 논리적 오류 발생 방지를 위한 코드
    if len(w) == 1: 
        cnt += 1
        break 
        
    if w[0] + w[-1] > m: # 마지막 사람 몸무게 때문에 두 명이서 같이 탑승 불가할 때
        w.pop()
        cnt += 1
    else: # 두 명이서 같이 탑승 가능할 때
        w.pop(0)
        w.pop()
        cnt += 1
        
print(cnt)

5 140
90 50 70 100 60

3

아래의 코드의 부재 때문에 사실상 내 코드는 오답일 수도 있다. 다른 테스트케이스를 넣어보면 알 것이다.

# 논리적 오류 발생 방지를 위한 코드
if len(w) == 1 : # 한 명 남았을 때
	cnt += 1 # 이 1명에 대해서도 탑승 인원에 추가해준다
    break # 마지막 한 명이기 떄문에 pop을 사용할 필요 없이 바로 반복문 탈출

위 코드가 필요한 이유는 무엇일까?

예를 들어, 유람선에 2명의 승객만 남았다고 가정해보자. 만약에 이 중에서 두 사람의 몸무게 합이 m kg를 초과할 경우 p.pop()로 인해 w 리스트에는 1명만 남게될 것 이다. 이 1명으로 다시 반복문이 돈다면 p[0] + p[-1]에서 1명의 몸무게가 중복값으로 더해지기 때문에 논리적인 오류가 발생한다. 이를 방지하기 위한 코드라고 생각하면 될 것 같다.


이 풀이가 정답을 출력하기는 하지만, 더 좋은 코드를 만들 수 있다고 한다.
위의 풀이에서 사용한 List의 경우, pop을 할 때 빈공간이 생기는데, 그러면 나머지 모든 자료가 빈 공간을 채우기 위해 이동해야하기 때문에 비효율적이다.

이 때, Deque(데크) 라는 자료구조를 사용해서 보다 효율적으로 코드를 작성할 수 있다. 

## 모범답안 - 데크 사용
from collections import deque
n, m = map(int, input().split())
w = list(map(int, input().split()))
w.sort()
w = deque(w) # 리스트 w를 데크로 변환

cnt = 0

while w:
    
    # 논리적 오류 발생 방지를 위한 코드
    if len(w) == 1:
        cnt += 1
        break
        
    if w[0] + w[-1] > m: # 마지막 사람 몸무게때문에 두 명이서 같이 탑승 불가할 떄
        w.pop()
        cnt += 1
    else: # 두 명이서 같이 탑승 가능할 때
        w.popleft() # 데크 왼쪽에서 요소 제거 (빈 괄호는 첫번째 요소를 의미)
        w.pop()
        cnt += 1
        
print(cnt)

5 140
90 50 70 100 60

3

우선 deque 자료구조는 colletions 모듈에서 제공하기 때문에
from collections import deque의 과정이 필요하다. deque는 스택과 큐의 장점을 모두 채택한 자료구조인데, 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것 보다 더 간단하다.

위의 문제에 deque를 활용해보자.
문제에서 필요한 w.pop()연산을 수행해도 deque에서는 나머지 자료들이 이동하는 것이 아니라 포인트 변수가 이동하면서 다음 자료를 가리키기 때문에 list보다 훨씬 효율적이다.





9. 증가수열 만들기(그리디)

1부터 N까지의 자연수로 구성된 길이 N의 수열이 주어진다. 이 수열의 가장 왼쪽 숫자 또는 가장 오른쪽 숫자 중 하나를 가져와 나열하여 가장 긴 증가수열을 만든다. 만들 수 있는 증가수열의 최대 길이(첫째 줄)와 숫자를 가져간 순서대로 가장 왼쪽에서 가져갔다면 'L'을, 가장 오른쪽에서 가져갔다면 'R'을 써서 방향을 표시한 문자열(둘째 줄)을 출력하는 프로그램을 작성하시오. (단, 마지막에 남은 값은 가장 왼쪽에서 가져온 것으로 생각합니다.)

## 내 풀이
n = int(input())
n_list = list(map(int, input().split()))

m = [] # 증가수열을 담을 빈 리스트 생성
cnt = 0 # 증가수열 길이
d = '' # 방향 문자열

s = n_list[0] # 가장 왼쪽 원소
e = n_list[-1] # 가장 오른쪽 원소

m.append(min(s,e))
n_list.remove(min(s,e))

while n_list:
    
    if s < e and s >= m[-1] :
        m.append(n_list.pop(0))
        cnt += 1
        d += 'L'
        
    elif e < s and e >= m[-1]:
        m.append(n_list.pop(-1))
        cnt += 1
        d += 'R'


print(cnt)
print(d)

풀이 아이디어 : 증가수열의 마지막 항보다 크고 주어진 리스트의 양 끝 원소 중 더 작은 원소 뽑기

풀이 아이디어 자체는 세웠는데 막상 코드로 옮겨보니 에러가 떴다.

## 모범답안
n = int(input())
a = list(map(int, input().split()))

lt = 0
rt = n-1

last = 0 # 증가수열의 마지막 항
res = "" # 방향 문자열
tmp = [] 

while lt <= rt:
    
    # (1) a의 양끝원소가 last보다 크다면 tmp에 추가
    if a[lt] > last :
        tmp.append((a[lt], 'L'))
    if a[rt] > last :
        tmp.append((a[rt], 'R'))
        
    tmp.sort() # 양끝원소 기준으로 오름차순 정렬

    # 종료조건
    if len(tmp) == 0: # a에서 더이상 가져올 리스트가 없을때(양끝원소가 last보다 작을때)
        break

    # (2)
    else: # a에서 양끝원소를 가져왔을 때
        res = res + tmp[0][1] # res에 양끝원소 중 더 작은수의 방향문자열 추가
        last = tmp[0][0] # last를 양끝원소 중 더 작은 수 로 갱신
        
        
        # (3) 포인터변수 이동
        if tmp[0][1] == 'L': # 증가수열이 된 양끝원소를 가장 왼쪽에서 가져왔을 때
            lt += 1 # 포인터변수 lt를 오른쪽으로 한 칸 이동
        else: # 증가수열이 된 양끝원소를 가장 오른쪽에서 가져왔을 때
            rt -= 1 # 포인터변수 rt를 왼쪽으로 한 칸 이둥
            
            
    # (4) tmp 초기화하고 반복문 처음올 돌아감
    tmp.clear()

print(len(res))
print(res)

5
2 4 5 1 3

4
LRLL


풀이 아이디어는 내가 생각한 것과 동일한데, tmp라는 튜플을 담은 리스트를 사용했다는 점에서 풀이 방식이 달랐다. 코드의 작동 원리는 다음과 같다.





10. 역수열(그리디)

1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 '역수열'이라 한다. n과 1부터 n까지의 수를 사용하여 이루어진 수열의 역수열이 주어졌을 때, 원래의 수열을 출력하는 프로그램을 작성하세요.

## 내 풀이


## 모범답안
n = int(input())
a = list(map(int, input().split()))


seq = [0] * n # 원래수열을 담을 리스트 생성 (빈공간을 뜻하는 0으로 초기화)

for i in range(n): # 자리 찾아갈 1부터 n까지의 수라고 생각하자.
    for j in range(n): # seq의 포인트변수라고 생각하자.
        if a[i] == 0 and seq[j] == 0: # a[i]==0 : 빈공간 확보/ seq[j]==0 : 그 자리가 비어있음
            seq[j] = i+1 # i는 0부터시작하기 때문에 1더해줌
            break # j를 break
            
        elif seq[j] == 0 : # 빈자리 발견되면
            a[i] -= 1

for x in seq:
    print(x, end = ' ')

8
5 3 4 0 2 1 1 0

4 8 6 2 5 1 3 7
뭔소리지 ..

profile
bee
벌집처럼 밀도있게 차곡차곡 쌓아나가는중
이전 포스트

[Algorithm] 그리디 (Greedy)

다음 포스트

[Algorithm] 동적계획법(DP: Dynamic Programming)

0개의 댓글