반갑습니다!

[프로그래머스] 파일명 정렬 본문

알고리즘 문제 풀이

[프로그래머스] 파일명 정렬

김덜덜이 2020. 5. 4. 23:36
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr

풀이

파일명을 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