[2019 카카오 개발자 겨울 인턴십] 튜플 Java 풀이

PROBLEM

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

SOLUTION

  1. 주어지는 튜플은 중복되는 원소가 없고,
  2. 표현된 집합들은 고유의 개수를 가지고 있다.

결과로 구해야하는 튜플에서 첫 번째 요소는 개수가 1개인 집합의 원소이고, 두 번째 요소는 개수가 2개인 집합에서 등장했던 원소를 제외한 원소이다. 즉, 집합의 길이 순으로 하나씩 가져오면서, 이미 등장했던 원소는 무시해야한다.

예를 들어, "[[4,2,3],[3],[2,3,4,1],[2,3]]"에서

  • 튜플의 첫 번째 요소는 [3]에 해당하는 3이고,
  • 두 번째 요소는 [2,3]에서 3을 제외한 2이고,
  • 세 번째 요소는 [4,2,3]에서 3, 2를 제외한 4이고,
  • 네 번째 요소는 [2,3,4,1]에서 3, 2, 4를 제외한 1이다.
  • 따라서 튜플은 [3, 2, 4, 1]이다.

주어지는 문자열을 탐색하면서, 집합의 길이 별로 나누어 저장한다. 각 집합 속에 숫자들을 하나씩 가져오는데, 순서는 유지하면서 중복을 제거하는 LinkedHashSet 컬렉션을 사용했다.

SOURCE CODE (JAVA)

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

import java.util.*;

class Solution {
  static final int MAX_LENGTH = 500;

  public int[] solution(String s) {
    // 양끝 중괄호 제거
    s = s.substring(1, s.length() - 1);

    // 원소 개수 별로 집합이 존재한다.
    String[] setByCount = new String[MAX_LENGTH + 1];

    // 문자열을 탐색하면서,
    // 원소가 1개인 것은 setByCount[1]에, 원소가 2개인 것은 setByCount[2]에, 이런식으로 저장한다.
    int strCursor = 0;
    int lengthOfSet = 0;

    while (strCursor < s.length()) {
      char c = s.charAt(strCursor);

      if (c == '{') {
        StringBuilder sb = new StringBuilder();
        int elementCount = 1;
        while (true) {
          c = s.charAt(++strCursor);
          if (c == '}')
            break;
          if (c == ',')
            elementCount++; // 콤마 개수가 집합 속 숫자 개수
          sb.append(c);
        }
        setByCount[elementCount] = sb.toString();
        lengthOfSet++;
      }

      strCursor++;
    }

    // setByCount[]를 1부터 반복하면서
    // 숫자들을 linkedSet에 삽입한다. 순서는 유지하면서 중복은 사라진다.
    LinkedHashSet<Integer> linkedSet = new LinkedHashSet<>();
    for (int i = 1; i <= lengthOfSet; i++) {
      String[] splitted = setByCount[i].split(",");
      for (String spl : splitted) {
        linkedSet.add(Integer.parseInt(spl));
      }
    }

    // linkedSet을 answer[]로 옮긴다.
    int answerIdx = 0;
    int[] answer = new int[lengthOfSet];
    Iterator<Integer> it = linkedSet.iterator();
    while (it.hasNext())
      answer[answerIdx++] = it.next();

    return answer;
  }
}

OFF THE RECORD

다른 사람들의 풀이를 보니 단순하게 등장하는 숫자의 개수를 세서 정렬하여 풀었던데, 너무 복잡하게 생각했네…

댓글 남기기

관련있는 다른 게시글