창업 (16890번) - 백준 (BOJ)

https://www.acmicpc.net/problem/16890

16890번: 창업

 

 

백준 - 창업 (16890번)

 

난이도 : Gold 1

알고리즘&자료구조 : Greedy (그리디) & Sorting (정렬)

---

★ 핵심 Idea ★

 

아래 두 가지 경우를 나눠서, 그리디(Greedy)하게 구현하는 것이 포인트이다.

 

1. 구사과의 문자 중 사전에서 가장 앞쪽 문자가,

큐브러버의 문자 중 사전에서 가장 뒤쪽 문자보다 사전에서 앞서는 경우

ex) 구사과 : 'abc' / '큐브러버' : 'xyz'

 

2. 구사과의 문자 중 사전에서 가장 앞쪽 문자가,

큐브러버의 문자 중 사전에서 가장 뒤쪽 문자와 사전에서 같거나 뒤에 있는 경우

ex) 구사과 : 'xyz' / '큐브러버' : 'abc'

 

 

< 전체 코드 >

 

class CompanyName():
    def __init__(self, koo, cube):
        N = len(koo)
        koo = sorted(koo, reverse=True)[~((N>>1)+(1 if N&1 else 0))+1:]
        cube = sorted(cube)[~(N>>1)+1:] if N>1 else []
        head, tail = [], []
        turn = 0
        while koo and cube and koo[-1] < cube[-1]:
            if turn:
                head.append(cube.pop())
            else:
                head.append(koo.pop())
            turn ^= 1
        koo = koo[::-1]
        cube = cube[::-1]
        while koo and cube:
            if turn:
                tail.append(cube.pop())
            else:
                tail.append(koo.pop())
            turn ^= 1
        self.final = head + (koo if koo else cube) + tail[::-1]


if __name__ == '__main__':
    cands = CompanyName(input().rstrip(), input().rstrip())
    print(''.join(cands.final))

---

 

① 구사과의 문자열 "koo"는 내림차순, 큐브러버의 문자열 "cube"는 오름차순 정렬한다.

그리고 각 문자열의 뒤쪽에서 앞으로 뽑게 될 개수의 문자만큼만 인덱싱해서 저장한다.

 

N = len(koo)
koo = sorted(koo, reverse=True)[~((N>>1)+(1 if N&1 else 0))+1:]
cube = sorted(cube)[~(N>>1)+1:] if N>1 else []

 

 

 

② "koo"에서 사전 기준 가장 앞쪽 문자가,

"cube"의 사전 기준 가장 뒤쪽 문자보다 사전에서 앞서는 경우

[ ex) 구사과 : 'abc' / '큐브러버' : 'xyz' ]

그리디하게 "koo"에서는 사전 기준 가장 앞 문자를,

"cube"에서는 사전 기준 가장 뒷쪽 문자를 하나씩 꺼내서 "head"에 append한다.

 

head = []
turn = 0
while koo and cube and koo[-1] < cube[-1]:
    if turn:
        head.append(cube.pop())
    else:
        head.append(koo.pop())
    turn ^= 1

 

 

 

③ "koo"에서 사전 기준 가장 앞쪽 문자가,

"cube"의 사전 기준 가장 뒤쪽 문자보다 사전에서 동일하거나 뒤에 있는 경우

[ ex) 구사과 : 'xyz' / '큐브러버' : 'abc' ]

그리디하게 "koo"에서는 사전 기준 가장 뒷 문자를,

"cube"에서는 사전 기준 가장 앞쪽 문자를 하나씩 꺼내서 "tail"에 append한다.

 

("koo"의 모든 문자가 "cube"의 모든 문자보다 사전 상 뒤에 있기 때문에,

구사과 입장에서는 "koo"의 문자 중 사전 상 가장 뒤쪽 문자를, 회사 이름의 뒤쪽에 두는 것이 유리하다.)

 

(그래서 밑의 ④ 단계에서 정답을 출력할 때, tail을 거꾸로 뒤집어서 붙인다.)

 

tail = []
koo = koo[::-1]
cube = cube[::-1]
while koo and cube:
    if turn:
        tail.append(cube.pop())
    else:
        tail.append(koo.pop())
    turn ^= 1

 

 

 

④ "head"에 ("koo" 또는 "cube")에서 남은 문자 1 개를 뒤에 이어붙이고,

마지막으로 "tail"을 거꾸로 뒤집은 것을 뒤에 이어붙인다.

그리고 그것을 출력하면 정답이 된다.

 

self.final = head + (koo if koo else cube) + tail[::-1]
print(''.join(cands.final))