백준 18870번: 좌표 압축

문제

https://www.acmicpc.net/problem/18870

코드

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
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    br.readLine();
    Integer[] array = convertStringArrayToIntegerArray(br.readLine().split(" "));
    List<Integer> list = Arrays.asList(array.clone());

    Collections.sort(list);

    Map<Integer, Integer> map = new HashMap<>();
    int index = 0;
    for (int i : list) {
        if (!map.containsKey(i)) {
            map.put(i, index++);
        }
    }

    StringBuilder sb = new StringBuilder();
    for (int i : array) {
            sb.append(map.get(i)).append(" ");
    }

    System.out.println(sb.toString());
}

private static Integer[] convertStringArrayToIntegerArray(String[] args) {
    Integer[] array = new Integer[args.length];
    int i = 0;
    for (String str : args) {
        array[i++] = Integer.parseInt(str);
    }

    return array;
}

흐름

  1. 입력받은 좌표를 저장한 리스트로 수정하면 출력 순서를 맞출 수 없으니 우선 좌표 list를 복사한다.
  2. 복사한 list를 정렬하고 순서대로 반복하면서 좌표값을 key로 index를 저장한다.
    1. {-10 : 0}, {-9, 1}… {4,4}
  3. 입력받은 좌표를 순서대로 반복하면서 map에 key로 index를 가져온다.
  4. 끝

좌표 압축의 이유

좌표 {2 4 -10 4 -9} 압축 전
좌표 {2 4 -10 4 -9} 압축 후
  • 문제의 예제인 좌표 {2 4 -10 4 -9}을 위와 같은 알고리즘으로 압축하면 {2 3 0 3 1}이 되는데 위 그림 처럼 압축된 점들도 같은 동일선상 안에 놓이게 된다.
  • 이렇게 범위가 매우 넓은 좌표의 경우에 좌표를 인덱싱해서 처리 할 경우 손쉽게 처리 할 수 있게 된다.

결과

참고 사이트

댓글 공유

프로그래머스: H-Index

문제

https://programmers.co.kr/learn/courses/30/lessons/42747?language=java

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int solution(int[] citations) {
    int answer = 0;
    int n = citations.length;

    Arrays.sort(citations);

    for (int i = 0; i <= citations[n - 1]; i++) {
        int high = 0;

        for (int j = 0; j < n; j++) {
            if (i <= citations[j]) {
                high++;
            }

            if (i <= high) {
                answer = i;
            }
        }
    }

    return answer;
}

흐름

  1. 논문을 인용한 횟수가 담긴 배열 citations를 정렬

  2. 가장 많이 인용한 횟수 만큼 반복

  3. 0부터 배열 길이만큼 반복하면서 i 값이 인용 횟수보다 작은 경우 i 보다 인용된 횟수가 많은 것이므로 high 변수 증가

  4. h번 이상 인용된 논문이 h편 이상이여야 하므로 i가 high 보다 작을 경우에만 answer에 저장

  5. i가 high보다 커질 경우 answer에 저장되지 않으므로 answer에 마지막으로 저장된 값이 h

  6. 끝

다른 해결방법

코드

1
2
3
4
5
6
7
8
9
10
11
public int solution(int[] citations) {
    Arrays.sort(citations);

    int max = 0;
    for(int i = citations.length-1; i > -1; i--){
        int min = (int)Math.min(citations[i], citations.length - i);
        if(max < min) max = min;
    }

    return max;
}

위 코드의 로직

  1. 배열을 정렬 후 배열의 마지막 값과 1 부터 증가 시키면서 citations의 길이 만큼 반복함

  2. 예를 들어 {0, 1, 3, 5, 6} 인 경우, citations.length는 5, i = 5 - 1 이므로 4, citations.length - i는 5 - 4가 되므로 1임 그런고로, 1과 citations[4]인 6과 비교해서 작은 놈을 min에 저장

  3. 위 과정을 반복하면
    min = Min(6,1)
    min = Min(5,2)
    min = Min(3,3)
    min = Min(1,4)
    min = Min(0,5)
    가 되고 max는 max가 min 보다 작을 때 max에 min 값이 저장되므로 max엔 최종적으로 3이 저장

  • 어떻게 유추해서 푼 건지 이해가 안간다 천재인 듯

