정렬

[프로그래머스 Lv.2] 가장 큰 수 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이주어진 숫자들을 가지고 가장 큰 수를 만들면 되는 문제이다. 그렇기에 가장 큰 수를 만들 수 있는 방법을 먼저 고민해야 한다.쉽게 생각할 수 있듯이 높은 자릿수에 큰 수가 위치하면 된다. 그렇기에 배열 내의 숫자를 가장 높은 자릿수의 내림차순으로 정렬하고, 이를 하나로 합치면 된다.10, 7, 3이 있는 상황을 예로 들어보자. 그렇다면 높은 자릿수에 가장 큰 수가 위치한 7, 3, 10..

[프로그래머스 Lv.2] H-Index (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42747 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이정렬한 인용 횟수의 배열과 인덱스와 전체 길이를 사용해서 문제를 해결할 수 있다.def solution(citations): citations.sort() # 배열 정렬 idx = 0 length = len(citations) if citations[idx] > length: # 인용 횟수의 최소값이 이미 전체 논문 수를 초과한다면 return ..

(C++) 백준 2910번 - 빈도 정렬

문제 링크 : https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 문제 풀이 stable_sort와 커스텀 비교 함수를 사용하여 풀이하였다. pair를 사용해 값과 빈도수를 동시에 저장하는 것과 stable_sort를 사용하는 것이 중요하다고 할 수 있다. #include #include #include #define X first #define Y second using namespace std; int n, c; vector v; // 첫번째 int는 값, 두번째 int는 나타난 빈도수..

(C++) 백준 1181번 - 단어 정렬

문제 링크 : https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 풀이 sort 함수와 커스텀 비교 함수를 사용하여 단어를 정렬하여 풀이를 진행하였다. 다만 C++ vector에서의 중복 제거를 처음 사용해 보아서 조금 어려움도 있었다. ※ unique 함수는 중복된 값들을 뒤로 보내고, 중복된 값들의 시작 위치를 반환한다. ※ erase 함수는 시작 위치부터 종료 위치까지의 값을 모두 제거한다. #include #include #..

(C++) 백준 1431번 - 시리얼 번호

문제 링크 : https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 문제 풀이 sort 함수를 사용하고, 커스텀 비교 함수를 만들어 이를 활용함으로써 풀이를 진행하였다. #include #include using namespace std; string arr[51]; int n; string tmp; bool cmp(string &s1, string &s2){ // 커스텀 비교 함수 if(s1.size() != s2.size()) return ..

(C++) 백준 15688번 - 수 정렬하기 5

문제 링크 : https://www.acmicpc.net/problem/15688 15688번: 수 정렬하기 5 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이며, 같은 수가 여러 번 중복될 수도 있다. www.acmicpc.net 문제 풀이 계수 정렬(Counting Sort)을 이용한 풀이이다. 등장 횟수를 배열에 저장하고, 등장 횟수만큼 해당 숫자를 출력하는 형식으로 풀이했다. #include using namespace std; int a[2000002]; // 해당 숫자(-1000000~1000000)이 몇 번 나타나는지 저장하는 배열 int n, tmp; int mai..

(C++) 백준 11728번 - 배열 합치기

문제 링크 : https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 문제 풀이 Merge Sort를 활용하여 풀이하였다. 이미 병합할 배열들이 정렬되어 있기에 두 배열의 최솟값을 비교하여 더 작은 최솟값을 출력하는 방식으로 풀이하였다. #include using namespace std; int a[1000001]; int b[1000001]; int n, m, tmp, ida, idb; int main() { i..

(Python) 백준 11651번 - 좌표 정렬하기 2

문제 링크 : https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 풀이 11650번 문제와 정렬 순서가 바뀌었을 뿐, 동일한 정렬 문제로 볼 수 있다. sort() 함수에 key로 lambda 함수를 넘겨주게 되면, 이 함수의 반환값을 기준으로 순서대로 정렬하게 된다. 여기서는 x[1], x[0] 순으로, 즉 리스트의 두번째 요소인 y좌표로 정렬 후에 첫번째 요소인 x좌표를 기준으로 정렬하게..

(Python) 백준 11650번 - 좌표 정렬하기

문제 링크 : https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 풀이 sort() 함수에 key로 lambda 함수를 넘겨주게 되면, 이 함수의 반환값을 기준으로 순서대로 정렬하게 된다. 여기서는 x[0], x[1] 순으로, 즉 리스트의 첫번째 요소인 x좌표로 정렬 후에 두번째 요소인 y좌표를 기준으로 정렬하게 되는 것이다. import sys num = int(sys.stdin.readlin..

(Python) 백준 10814번 - 나이순 정렬

문제 링크 : https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 풀이 sort() 함수에 key로 lambda 함수를 넘겨주게 되면, 이 함수의 반환값을 기준으로 순서대로 정렬하게 된다. 여기서는 x[0], 즉 리스트의 첫번째 요소인 age를 기준으로 정렬하게 되는 것이다. import sys num = int(sys.stdin.readline()) arr = [] for _ in range(num): age, name = map(str, sys.st..