상세 컨텐츠

본문 제목

[programmers] 프로그래머스 문자열 내림차순으로 배치하기(Python)

Problem Solving/programmers

by HelloMinchan 2020. 6. 12. 16:54

본문

(주)그렙

[programmers] 프로그래머스 문자열 내림차순으로 배치하기

(Python)

(글쓴날 : 2020.06.12)

 


* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.


 

 

프로그래머스 문자열 내림차순으로 배치하기


1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12917

 

코딩테스트 연습 - 문자열 내림차순으로 배치하기

문자열 s에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요. s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 �

programmers.co.kr


2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

주어진 문자열 s를 소문자 대문자 순서로 내림차순 정렬하는 문제입니다.

 

저의 경우, 우선순위 큐를 적용하였고, Python을 사용했습니다.

소문자와 대문자들을 아스키코드로 변환하여 각각 따로 최대 힙 기반 우선순위 큐에 저장한 뒤, 마지막에 모두 꺼내 문자열로 만들어 문제를 해결했습니다.


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import heapq
def solution(s):
    low = []
    cap = []
    
    for alpha in s:
        if alpha.islower():
            heapq.heappush(low, -ord(alpha))
        else:
            heapq.heappush(cap, -ord(alpha))
    
    lowLength = len(low)
    capLength = len(cap)
    
    lowStr = "".join([chr(-heapq.heappop(low)) for _ in range(lowLength)])
    capStr = "".join([chr(-heapq.heappop(cap)) for _ in range(capLength)])
    
    return lowStr + capStr

 

관련글 더보기

댓글 영역