결과

1번

번호 속도
테스트 1 통과 (11.43ms, 50.3MB)
테스트 2 통과 (14.71ms, 52.4MB)
테스트 3 통과 (15.13ms, 50.7MB)
테스트 4 통과 (13.74ms, 50.1MB)
테스트 5 통과 (16.49ms, 50.6MB)
테스트 6 통과 (13.86ms, 50MB)
테스트 7 통과 (10.08ms, 52.4MB)
테스트 8 통과 (7.45ms, 52.6MB)
테스트 9 통과 (8.26ms, 52.9MB)
테스트 10 통과 (10.29ms, 50MB)
테스트 11 통과 (17.04ms, 50.9MB)
테스트 12 통과 (8.21ms, 52.8MB)
테스트 13 통과 (15.30ms, 52.5MB)
테스트 14 통과 (13.62ms, 52.7MB)
테스트 15 통과 (15.64ms, 50.5MB)
테스트 16 통과 (0.97ms, 54.7MB)

2번

번호 속도
테스트 1 통과 (1.10ms, 52.4MB)
테스트 2 통과 (1.36ms, 50.5MB)
테스트 3 통과 (1.36ms, 50.8MB)
테스트 4 통과 (0.85ms, 51.9MB)
테스트 5 통과 (0.95ms, 52.5MB)
테스트 6 통과 (1.35ms, 52.7MB)
테스트 7 통과 (1.00ms, 50.6MB)
테스트 8 통과 (0.87ms, 50.9MB)
테스트 9 통과 (1.06ms, 50.5MB)
테스트 10 통과 (1.11ms, 52.6MB)
테스트 11 통과 (1.39ms, 52.5MB)
테스트 12 통과 (0.91ms, 52.6MB)
테스트 13 통과 (1.22ms, 50.3MB)
테스트 14 통과 (1.50ms, 52.5MB)
테스트 15 통과 (1.36ms, 52.3MB)
테스트 16 통과 (0.94ms, 52.5MB)
  • 속도도 압도적…

테스트 케이스

1
2
3
4
5
6
7
8
9
10
11
assertEquals(3, test.solution(new int[] {3,0,6,1,5}));
assertEquals(3, test.solution(new int[] {6,5,4,3,1,1,1,1,1}));
assertEquals(3, test.solution(new int[] {0, 1, 1, 1, 1, 3, 3, 4}));
assertEquals(3, test.solution(new int[] {5, 5, 5, 0}));
assertEquals(2, test.solution(new int[] {2,2,2,2,2}));
assertEquals(4, test.solution(new int[] {5, 5, 5, 5}));
assertEquals(5, test.solution(new int[] {5, 5, 5, 5, 5}));
assertEquals(1, test.solution(new int[] {7}));
assertEquals(3, test.solution(new int[] {4, 3, 3, 3, 3}));
assertEquals(0, test.solution(new int[] {0,0,0,0,0,0}));
assertEquals(3, test.solution(new int[] {6, 5, 3, 1, 0}));

댓글 공유

프로그래머스: 가장 큰 수

문제

https://programmers.co.kr/learn/courses/30/lessons/42746

코드

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
public String solution(int[] numbers) {

    List<Numbers> list = new ArrayList<Numbers>();
    for (int i = 0; i < numbers.length; i++) {
        int number = numbers[i];

        char[] str = String.valueOf(number).toCharArray();
        StringBuilder fourDigitString = new StringBuilder();

        fourDigitString.append(str);
        if (str.length < 4) {

            for (int j = 0; j < 4 - str.length; j++) {
                fourDigitString.append(str[((j) % str.length)]);
            }
        }

        list.add(new Numbers(i, Integer.parseInt(fourDigitString.toString())));
    }

    Collections.sort(list, new Comparator<Numbers>() {

        @Override
        public int compare(Numbers o1, Numbers o2) {
            return o2.value.compareTo(o1.value);
        }
    });

    StringBuilder sb = new StringBuilder();
    int sum = 0;
    for (Numbers n : list) {
        sum += n.value;
        sb.append(numbers[n.postion]);
    }

    if (sum == 0) {
        sb.setLength(0);
        sb.append(0);
    }

    return sb.toString();
}

