[프로그래머스 lv.2 - 64065] 튜플 // Java regex, Comparator 활용

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

프로그래머스

 

 

열받게도 문제를 또 잘못 읽어버린 ㅡㅡ (정답 풀이 맨 아래)

 

↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓삽질의 시작↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

<문제 이해>

주어지는 집합의 size가 순차적으로 1 -> 2 -> 3 ->4 .... 순이므로 (<== 삽질의 근원), n번째에 주어지는 집합에서 n-1번째 집합을 빼고 남는 원소가 n번째에 주어진 원소가 될 것이다. n 번째에 주어진 원소를 An이라고 하면, 결과로 반환해야하는 튜플은

(A1, A2, A3, A4.....)가 되어야 함. 즉, 주어진 Set들의 Set을 돌면서 이전 Set에 추가된 원소들을 찾으면 될 것.

 

<풀이 구상>

1. input[i]를 돌면서 input[i-1]의 원소들을 하나씩 지워나가고, 남는 원소를 FinalSet에 추가

    ==> 각 시행마다 input[i]의 길이 * input[i-1]의 길이를 탐색하므로 시간 오래걸릴 듯

 

2. input[i]와 input[i-1]를 Set으로 만들어주고, Set끼리의 연산

   ==> 파이썬처럼 Set - Set 연산이 가능한지 알아봐야함

   ==> int[]를 Set으로 만드는 것 자체가 오래걸리지 않을까 ?

   ==> 문제에서 중복이 없음을 보장하고 있는데 Set을 쓰는게 맞는가?

 

<구현가능성>

===============문제를 확인해보니, 주어지는 input이 배열이 아니라 String임============

★String 처리하여 각 input을 받아올 방법 필요

 

-파이썬처럼 Set - Set 연산이 가능한지 ?  ==> .removeAll(c) 메서드로 가능

AbstractSet의 removeAll 메서드

myself.removeAll(Collection c) ==> 내 자신의 원소가 collection c에 있으면 remove.

결국 iterator를 끝까지 도는 것은 매한가지다. 효율은 그닥일 듯. 이 함수를 쓰려면 input string s 를 거꾸로 읽는게좋겠다.

번외로, retainAll이라는 메서드도 있다.

 

==> 어차피 돌거면 그냥 앞에서부터 읽으면서, 그동안 나온 숫자를 모아놓은 SET을 유지   (=> 어차피 중복X 보장이고, 순서를 알아야하므로 List로 하기로 함)하고, i번째 집합의 원소마다 contains를 확인하여 없으면 answer에 붙이고 없으면 pass하도록 하는게 나을 것 같다고 생각함

 

-String을 읽으면서 {와 } 사이의 숫자를 읽는 방법이 필요함

buffer라는 개념이 생각남  ==> 추후 공부하여 정리하기

버퍼는 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역

자세히는 모르지만, 이런 방법을 생각했다

