[JAVA] 프로그래머스 - 튜플

문제내용

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

코딩테스트 연습 - 튜플

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

• (a1, a2, a3, ..., an)

튜플은 다음과 같은 성질을 가지고 있습니다.

1. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)
2. 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)
3. 튜플의 원소 개수는 유한합니다.

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

• {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

와 같이 표현할 수 있습니다. 이때, 집합은 원소의 순서가 바뀌어도 상관없으므로

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
• {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
• {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• s의 길이는 5 이상 1,000,000 이하입니다.
• s는 숫자와 '{', '}', ',' 로만 이루어져 있습니다.
• 숫자가 0으로 시작하는 경우는 없습니다.
• s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.
• s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.
• return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다.

---

문제 접근 방법

일단 본인은 처음에 문제를 봤을때 문제 이해를 잠깐 못했었다. 때문에 내가 이해못했던 부분을 잠깐 설명하고 넘어가려한다.

우선 내가 이해못한 부분은 아래와 같이 부분집합의 원소가 있을때 해당 튜플인지 어떻게 아는지 였다.

"{{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}" -> (2, 1, 3, 4)

위의 부분집합 원소를 보고 튜플을 유추하는 방법은 간단하다. 제일 작은 원소부터 시작해서 가장 큰 원소까지 검사하여 빈 튜플에 하나씩 추가하면 본래 튜플을 유추해 낼 수 있다. 즉, 예를들면 {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}} 는

첫번째로 봐야하는 부분집합 원소 {2} -> (2)

두번째로 봐야하는 부분집합 원소 {2, 1} -> (2, 1)

세번째로 봐야하는 부분집합 원소 {1, 2, 3} -> (2, 1, 3)

네번째로 봐야하는 부분집합 원소 {1, 2, 3, 4} -> (2, 1, 3, 4)

4번의 과정을 통해 튜플 유추할 수 있다.

 

이제 문제풀이 방법에대해 말해보자.

1. 문자열 분리
   일단 부분집합을 배열로 입력받는게 아니라 문자열로 입력 받기 때문에 해당 문자열을 { } 를 기준으로 나눌 필요성이 있다고 봤고 분리는 아래와 같이 했다.
   
   만약 입력받은 s가 "{{20,111},{111}}" 일 경우 1차적으로 "20,111" "111" 로 분리해야 한다고 생각했고,
   그렇게 생각한 이유는 문자열 s를 2차원배열로 바꿔서 가장 작은 크기의 요소부터 차례대로 빈튜플(answer)에 넣어줘야겠다고 생각했기 때문이다.
   그래서 문자열 분리를 가장 먼저 했다.
2. 2차원 List 생성
   처음에 2차원 배열로 하려고 했으나 원소의 길이가 다르기 때문에 2차원 List를 사용하는것으로 바꿨다.
   2차원 List의 경우 List안에 List가 있는경우로 2차원 List로 만드는 이유를 "{{20,111},{111}}"로 예를들면,
   
   list.get(0).get(0) -> 20
   list.get(0).get(1) -> 111
   list.get(1).get(0) -> 111
   
   list.get(0) -> [20, 111]
   list.get(1) -> [111]
   
   로 만들기 위함이다. 2차원 List는 큰박스안에 작은박스가 있다고 생각하면 편하다.
3. 방문배열 초기화
   먼저 방문배열(check)를 만드는 이유는 튜플에 이미 삽입했던 원소는 다시 삽입하지 않기 위함이다.
   예를들면 "{{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}"일 때 가장 작은 부분집합 원소부터 튜플에 넣어주기 때문에
   "2"는 4번 / "1"은 3번 / "3"은 2번 겹치게 된다.
   따라서 {1,2,3,4}가 들어있는 check배열을 생성해 나중에 answer을 만드는 메서드에서 이미 삽입했던 원소를 다시 삽입하지 않도록 만든다.
   
   
4. 튜플 찾기
   위의 모든 과정을 거치면 마지막으로 본래 튜플만 찾아주면 된다.
   튜플을 찾는 방법은 위에서 말했다시피 list의 가장작은 원소부터 가장큰 원소까지 차례대로 answer에 삽입하면된다. 다만 이때 check배열을 이용해 이미 삽입했던 원소는 삽입하면 안된다것만 주의하면 된다.

 

솔직히 말해서 내가 푼 풀이는 좋은 풀이라고 말하진 못하겠다.

왜냐면 나름 풀었다는것에 기분이 좋긴하지만 다른 사람들의 풀이를 봤을때 비교가 되기 때문이랄까..

그래서 내가푼 풀이와 다른사람 풀이를 같이 올릴 생각이다.

 

풀이를 보자

---

풀이

내풀이

import java.util.ArrayList;

public class Solution {
	static ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();
	static String[] check;
	static int[] answer;
	
	public static int[] solution(String s) {
		int open = 0;
		StringBuilder sb = new StringBuilder();
		
		//입력 문자열을 {} 기준으로 나누기
		for(int i=1; i<s.length()-1; i++) {
			char temp = s.charAt(i);
			if(temp=='}') {
				open--;
				if(open==0) {sb.append(" ");}
			}
			else if(temp=='{') {open++;}
			else if(open>0){sb.append(temp);}	
		}
		listBox(sb);//2차원 배열처럼 리스트를 2차원으로 만들어줌.
		checkArr();//check배열 초기화.
		checkTuple();//어떤 튜플인지 찾기.
		
		return answer;
	}
	
	//2차원 list 생성
	public static void listBox(StringBuilder sb) {
		String[] arr = sb.toString().split(" ");//공백기준으로 나눈 문자열을 배열에 넣기
		sb.delete(0, sb.length());//sb 초기화
		//arr[i]는 list의 i번째 요소로 생각.
		for(int i=0; i<arr.length; i++) {
			//list안에 ArrayList 생성
			list.add(new ArrayList<String>());
			
			//i번째 요소의 문자를 처음부터 끝까지 탐색
			//,가 나오면 숫자하나 만들어진거 넣고
			//안나오면 숫자계속 만들기.
			for(int j=0; j<arr[i].length(); j++) {
				char temp = arr[i].charAt(j);
				if(temp!=',') {sb.append(temp);}
				else {
					list.get(i).add(sb.toString());
					sb.delete(0, sb.length());
				}
			}
			//i번째의 마지막 숫자 추가
			list.get(i).add(sb.toString());
			sb.delete(0, sb.length());
		}
		//answer의 크기 = 튜플의 집합원소 개수
		answer = new int[list.size()];
	}
	
	//check배열 초기화
	//check배열 = 튜플 집합 원소 중 가장큰 집합원소. 
	public static void checkArr() {
		check = new String[list.size()];
		for(int i=0; i<list.size(); i++) {
			if(check.length == list.get(i).size()) {
				for(int j=0; j<check.length; j++) {
					check[j] = list.get(i).get(j);
				}
			}
		}
	}
	
	//튜플 찾기.
	public static void checkTuple() {
		int cnt = 1;//종료조건 변수, 튜플찾기 위한 집합원소 개수.
		int idx = 0;//list 인덱스
		int ansIdx=0;//answer 인덱스
		while(true) {
			//cnt가 1부터 시작하기 때문에 'list의 크기+1'이됐을때 종료해줘야함.
			//즉, list를 전부 돌았을때 종료한다는 말.
			if(cnt==list.size()+1) {break;}
			
			//가장 작은크기의 list 요소 순서대로 answer에 추가.
			if(list.get(idx).size()==cnt) {
				for(int i=0; i<list.get(idx).size(); i++) {
					String value = list.get(idx).get(i);
					for(int j=0; j<check.length; j++) {
						if(check[j].equals("-1")) {continue;}//방문한건 패스
						if(check[j].equals(value)) {
							check[j] = "-1";//방문표시
							answer[ansIdx] = Integer.parseInt(value);//요소 삽입
							ansIdx++;//answer 인덱스 증가
						}
					}
				}
				cnt++;//cnt 증가
				idx = 0;//idx 초기화
			}else {//idx번째 요소가 cnt만큼의 크기가 아닐때.
				idx++;
			}
		}
	}
}

---

다른사람풀이

import java.util.*;
class Solution {
    public int[] solution(String s) {
        Set<String> set = new HashSet<>();
        String[] arr = s.replaceAll("[{]", " ").replaceAll("[}]", " ").trim().split(" , ");
        Arrays.sort(arr, (a, b)->{return a.length() - b.length();});
        int[] answer = new int[arr.length];
        int idx = 0;
        for(String s1 : arr) {
            for(String s2 : s1.split(",")) {
                if(set.add(s2)) answer[idx++] = Integer.parseInt(s2);
            }
        }
        return answer;
    }
}

---

마치며

풀이를 보면 알겠지만 코드의 깔끔함이 차이가 나는것을 볼 수 있다.

배열을 만드는 것부터 아주 심플하고 깔끔하게 만들었는데 저런 생각은 어떻게 하는건지 모르겠다ㅋㅋㅋㅋ

역시 세상엔 고수가 정말 많은듯하다. 여튼 다른사람 풀이도 참고하면서 모두 화이팅하자 ㅎㅎ