class Numbers {
    public Integer postion;
    public Integer value;

    public Numbers(Integer postion, Integer value) {
        this.postion = postion;
        this.value = value;
    }
}

흐름

  1. 문제에서 numbers의 원소 값이 1000 이하라고 했으므로 numbers 크기 만큼 돌면서 numbers 안에 값이 4자리가 아닌 경우 자기 숫자를 뒤에 덧붙여서 4자리로 만듬
    • ex) 121 > 1212, 1 > 1111, 23 > 2323, …
  2. 현재 배열의 index와 값을 비교하기 위에 inner class를 하나 만들어서 index와 value를 저장하고 class를 list에 추가
  3. list를 class의 value 값으로 큰 수부터 나오도록 정렬
  4. list를 돌면서 value를 StringBuilder로 붙임
  5. 이 때, 0 0 0 0 일 경우 0 이 되어야 하므로 value들을 모두 더했을 때 값이 0이라면 0 만 붙임
  6. toString() 으로 String형으로 return
  7. 끝

다른 분들의 해결방법

다른분의 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public String solution(int[] numbers) {
    String answer = "";

    List<Integer> list = new ArrayList<>();
    for(int i = 0; i < numbers.length; i++) {
        list.add(numbers[i]);
    }
    Collections.sort(list, (a, b) -> {
        String as = String.valueOf(a), bs = String.valueOf(b);
        return -Integer.compare(Integer.parseInt(as + bs), Integer.parseInt(bs + as));
    });
    StringBuilder sb = new StringBuilder();
    for(Integer i : list) {
        sb.append(i);
    }
    answer = sb.toString();
    if(answer.charAt(0) == '0') {
        return "0";
    }else {
        return answer;
    }
}

위 코드의 로직

  • list에 numbers array를 그대로 저장하고 list의 저장된 element를 앞뒤로 붙여서 정수로 바꾼 후 비교해서 정렬
  • String을 다루는 부분이 많아서 속도는 살짝 떨어지는 듯

결과

1 번

번호 속도
테스트 1 통과 (139.80ms, 83.2MB)
테스트 2 통과 (88.71ms, 67MB)
테스트 3 통과 (167.96ms, 82.4MB)
테스트 4 통과 (17.95ms, 50.7MB)
테스트 5 통과 (129.09ms, 77.4MB)
테스트 6 통과 (116.84ms, 71.2MB)
테스트 7 통과 (1.44ms, 52.3MB)
테스트 8 통과 (1.38ms, 52.7MB)
테스트 9 통과 (1.20ms, 50.2MB)
테스트 10 통과 (1.46ms, 52.6MB)
테스트 11 통과 (1.65ms, 52.9MB)

2 번

번호 속도
테스트 1 통과 (340.75ms, 105MB)
테스트 2 통과 (236.67ms, 82.1MB)
테스트 3 통과 (350.56ms, 126MB)
테스트 4 통과 (80.72ms, 59.7MB)
테스트 5 통과 (300.18ms, 110MB)
테스트 6 통과 (280.61ms, 87.6MB)
테스트 7 통과 (31.26ms, 57.2MB)
테스트 8 통과 (35.88ms, 53.4MB)
테스트 9 통과 (34.27ms, 55.3MB)
테스트 10 통과 (30.44ms, 55.6MB)
테스트 11 통과 (40.16ms, 55.3MB)

테스트 케이스

1
2
3
4
5
6
7
8
9
assertEquals("6210", test.solution(new int[] {6, 10, 2}));
assertEquals("9534330", test.solution(new int[] {3, 30, 34, 5, 9}));
assertEquals("220200", test.solution(new int[] {2,200,20}));
assertEquals("2200", test.solution(new int[] {2,0,20}));
assertEquals("0", test.solution(new int[] {0,0,0}));
assertEquals("21212", test.solution(new int[] {12, 212}));
assertEquals("21221", test.solution(new int[] {212, 21}));
assertEquals("7000", test.solution(new int[] {0, 0, 70}));
assertEquals("1000000", test.solution(new int[] {0, 0, 0, 1000}));

댓글 공유

  • page 1 of 1

Junggu Ji

author.bio


author.job