1. {를 만나면 버퍼를 연다 

2. ,를 만나면 버퍼에 저장된 String을 숫자로 변환해 기존 Set에 있는지 검사

3. Set에 없으면 Set에 넣고, 진행 // Set에 있으면 버퍼를 닫고 다음 }까지 진행

 

이를 위해 buf라는 char[] 배열을 선언하였고, 이 배열의 내용물을 Int로 바꾸는 메서드와 buffer를 clear해주는 메서드를 작성하였다. ==> size를 저장하는 변수를 관리해야하는데, 어디 선언해야 예쁜지 몰라서 그냥 List<Character>로 진행

<구현>

 

<문제>

1. 내 Buffer를 String으로 바꾸는 방법에 대한 문제

buffer를 List<Character>로 구현했더니, buffer의 내용물을 String으로 바꿔주는 과정에서

Character List에 담긴 2가 String "2"로 변환되지 않고, "[2]"로 변환되는 문제가 있었다.

 buf의 타입을 바꿔줘야 할 것 같았지만, 일단 코드 작동을 확인하기 위해 정규표현식으로 [와 ]를 벗겨주었더니, 

첫번째 예시에 대해서 통과하여 일단 로직이 잘못되지는 않았다는 걸 알 수 있었다. 그러나,

한자리수를 초과하는 숫자에 대해서 "20"과 같은 String으로 나오는 것이 아니라 "2, 0"으로 나와 숫자로 변환이 안됐다.

buffer.toString()이   "[2, 0]"을 return 했다는 얘기였다.

String.valueOf(buf) 도 마찬가지였다.

String.valueOf() 메서드는 파라미터로 Object가 들어왔을 때, object가 null이 아니면 object의 toString() 함수를 호출한다고 되어있다. 따라서 String.valueOf(buf) ==  buf.toString() 메서드 (현재 buf는 List<Character>인 Object 니까)

List의 toString() 메서드를 보면,

List.toString()

사람이 이 Object에 뭐가 담겨있는지 한 눈에 볼 수 있도록 변환하도록 되어있다.

ArrayList의 element type은 Map이 될 수도 있고, Integer가 될 수도 있고, 어떤 객체든 올 수 있다.

만약 [1, 2, 3, 4, 5, 6]이 List로 담겨있을 때 내가 바랐던 것처럼 하나의 String에 이 요소들을 모두 모으게 되면,

"123456"이 되어 이 List가 한 자리 숫자들을 하나의 element로 담고있다는 정보가 없어질 것이다. 타입이 Map이거나 다른 사용자가 정의한 Class라면 더 어지러울 것이므로, toString()의 return값은 "[요소1, 요소2]" 이런식의 String으로 반환하여 로그를 찍어볼 때 한 눈에 볼 수 있게 해둔 것 같다.

★char[]같은 경우 각 element에 문자가 딱 하나씩 담긴게 보장이 되므로, "abcde"같은 string으로 반환해준다.

int, char, long, float, double, boolean, char[]에 대해서는 String 클래스 안에 정의되어있지만,

int[] 타입의 ints의 경우 Object로 간주해 int[]에 override 되어있는 toString()함수를 호출하게 하는 것을 보면, 숫자 하나, 문자하나 또는 char[]과 같이  헷갈릴만한 소지가 없는 경우에만 String.valueOf를 정의하고 있는 것을 알 수 있다.

 

<문제 해결>

방법1. buf를 List<Character>로 유지할 경우 : StringBuilder 클래스를 사용한다.

방법2. buf를 char[] 로 바꿔줄 경우 : toString()으로 변환 가능. 대신, List의 이점을 포기해햐함

                                                                                         ==>buffer size 저장, buffer clear 간편

 

조금 귀찮아도 방법 2로 하기로 했다.

 

buflen 추가하여 버퍼를 관리

 

<더 큰 문제>

또 문제를 똑바로 안읽었다. input = {{집합1}, {집합2}, {집합3}.... } 에서 input 역시 집합이므로 안에 원소가 길이가 바뀔 수가 있다는 것......... 나는 예시1만 보고 냅다 로직을 구상해버린 것이었다.😭😭

어쩐지 쉽더라 .... 정신적 충격이 심해 조금 쉬었다가 해야겠다..

 

============================================================================================

 

<새로운 풀이>

 

정신이 말짱해지고 오니 왜 저렇게 했는지 모르겠다. 난 정규표현식과 Comparator를 아는데 !!

 

1.input s 에서 처음 등장하는 {{와 마지막에 등장하는 }}를 지워준다.

2.split( " },{ ")로 각 내부집합을 받아온다

3. 2에서 받아온 내부집합은 String[] 인데, custom Comparator를 사용하여 길이순으로 정렬해준다.

4.내부집합의 원소들을 돌면서 Set에 있는지 확인하고, 없으면  tuple에 넣어준다

 

import java.util.*;
class Solution {
    public static int[] solution(String s) {
        List<Integer> tuple = new ArrayList<>();

        String regex = "^\\{\\{|}}$";  // s 시작의 {{, 끝의 }}를 지워줌
        String[] toarr = s.replaceAll(regex,"").split("},\\{");
        Arrays.sort(toarr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        });

        for(String set:toarr){
            String[] nums = set.split(",");
            for(String num:nums){
                int intNum = Integer.parseInt(num);
                if (!tuple.contains(intNum)){
                    tuple.add(intNum);
                    break;
                }
            }
        }
        int[] answer = new int[tuple.size()];
        for(int i = 0; i< tuple.size(); i++){
            answer[i] = tuple.get(i);
        }

        return answer;
    }
}

 

처음 했던 방식보다 훨씬 깔끔하고 쉽게 풀렸다. 애초에 문제를 잘못 이해 했을 경우에도 이렇게 하는게 맞았는데, 깊이 생각 안하고 냅다 풀어버리니까 버퍼에 집착해서 이상하게 풀게 됐던 듯.

test case에서 걸려서 다행이지 hidden case에만 걸렸으면 진짜 오래 고민했을 것 같다.

 

제출 후에 다른사람들의 풀이를 보니 비슷한 풀이가 많았는데, 내 코드를 줄일 여지를 몇 개 찾아 적어놓는다

1. Comparator를 람다식으로 작성 ==> 가독성 좋아보임 (어차피 간단한 comparator니까)

2. java.util.regex의 Pattern과 Matcher를 활용해 input s에서 숫자만 찾고. matcher의 find와 group 활용

     ==> 추후 regex 공부할 때 알아보고 정리하기

3. Set.add에는 boolean 반환값이 있다. List로 하지 않더라도 if (Set.add(num)) ==> num을 tuple에 저장

    과 같은식으로 할 수 있을 것 같다. (Set.add는 중복아닐 때 true 반환). 물론 이 문제에서는 중복인 경우가 주어지지

    않는다고 했으니 중복검사를 안 하는 List.add가 조금이나마 더 효율적이지 않을까....

 

 

<오늘 배운 점>

1. 문제를 똑바로 읽자 제발

2. 문제를 읽었으면 예시를 떠올려보자. 최대한 내가 생각한 풀이가 틀리게 되는 방향으로 생각해보기

3. toString() 메서드에 대한 이해......(왜 그냥 String으로 반환해주지 않는지 이해해서 유익하긴 했다.)