[코딩테스트] 프로그래머스 lv.1 문자열 내 마음대로 정렬하기

HONGKYUMIN (ANTHONY)·2022년 8월 22일
오답노트코딩테스트프로그래머스
0

시간을 많이 썼던 문제이다. 결국 검색해서 힌트를 얻고, 세번째 시도만에 성공했다.

문제 설명

첫번째 시도

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public String[] solution(String[] strings, int n) {
 
        if (n == 0) {
            Arrays.sort(strings);
        } else {
 
            boolean onemore = true;
            while (onemore) {
                for (int i = 1; i < strings.length; i++) {
                    sorting(strings, i, n);
                }
                onemore = checkOneMore(strings, n);
            }
 
        }
        return strings;
    }
 
    private boolean checkOneMore(String[] strings, int n) {
        boolean check = false;
        int tmp = strings[0].charAt(n);
        for (int i = 0; i < strings.length; i++) {
            if (tmp <= strings[i].charAt(n)) {
                tmp = strings[i].charAt(n);
            } else {
                check = true;
                break;
            }
        }
 
        return check;
    }
 
    private boolean sorting(String[] strings, int i, int n) {
        boolean onemore = false;
 
        if (n == 0) {
            Arrays.sort(strings);
        } else if ((int) strings[i - 1].charAt(n) > (int) strings[i].charAt(n)) {
            swap(strings, i - 1, i);
            onemore = true;
        } else if ((int) strings[i - 1].charAt(n) == (int) strings[i].charAt(n)) {
 
            sorting(strings, i, 0);// 여기서 문제임. n+1 번째가 가장 길이가 작은 요소의 길이를 넘어버림.
            onemore = true;
        }
        return onemore;
    }
 
    // i가 바꾸기 전 앞, j가 뒤
    private void swap(String[] strings, int i, int j) {
        String tmp = "";
        tmp = strings[i];
        strings[i] = strings[j];
        strings[j] = tmp;
    }
cs

단순히 하나하나 비교하고 재정렬하는 방법으로 짜보았다. 하지만 몇몇의 예외 처리를 계속 잡지 못했고, 문제도 잘못 이해해서(n번째 이후부터 문자열 사전순으로 이해함) 모든 테스트 케이스에 계속 통과하지 못했다..😥

질문하기에 나처럼 이해를 못했던 분의 조언을 받고 2차 시도..!



두번째 시도

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class sort_string_by_my_will3 {
 
    public static void main(String[] args) {
 
        sort_string_by_my_will ssbmw = new sort_string_by_my_will();
 
        String[] a = { "aaa", "aab", "baa" };
        for (String item : ssbmw.solution(a, 1))
            System.out.println(item);
 
    }
 
    public String[] solution(String[] strings, int n) {
 
        if (n < 1) {
            Arrays.sort(strings);
        } else {
 
            String[] front = new String[strings.length];
            String[][] back = new String[strings.length][2];
 
            // 문자열 자르고 원래 순번 붙이기.
            for (int i = 0; i < strings.length; i++) {
                front[i] = strings[i].substring(0, n);
                back[i][0] = strings[i].substring(n);
                back[i][1] = String.valueOf(i);
            }
 
            // 2차원 배열 정렬
            Arrays.sort(back, Comparator.comparing((String[] o) -> o[0]));
 
            // 잘렸던 앞부분 원래 순번 찾아가서 붙여주고 현 순번으로 업데이트.
            for (int i = 0; i < front.length; i++) {
                for (int j = 0; j < back.length; j++) {
                    if (String.valueOf(i).equals(back[j][1])) {
                        back[j][0] = front[i] + back[j][0];
                        back[j][1] = String.valueOf(i);
                    }
                }
            }
 
            // n번째 문자가 같은 요소들은 따로 모아 0번째 글자 기준으로 정렬하고 바뀐 위치로 들어가기.
            char tmp = back[0][0].charAt(n);
            int start = 0; // 중복 시작 index
            int cnt = 0; // start부터 몇개까지 같은지
            List<String> list = new ArrayList<>();
            
            for (int i = 0; i < back.length; i++) {
 
                if (tmp == back[i][0].charAt(n)) {
                    start = i;
                    // continue;
                } else {
                    tmp = back[i][0].charAt(n);
                }
                for (int j = 0; j < back.length; j++) {
                    if(i == j) continue;
                    else if (tmp == back[j][0].charAt(n)) {
                        cnt++;
                        list.add(back[j][0]);
                        //여기서부터 뭔가 꼬였다 생각.... 이후 코드 구현은 중단하고 검색함..
                    }
                }
            }
 
            // 결과 담기
            for (int i = 0; i < back.length; i++) {
                strings[i] = back[i][0];
            }
 
        }
 
        return strings;
    }
 
}
 
cs

두번째 시도는 배열 안의 문자열들을 n번째 이상(back)의 string만 정렬하고, n번째 이하(front)는 이후 정렬된 배열의 원래 순서를 찾아갈 수 있도록
2차원 배열 {{n이후 string, 원래순서}, ...}
로 짜보았다.
하지만 n번째 문자가 같은 요소들의 사전적 정렬에서 뭔가 꼬였음을 감지..😥



세번째 시도(최종 답안)

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
public class sort_string_by_my_will {
 
    public static void main(String[] args) {
 
        sort_string_by_my_will ssbmw = new sort_string_by_my_will();
 
        String[] a = {"abce", "abcd", "cdx"};
        for (String item : ssbmw.solution(a, 2))
            System.out.println(item);
 
    }
 
    public String[] solution(String[] strings, int n) {
 
        List<String> list = new ArrayList<>();
 
        for (String item : strings) {
            list.add( item.charAt(n) + item);
        }
        
        Collections.sort(list);
        
        for (int i = 0; i < list.size(); i++) {
            strings[i] = list.get(i).substring(1);
        }
 
        return strings;
    }
 
}
 
cs

'n번째 문자 기준 정렬, 이후 n번째 문자 중복 값들을 사전적으로 재배치' 과정이라고 틀에 박혀 생각했던게,
'n번째 문자를 떼서 문자열 앞에 붙여 정렬, 이후 첫 문자 제거' 로 코드 단 6줄 만에 끝나버렸다..😶

👉알고리즘을 풀 때, 문제에 적혀있는 그 과정 순서를 하나하나 절차적으로 짜기 보다는,
결과를 보고, 원리를 이해해서 해석해보자..!!💁‍♂️

profile
HONGKYUMIN (ANTHONY)
매일매일 성장하는 개발자
이전 포스트

[Java] StringBuffer클래스와 StringBuilder클래스

0개의 댓글