그리디 기초 테크닉 익히기2 - 특별한 정렬, 사고 전환, 상쇄, 올바른 순서 부분문자열 몇개 있는지, 원소 상태 바꾸기-

1. 문제1

 

3216번: 다운로드 (acmicpc.net)

3216번: 다운로드

 

2. 풀이

 

생각보다 어렵더라..? 다운로드 하면서 음악 재생시간을 누적해오고..

 

어느 순간에 음악을 재생시키면.. 모든 다운로드 시간을 커버하면서 음악이 연속으로 흐를수 있게 할려면..

 

다운로드가 언제 끝나는지 알아야하는데.. 이게 가능한가??

 

 

 

리스트를 구성하면서 미리 더해서 남은 시간을 구해놓기도 하고..

 

그리디의 기본인 정렬을 해서 짧은 시간부터  다운로드 해나가야하나? 생각은 했는데

 

 

정해진 순서대로 다운받아야하기 때문에.. 정렬은 할 수 없다

 

정직하게 순회하면 i번째 음악 재생시간이랑 다운로드 시간을 알 수 있는데..

 

먼저 0번째 음악 재생시간이랑 다운로드 시간을 저장해두고..

 

1번부터 n-1번까지 순회를 한다

 

매 순회마다 음악 재생시간은 누적해주면서..

 

매 i번째 다운로드 시간이랑 i-1번째까지 누적해온 재생시간을 비교해서..

 

만약 누적해온 재생시간이 다운로드 시간보다 크거나 같다면.. 음악을 재생해서 다운로드 시간을 없애버린다..

 

하지만 누적해온 재생시간이 다운로드 시간보다 짧다면.. 음악 재생을 해도 다운로드 시간이 남으니 그 차이만큼은 다운로드 시간에 써줘야겠다

 

이걸 n-1번까지 순회하면 처음에 다운로드에 얼마나 써야할지 알수 있게 된다

 

from sys import stdin

n = int(stdin.readline())

music = []

for _ in range(n):
    
    d,v = map(int,stdin.readline().split())

    music.append((d,v))

#다운받으면서 음악 재생시간을 누적해가고.. 어느 순간 재생하면 모든 다운 로드 시간을 커버~ X
#처음부터 순회하면서.. 이전에 받은 음악 재생시간으로 다운로드 시간을 상쇄해가며 전체 필요한 다운로드 시간을 구하기 O
answer = music[0][1]
play = music[0][0]

for i in range(1,n):

#누적된 음악 재생시간보다 다운로드 시간이 더 크다면..
#음악 재생시간으로 다운로드 시간을 일부 없애고 남은 시간만큼 다운로드에 쓴다

    if music[i][1] > play:
        
        answer += music[i][1] - play
        play = 0

#누적된 음악 재생시간이 다운로드 시간보다 더 짧다면..
#음악 재생시간을 사용해서 다운로드 시간을 모두 없애버린다

    else:
        
        play -= music[i][1]

    play += music[i][0] #해당 음악을 다운받으면.. 음악 재생시간에 누적해가고..

print(answer)

 

여기서 배울점은 사고 과정을 조금 고쳐서..

 

미리 남은 다운로드 시간을 알고 있어서.. 어느 정도 다운로드 받으면 음악을 재생시켜야지~가 아니라

 

처음부터 끝까지 순회하면서 일단 다운로드하고, 음악 재생시간은 누적해가면서..

 

누적된 재생시간을 이용해서 다음 다운로드 시간에 그 재생시간만큼 없애버리는 방식으로..

 

생각을 바꿔

 

3. 문제2

 

12933번: 오리 (acmicpc.net)

12933번: 오리

 

4. 풀이

 

문자열을 보면서 오리가 몇마리 있는지 알아내기..

 

처음에는 올바른 괄호문자열 문제처럼 스택으로 가볍게 풀 수 있는 문제거니 했지만

 

한마리의 오리가 여러번 울 수 있기 때문에 만만한 문제가 아니다

 

 

오리는 quack 순서로 울어야하니까.. quack가 나오기 전에 q가 나오면 새로운 오리를 배정해야한다고 생각할 수 있다

 

q가 나왔으니 오리 3

 

quq가 나왔으니 오리 2

 

qu_a

    q__q가 나왔으니 오리 1

 

 

리스트의 원소를 오리 1마리가 어디까지 울었는지 나타내도록 해서..

 

문자열을 순회하면서 q가 나왔을때랑 q 이외의 문자가 나왔을때 다르게 전략을 구성하면 될 것 같다

 

