[프로그래머스] level2. 튜플 (자바 JAVA)

[ 문제 ]  [프로그래머스] level2. 튜플 (자바 JAVA)

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64065

코딩테스트 연습 - 튜플

 

---

# 접근 방법 및 풀이 

 

• 문제보고 쉽다고 생각했는데 생각보다 풀이가 훠~~~~얼씬 오래걸렸다. {{},{},{}} <- 이 형태의 문자열 파싱때문이기도하다..
• 먼저 문제는 튜플이 표현하는 집합이 주어졌을 때, 튜플 배열을 뽑아내는 것이다. 그리고 집합안의 원소의 순서는 뒤바껴도 상관없다고 되어있다.
• 문제 예시처럼 {2,1,3,4}라는 튜플 배열이 주어졌을때, {a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4} 형태로 튜플집합을 만들 수 있고, {} < 이 집합기호 안에 들어있는 원소의 순서는 뒤바껴도 된다. 순서가 다르면 다른 튜플이기때문이다.
• 따라서  {a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4} 가  {a1}, {a2, a1}, {a3, a2, a1}, {a4, a2, a1, a3} 이런 형태로 나와도 가능하다.
• 이런 집합이 주어지고 튜플배열을 return하면 답이다. 
• 여기서 한개를 뽑고, 두개를 뽑고, 3개를 뽑고 ... n개를 뽑기 때문에 일단 {}의 길이만큼 오름차순으로 정렬해야된다고 생각했다.
• {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}  ->  {{2}, {2, 1}, {1, 2, 3},  {1, 2, 4, 3}} 이렇게 {}집합길이만큼 정렬한 후 앞에서부터 숫자를 하나씩 뽑는다. 이때 중복되어 있는 숫자를 제외해서 뽑으면 된다.
• 따라서 set을 떠올렸는데, 어떤 숫자가 몇개를 가지고있는지 체크하면 더 편할것 같아서 hashMap을 이용했다.
•  {{2}, {2, 1}, {1, 2, 3},  {1, 2, 4, 3}} 이형태의 튜플을 차례대로 보면 아래와 같이 map에 저장된다.

• key	value
  2	4
  1	3
  3	2
  4	1

• 그리고 value값이 큰 내림차순으로 key를 뽑아 int[] answer배열에 하나씩 담아주면 된다.
• 여기서 첫번째 풀이는 map을 value로 sort시키는 것이다. 그러기 위해선 key와 value가 들어가있는 entrySet()을 이용하는데, 이부분은 잘 몰라서 인터넷 찾아봤다. 
• 그런데 형태가 복잡했다. 아무래도 구글링 가능한 코테면 몰라도 이렇게 안 써본걸 실전에서 바로 쓸 수는 없을 것 같아서 두번째 풀이를 사용했다.
• 두번째 풀이는 map.keySet()을 사용했다. for-each문으로 map에 key값을 하나씩 불러와 answer[]을 채워주는 형태다.
• 위의 예시로 map의 size는 4다. 
• answer[맵의 사이즈 - 맵의 value] = key를 해주면 되는 간단한 문제였다.
• answer[4 - 4] = 2, answer[4-3] = 1, answer[4-2] = 3, answer[4-1] = 4
• 그리고 {{}} 형태의 String 파싱은 StringTokenizer를 2개 이용해서 파싱했다.
• 먼저, {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}} 형태에서 맨 앞 뒤에 { }를 떼어준다.
• {1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2} 그다음 StringTokenizer를 이용해서 "{}"기준으로 분리한다.
• StringTokenizer.nextToken()을 이용하면 1,2,3  / 2,1  / 1,2,4,3   / 2 형태로 값이 떨어진다.
• 다시한번 StringTokenizer을 이용해 ","기준으로 분리하면 1 2 3 < 형태의 숫자 값이 떨어진다.
• 자세한건 코드참조

# 주의할 점 

 

• {{}}튜플 파싱 정확하게 하기.

 

JAVA 코드

첫번째 풀이

import java.util.*;
import java.util.Map.Entry;
class Solution {  
    public static int[] solution(String s) {
        s = s.substring(1, s.length());
        StringTokenizer st = new StringTokenizer(s, "{}");
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        while(st.hasMoreTokens()) {
        	StringTokenizer st2 = new StringTokenizer(st.nextToken(), ",");
        	while(st2.hasMoreTokens()) {
        		int num = Integer.parseInt(st2.nextToken());
        		map.put(num, map.getOrDefault(num, 0)+1);
        	}
        }
        List<Entry<Integer, Integer>> answer = new ArrayList<>(map.entrySet());
        answer.sort(Entry.comparingByValue(Collections.reverseOrder()));
        int ans [] = new int[answer.size()];
        for(int i = 0; i < answer.size(); i++) {
        	ans[i] = answer.get(i).getKey();
        }
        return ans;
    }
}

두번째 풀이

import java.util.*;
class Solution {  
	public static int[] solution(String s) {
        s = s.substring(1, s.length());
        StringTokenizer st = new StringTokenizer(s, "{}");
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        while(st.hasMoreTokens()) {
            StringTokenizer st2 = new StringTokenizer(st.nextToken(), ",");
            while(st2.hasMoreTokens()) {
                int num = Integer.parseInt(st2.nextToken());
                map.put(num, map.getOrDefault(num, 0)+1);
            }
        }
        int size = map.size();
        int ans [] = new int[size];
        for (Integer key :  map.keySet()) {
			ans[size-map.get(key)] = key;
		}
        return ans;
    }
}

 

 

REVIEW

이거 푸는데 정말 오래걸려서 멘붕탔다..

프로그래머스 레벨2에서 dp빼고 오래걸린 문제가 없어서 무난하게 잘푸나 싶었는데ㅠㅠ

카카오 기출은 더 많이 풀어봐야겠다.