프로그래머스_튜플(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 이하인 경우만 입력으로 주어집니다.

---

[입출력 예]

s	result
"{{2},{2,1},{2,1,3},{2,1,3,4}}"	[2, 1, 3, 4]
"{{1,2,3},{2,1},{1,2,4,3},{2}}"	[2, 1, 3, 4]
"{{20,111},{111}}"	[111, 20]
"{{123}}"	[123]
"{{4,2,3},{3},{2,3,4,1},{2,3}}"	[3, 2, 4, 1]

입출력 예에 대한 설명입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

문제 예시와 같습니다.

입출력 예 #3

(111, 20)을 집합 기호를 이용해 표현하면 {{111}, {111,20}}이 되며, 이는 {{20,111},{111}}과 같습니다.

입출력 예 #4

(123)을 집합 기호를 이용해 표현하면 {{123}} 입니다.

입출력 예 #5

(3, 2, 4, 1)을 집합 기호를 이용해 표현하면 {{3},{3,2},{3,2,4},{3,2,4,1}}이 되며, 이는 {{4,2,3},{3},{2,3,4,1},{2,3}}과 같습니다.

 

[문제 풀이]

s	result
"{{1,2,3},{2,1},{1,2,4,3},{2}}"	[2, 1, 3, 4]

위의 String s를 예시로 문제 해결 과정을 풀이하겠다.

 

1. 주어진 s에서 양끝 괄호를 제거한다.

    -> s = {1,2,3},{2,1},{1,2,4,3},{2}가 될 것이다.

 

2. string 배열을 선언하고 "},"을 기준으로 s를 자른다

    -> str[0] = "{1,2,3", str[1] = "{2,1", str[2] = "{1,2,4,3", str[3] = "{2" 가 될 것이다.

 

3. str 배열에서 맨 앞 문자인 "{"을 제거한다. 

    -> str[0] = "1,2,3", str[1] = "2,1", str[2] = "1,2,4,3", str[3] = "2" 가 될 것이다.

 

4. 2차원 정수 배열 ss를 선언하고 여기에 값을 넣어준다.

    4-1. 숫자가 한자리 이상일 수 있으므로, 해당 위치의 문자가 ","가 아니면 temp 문자열에 해당 문자를 이어붙인다.

    4-2. ","가 등장한다면 해당 수가 모두 이어붙여진 것이므로 temp를 integer 형식으로 변환하여 ss[i][k]에 넣어주고 k를 증가시켜준다.

    4-3. for문이 한번 완료되면 마지막 원소는 ","가 존재하지 않아 ss에 들어가지 않았을 것이므로 ss[i][k]에 for문이 끝났을 때의 문자열 temp를 저장한다.

    4-4. k는 ss[i]의 숫자 원소 개수-1을 의미한다. 따라서 integer 배열 index[k]=i를 해주면 나중에 원소 개수가 가장 적은 ss의 인덱스를 탐색할 수 있다.

    -> ss[0][0] = 1, ss[0][1] = 2, ss[0][2] = 3 , ss[0][3] = null    index[2]=0

    -> ss[1][0] = 2, ss[1][1] = 1, ss[1][2] = null, ss[1][3] = null    index[1]=1

    -> ss[2][0] = 1, ss[2][1] = 2, ss[2][2] = 4, ss[2][3] = 3    index[3]=2

    -> ss[3][0] = 2, ss[3][1] = null, ss[3][2] = null, ss[3][3] = null    index[0] = 3 

 

5. index배열에 저장된 값 순으로 ss를 방문한다. 따라서 가장 처음엔 숫자 원소의 개수가 1개만 저장되어있는 ss[index[0]][j]값 즉, ss[3][j]를 탐색하고 해당 값이 최종 답안 배열 answer에 포함되어 있지 않다면 그 값을 add한다. i는 원소의 개수 -1을 의미하고, null값 전인 index까지만 탐색해야 하므로 j는 0부터 i까지만 탐색한다.

원소 개수가 적은 인덱스부터 탐색하게 되면, 원소 개수는 1씩만 차이나므로, ss는 이미 answer에 들어가있는 값들과 아직 들어가지 않은 하나의 원소로만 구성되어있다. 따라서 answer가 해당 값을 포함하고 있지 않다면 해당 집합에서 아직 들어가지 않은 단 하나의 원소인 것이므로 answer에 넣어주면 된다.

    -> 최종적으로, [2, 1, 3, 4] 의 값을 얻을 수 있게 된다.

[코드]

import java.util.*;
class Solution {
    public ArrayList<Integer> solution(String s) {
        
        s = s.substring(1,s.length()-2);    //양끝 괄호 제거
       
        String[] str = s.split("},");   //{숫자, {숫자, 숫자 ... 식으로 저장
        
        ArrayList<Integer> answer = new ArrayList<>();  //최종 답안 저장 arraylist
        Integer[][] ss = new Integer[str.length][str.length];   //숫자만 저장할 Integer 2차원 배열
        
        for(int i=0;i<str.length;i++){  //집합 시작 시 "{" 제거, 최종적으로 str[i]에는 숫자와 ","로만 구성된 string
            str[i]=str[i].substring(1);
        }
    
        String temp ="";
        int[] index = new int[str.length];  //집합 원소 개수가 가장 적은 순으로 ss의 index가 저장됨
        
        for(int i=0;i<str.length;i++){  
            //str 원소에서 ","를 제거하고 숫자만 Integer 배열 ss에 저장, Integer배열 index에 집합을 이루는 원소 수가 가장 적은 순으로 ss의 인덱스 저장
            int k=0;
            temp="";
            
            for(int j=0;j<str[i].length();j++){
               
                if(str[i].charAt(j)!=','){   
                    //숫자가 한자리 이상일 수도 있으므로 해당 위치의 char가 ","가 아니면 ss에 바로 저장하지 않고 temp에 이어붙임
                    temp += str[i].charAt(j);
                }
                    
                
                else{
                    ss[i][k++] = Integer.parseInt(temp);
                    temp="";
                    
                }
            }
            
            ss[i][k] = Integer.parseInt(temp);
            index[k]=i;   //k는 ss[i]에 들어있는 원소의 개수, 즉 집합을 이루는 원소의 개수이고 index[k]에 i를 저장해줌
          
           
        }
      
        
        int k=0;
        //index 배열 값 순으로 ss 탐색, 원소 개수가 적은 인덱스부터 탐색하게 됨
        for(int i=0;i<index.length;i++){
            for(int j=0;j<=i;j++){
                if(!answer.contains(ss[index[i]][j])){
                    answer.add(ss[index[i]][j]);
                    break;
                }
                
            }
        }
        
        return answer;
    }
}