q가 나왔을때, 오리를 담은 배열을 순회하면서 오리 1마리가 다 운 상태라면 이미 있는 오리가 또 우는걸로 보는게 유리하다

 

하지만 모든 오리가 다 울지 않은 상태라면.. 새로운 오리가 울었다고 보는게 맞다

 

#오리를 담은 배열
#각 오리는 0(k),1(q),2(u),3(a),4(c) 상태를 가진다
answer = [1]

for i in range(1,n):
    
    #q가 나온다면.. 이미 가지고 있는 오리 배열을 순회
    if s[i] == 'q':

        find = False

        for j in range(len(answer)):
            
            #이미 다 운 오리가 있다면.. 그 오리가 새로 운다고 보는게 유리하다
            if answer[j] == 0:

                answer[j] = 1
                find = True
                break
        
        #가지고 있는 오리 중에 다 운 오리가 없다면.. 새로운 오리가 울었다고 보는게 맞다
        if find == False:

            answer.append(1)

 

 

q 말고 다른 문자가 나온다면.. 가지고 있는 오리 중에 어떤 오리가 울었는지 체크해야한다

 

현재 1이라면 u를 받아야하고, 2라면 a를 받아야하고 3이라면 c를 받아야하고 4라면 k를 받아야하고..

 

0이라면 q를 받아야하고..

 

현재 문자가 어떤 상태가 되어야하는지 체크해서.. 그런 오리가 먼저 발견된다면 거기에 배정해주면 된다

 

그런데 찾지 못한다면?

 

문자열은 올바른 문자열이 아니다

 

#현재 오리 상태가 0이면 q를 받아야하고, 1이면 u를 받아야하고 2면 a를 받아야하고...
order = {'q':0,'u':1,'a':2,'c':3,'k':4}

find = False

no = False

#q 이외의 문자가 온다면...
#오리들의 상태를 순회해서 현재 문자에 맞는 오리가 있는지 검사
for j in range(len(answer)):

    if answer[j] == order[s[i]]:

        answer[j] += 1 #있다면 그 오리에 배정하면 끝

        if answer[j] == 5: #배정하다가 5가 된다면 0으로 바꿔주고

            answer[j] = 0

        find = True
        break

#발견하지 못하면 올바른 문자열이 아니다
if find == False:
    no = True
    break

 

 

이렇게 문자열을 다 순회한다음.. 오리가 몇마리 있는지 체크하면 끝

 

올바른 문자열이라면 오리들이 모두 운 상태여야하므로, 배열이 전부 0을 원소로 가져야한다

 

s = input()

n = len(s)

#현재 오리 상태가 0이면 q를 받아야하고, 1이면 u를 받아야하고 2면 a를 받아야하고...
order = {'q':0,'u':1,'a':2,'c':3,'k':4}

if s[0] != 'q':
    
    print(-1)

else:
    
    #오리를 담은 배열
    #각 오리는 0(k),1(q),2(u),3(a),4(c) 상태를 가진다
    
    answer = [1]
    no = False #불가능한 문자열 여부

    for i in range(1,n):
        
        if s[i] == 'q': #q가 나온다면.. 이미 가지고 있는 오리 배열을 순회
            
            find = False

            for j in range(len(answer)):
                
                #이미 다 운 오리가 있다면.. 그 오리가 새로 운다고 보는게 유리하다
                if answer[j] == 0:
                    
                    answer[j] = 1
                    find = True
                    break
                    
             #가지고 있는 오리 중에 다 운 오리가 없다면.. 새로운 오리가 울었다고 보는게 맞다
            if find == False:
                
                answer.append(1)
        
        else:

            find = False
            
            #q 이외의 문자가 온다면...
            #오리들의 상태를 순회해서 현재 문자에 맞는 오리가 있는지 검사

            for j in range(len(answer)):
                
                if answer[j] == order[s[i]]: #있다면 그 오리에 배정하면 끝
                    
                    answer[j] += 1

                    if answer[j] == 5: #배정하다가 5가 된다면 0으로 바꿔주고
                        
                        answer[j] = 0

                    find = True
                    break
                    
            #발견하지 못하면 올바른 문자열이 아니다
            if find == False:
                no = True
                break
    
    if no: #애초에 올바르지 않은 문자열이라면...
        
        print(-1)
    
    else:
        
        #오리 배열을 순회해서..
        
        c = 0

        for i in range(len(answer)):
            
            if answer[i] != 0: #올바른 문자열이라면 모든 원소가 0이어야한다
                
                c = -1
                break
            
            else:
                
                c += 1
        
        print(c)

 

 

