[BOJ알고리즘, C++]#2752_30, 정렬 알고리즘, 퀵 정렬, median-of-three

2024. 1. 26. 17:46· 문제 풀이/BOJ 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. 퀵 정렬
  4. 2. 30의 배수는 자릿수의 합이 3으로 나누어 떨어지며, 마지막 자릿수는 0이다!
  5. #3. 코드

 

#1. 문제

 

10610번: 30

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한

www.acmicpc.net

 


 

#2. 풀이

 

1. 퀵 정렬

 

[알고리즘]#3_정렬 알고리즘

#1. 개념 1. 정렬 알고리즘 [정의] : 정렬 알고리즘은 데이터를 특정한 순서로 재배치하는 알고리즘입니다. 정렬 순서는 일반적으로 오름차순(ascending order/less) 또는 내림차순(descending order/greater)으

webddevys.tistory.com

 

[정의] : 퀵 정렬 알고리즘은 분할-정복 기반의 정렬 알고리즘으로, 피벗 원소를 기준으로 왼쪽은 피벗 원소보다 작은 원소들, 오른쪽은 큰 원소들로 정렬하고, 피벗 원소를 기준으로 두 부분 배열로 분할하여 재귀적으로 정렬 작업을 수행합니다. 퀵 정렬 알고리즘의 평균 시간 복잡도는 O(n log n)이지만, 최악의 경우 O(n²)입니다. 이때, 최악의 경우를 방지하기 위해, 퀵 정렬 알고리즘 수행 과정에서 피벗 원소의 선택을 "중간 값"으로 선택하는 Median-of-three 방법을 사용할 수 있습니다.

 

2. 30의 배수는 자릿수의 합이 3으로 나누어 떨어지며, 마지막 자릿수는 0이다!

 

  1. 입력받은 숫자를 문자열 형식의 변수에 저장하고, 사전 역순으로 퀵 정렬을 수행합니다.
  2. 각 자릿수를 더해, 3으로 나누어 떨어지는지 확인하는 동시에, 마지막 자릿수가 0인지 확인합니다.

 


 

#3. 코드

 

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

string N;

int FindMedian(string& str, int l, int r)
{
    int m = l + (r-l)/2;

    if(str[l] > str[m])
    {
        swap(str[l], str[m]);
    }
    if(str[l] > str[r])
    {
        swap(str[l], str[r]);
    }
    if(str[m] > str[r])
    {
        swap(str[m], str[r]);
    }
    return m;
}

int Partition(string& str, int l, int r)
{
    int pivIdx = FindMedian(str, l, r);
    swap(str[pivIdx], str[r]);

    int piv = str[r];
    int i = l-1;

    for(int j=l; j<r; ++j)
    {
        if(str[j] >= piv)
        {
            i++;
            swap(str[j], str[i]);
        }
    }
    swap(str[i+1], str[r]);
    return i+1;
}

void QuickSort(string& str, int l, int r)
{
    if(l < r)
    {
        int piv = Partition(str, l, r);

        QuickSort(str, l, piv-1);
        QuickSort(str, piv+1, r);
    }
}

void FindMaxMultipleOf30(string& str)
{
    bool hasZero = false;
    int sum = 0;

    for(const auto& c : str)
    {
        sum += c-'0';
        if(c == '0') hasZero = true;
    }

    if(hasZero && sum%3 == 0)
    {
        cout << str;
    }
    else{
        cout << -1;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    // #1. 퀵 정렬
    QuickSort(N, 0, N.length()-1);

    // #2. 30의 배수중 최대가 되는 수
    FindMaxMultipleOf30(N);

    return 0;
}

 


 

 

 

 

저작자표시 (새창열림)

'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글

[BOJ알고리즘, C++]#10825_국영수, 정렬, 병합 정렬  (1) 2024.02.05
[BOJ알고리즘, C++]#11656_접미사 배열, 정렬, 퀵 정렬, 병합 정렬  (0) 2024.02.05
[BOJ알고리즘, C++]#11399_ATM, 정렬, 병합 정렬, 퀵 정렬  (1) 2024.01.26
[BOJ알고리즘, C++]#2217_로프, 정렬 알고리즘, 병합 정렬  (0) 2024.01.26
[BOJ알고리즘, C++]#1956_운동, 최단 경로, 플로이드, 플로이드 워셜  (1) 2024.01.26
  1. #1. 문제
  2. #2. 풀이
  3. 1. 퀵 정렬
  4. 2. 30의 배수는 자릿수의 합이 3으로 나누어 떨어지며, 마지막 자릿수는 0이다!
  5. #3. 코드
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#10825_국영수, 정렬, 병합 정렬
  • [BOJ알고리즘, C++]#11656_접미사 배열, 정렬, 퀵 정렬, 병합 정렬
  • [BOJ알고리즘, C++]#11399_ATM, 정렬, 병합 정렬, 퀵 정렬
  • [BOJ알고리즘, C++]#2217_로프, 정렬 알고리즘, 병합 정렬
Hardii2
Hardii2
개발 블로그Hardii2 님의 블로그입니다.
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • C++
  • 개발
  • BFS
  • 기술 질문
  • 디자인 패턴
  • Effective C++
  • unreal
  • 우선순위 큐
  • 최단 경로
  • DP
  • BOJ
  • set
  • stl
  • 그래프
  • dfs
  • programmers
  • 트리
  • Unreal Blueprint
  • 정렬
  • 알고리즘

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#2752_30, 정렬 알고리즘, 퀵 정렬, median-of-three
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.