[프로그래머스] Level1 연습문제 문자열 내림차순으로 배치하기 cpp, java 풀이

프로그래머스(Programmers) 코딩테스트 연습

LEVEL 1 문자열 내 마믐대로 정렬하기 연습문제 자바(java) 풀이

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

문제 풀이

이 문제를 푸는 방법 2가지를 생각했습니다.
속도는 아무래도 1번이 평균적으로 훨씬 빠릅니다.

1. 오름차순으로 sorting한 다음에 뒤에서 부터 거꾸로 넣어준다.
2. 모든 문자를 탐색하면서 뒤의 값이 더 크다면 바꿔준다. (버블 정렬 O(len2))

1번 풀이

문자를 char 배열 형태로 바꾸어 이를 바로 내림차순으로 정렬할 수도 있고 오름차순으로 정렬하고 뒤에 부터 넣어줄 수 있습니다.
예를들어 abcdef가 있다면 이를 오름차순 하면 abcdef입니다.
내림 차순은 반대이므로 뒤에부터 쓰면 fedcba로 내림차순이 됩니다.

2번 풀이

이는 버블 정렬을 통해 그때 그때 뒤의 값이 크다면 자리를 바꿔줍니다.
i번 인덱스와 i+1 부터 문자열끝 문자까지 모두 비교해 나갑니다.
예를 들어 "Zbcdefg"가 있다면 처음에 Z와 b를 비교해 b가 더 크기 때문에 자리를 바꿔줍니다. bZcdefg
다음 b와 c를 비교해서 cZbdefg. c와 d를 비교해서 dZbcefg... 이렇게 자리를 바꿔나갑니다.
그러면 문자는 i전까지의 문자들, i문자, i

j사이의 문자, j문자, j

문자열 끝 으로 나뉘게 되므로 이를 '+'연산을 통해 concat 해주면 됩니다.

cpp 풀이

cpp로는 딱 두 줄이면 끝납니다.

#include <string>
#include <algorithm>

using namespace std;

string solution(string s) {
    sort(s.begin(), s.end(), greater<char>());

    return s;
}

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

1번 풀이
애초에 내림차순으로 정렬도 가능

class Solution {
    public String solution(String s){
        String answer = "";
        char[] arr = s.toCharArray();
        // 문자 오름차순 정렬
        Arrays.sort(arr);

        // 거꾸로 넣기
        for(int i=arr.length-1; i>=0; i--)
            answer += arr[i];    
        return answer;
    }
}

2번 풀이

class Solution {
  public String solution(String s) {
      String answer = "";

      // 버블 sort
      for(int i=0; i<s.length()-1; i++){
          for(int j=i+1; j<s.length(); j++){
              // 뒤의 문자가 더 크다면(아스키 코드) 자리를 바꿔준다
              if(s.charAt(i) < s.charAt(j)){
                s = s.substring(0,i) + s.substring(j,j+1) + s.substring(i+1,j) + s.substring(i,i+1) + s.substring(j+1,s.length());
              }
          }
      }
      answer = s;
      return answer;
  }
}