5. 문제3

 

27922번: 현대모비스 입사 프로젝트 (acmicpc.net)

27922번: 현대모비스 입사 프로젝트

 

 

6. 풀이

 

n개중 k개를 선택해서 각각 원소들을 합하여 a,b,c를 얻는다면.. 이 중 2가지 합 a+b, a+c, b+c중 최댓값을 구하는 문제

 

처음에는 a 기준으로 내림차순 정렬해서.. 각 원소 합 구해서 최댓값 찾고

 

b기준으로 내림차순 정렬해서 각 원소 합 구해서 최댓값 구하고

 

c기준으로 내림차순 정렬해서 각 원소 합 구해서 최댓값 구하고..

 

셋 중 최댓값을 답으로 했지만 반례가 있는지..오답이더라고

 

근데 원소가 (a,b,c)로 이루어져있다면.. 결국에 목표로 하는 건 a+b, a+c, b+c중 최댓값을 구하면 된다

 

그렇다면 애초에 원소를 (a+b,a+c,b+c)로 구성해놓고

 

이들을 각각 a+b기준으로 내림차순 정렬후 k개 합 구해서 최댓값 찾고

 

a+c 기준으로 내림차순 정렬후 k개 합 구해서 최댓값 찾고

 

b+c 기준으로 내림차순 정렬후 k개 합 구해서 최댓값 찾고

 

이들을 비교해서 최종 최댓값을 구한다

 

"""a 기준으로 내림차순 정렬해서.. 각 원소 합 구해서 최댓값 찾고

 

b기준으로 내림차순 정렬해서 각 원소 합 구해서 최댓값 구하고

 

c기준으로 내림차순 정렬해서 각 원소 합 구해서 최댓값 구하고..""" 이렇게 한다고 해서 a+b, a+c, b+c들이 최댓값이 되리라는 보장은 없다 이거지

 

from sys import stdin

n,k = map(int,stdin.readline().split())

lecture = []

#애초에 원소를 (a+b,b+c,a+c)로 구성하고..
for _ in range(n):
    
    a,b,c = map(int,stdin.readline().split())
    lecture.append((a+b,b+c,c+a))

answer = 0

#a+b, b+c, c+a 각각 기준으로 내림차순 정렬한다음
#각각에서 k개를 골라 합하면 각각에서 최댓값이 될거고
#전체에서 최댓값 비교해서 갱신
for i in range(3):

    lecture.sort(key = lambda item: -item[i])

    a = 0

    for j in range(k):

        a += lecture[j][i]
        
    if answer < a:
        
        answer = a

print(answer)

 

 

7. 문제4

 

29198번: 이번에는 C번이 문자열 (acmicpc.net)

29198번: 이번에는 C번이 문자열

 

8. 풀이

 

처음에는 문제 설명대로 n개의 문자열 리스트를 받아서 1) 오름차순 정렬하고

 

2) 이 중 앞선 k개를 선택해서 이들을 모두 붙이고, 3) 오름차순 정렬하면 가장 앞선 문자열이 나오겠다

 

라고 생각했는데.. 틀리더라고

 

근데 조금 더 생각해보면..

 

3)에 km 길이의 문자열을 만들어서 문자를 재배치하는 과정에서... 사실 결국 모든 문자를 재배치할 수 있는거나 다름 없거든?

 

그래서 km길이의 문자열이 애초에 가장 앞선 문자열이 나와줘야한다 이 말이다

 

그러니까 처음에 n개의 문자열 리스트를 받을때 1) 애초에 각 문자열들을 오름차순으로 미리 재배치해야하지 않냐 이거지

 

2) 그리고 그렇게 받은 문자열 리스트를 또 오름차순으로 정렬해주고

 

3) 여기서 앞선 k개 문자열을 고른 다음 붙이고..

 

4) 다시 오름차순으로 정렬해줘야 가장 앞선 문자열이 나오겠다

 

from sys import stdin

n,m,k = map(int,stdin.readline().split())

string = []

#각 문자열을 정렬해주고
for _ in range(n):
    
    s = list(stdin.readline().rstrip())
    s.sort()
    string.append(''.join(s))

#문자열 리스트를 정렬해서 k개를 고르고
string.sort()

string2 = []

for i in range(k):
    
    string2.append(string[i])

#이렇게 붙인 문자열을 또 정렬해주고
string2 = list(''.join(string2))

string2.sort()

print(''.join(string2))