Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 플로이드-와샬
- 문자열
- 완전탐색
- Kotlin
- JUnit 5
- 백트래킹
- mst
- 백준
- 프로그래머스
- swea
- 알고리즘
- 세그먼트 트리
- 동적계획법
- 구현
- 에라토스테네스의 체
- Effective Java
- 수학
- 스택
- 위상정렬
- CS
- 이분탐색
- 유니온 파인드
- dfs
- BFS
- 시뮬레이션
- 후니의 쉽게 쓴 시스코 네트워킹
- 투 포인터
- 그리디
- java
- Network
Archives
반갑습니다!
[프로그래머스] 파일명 정렬 본문
풀이
파일명을 HEAD와 NUMBER로 분리하여 문제의 주어진 조건을 기준으로 compare
함수를 정의하여 stable_sort
함수를 통해 해결하였다. Java의 경우 Comparator를 구현해서 해결했다.
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// HEAD와 NUMBER 분리
pair<string, int> parse_head_tail(string file) {
pair<string, int> ret;
int idx = 0;
// HEAD를 분리하기 위해 탐색
for (char c : file) {
if ('0' <= c && c <= '9') break;
idx++;
}
int num = 0;
// NUMBER를 분리하기 위해 탐색
for (int i = idx; i < file.length(); i++) {
if (!('0' <= file[i] && file[i] <= '9')) break;
num = num * 10 + (file[i] - '0');
}
// HEAD, NUMBER 리턴
return { file.substr(0, idx), num };
}
bool cmp(const string& a, const string& b) {
pair<string, int> file_a = parse_head_tail(a);
pair<string, int> file_b = parse_head_tail(b);
// 대문자로 변환
for (char& c : file_a.first) c = toupper(c);
for (char& c : file_b.first) c = toupper(c);
// HEAD가 일치하면 NUMBER를 비교해서 정렬정렬
if (file_a.first == file_b.first) return file_a.second < file_b.second;
// HEAD로 정렬
return file_a.first < file_b.first;
}
vector<string> solution(vector<string> files) {
stable_sort(files.begin(), files.end(), cmp);
return files;
}
Java
import java.util.Arrays;
import java.util.Comparator;
class Pair {
String head;
int number;
public Pair(String head, int number) {
this.head = head;
this.number = number;
}
}
class Solution {
// HEAD NUMBER 분리
public Pair parseHeadNumber(String str) {
int number = 0;
int idx = 0;
// HEAD를 분리하기 위해 탐색
for (char c : str.toCharArray()) {
if ('0' <= c && c <= '9') break;
idx++;
}
// NUMBER를 분리하기 위해 탐색
for (int i = idx; i < str.length(); i++) {
if (!('0' <= str.charAt(i) && str.charAt(i) <= '9')) break;
number = 10 * number + (str.charAt(i) - '0');
}
// HEAD, NUMBER 리턴
return new Pair(str.substring(0, idx), number);
}
public String[] solution(String[] files) {
Arrays.sort(files, new Comparator<>() {
@Override
public int compare(String o1, String o2) {
Pair p1 = parseHeadNumber(o1);
Pair p2 = parseHeadNumber(o2);
// 대문자로 변환
String h1 = p1.head.toUpperCase();
String h2 = p2.head.toUpperCase();
// HEAD가 다르면 HEAD를 비교해서 정렬
if (!h1.equals(h2)) return h1.compareTo(h2);
// HEAD가 일치하면 NUMBER를 비교해서 정렬
if (p1.number == p2.number) return 0;
else return Integer.compare(p1.number, p2.number);
}
});
return files;
}
}
'알고리즘 문제 풀이' 카테고리의 다른 글
[프로그래머스] 방금그곡 (0) | 2020.05.06 |
---|---|
[백준] 2665 미로만들기 (0) | 2020.05.05 |
[프로그래머스] 압축 (0) | 2020.05.04 |
[백준] 14503 로봇 청소기 (0) | 2020.05.04 |
[백준] 1194 달이 차오른다, 가자. (0) | 2020.05.03 |