본문 바로가기
  • 주니어 개발자의
    RESTful 성장기
Algorithm/Programmers

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

by 돌건 2021. 4. 3.
 

코딩테스트 연습 - 튜플

"{{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] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1]

programmers.co.kr

 

  • 분석 및 해결

집합의 원소들을 가지고 순서를 알아맞혀야 하며, 이때 주의할 점은 집합은 원소의 순서가 바뀔 수 있다는 점이다. 따라서 나는 집합을 원소의 개수별로 Map에 저장하였고, 집합의 원소가 1개인 것부터 n개인 것까지 차례로 돌아가며 순서를 유추했다.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class PG_튜플 {
    // 원소의 개수별로 집합을 관리 key:원소 개수, value: 집합
    private static Map<Integer, List<Integer>> map = new HashMap<>();
	
    public int[] solution(String s) {
        int[] answer = {};
        
        parsing(s);
        answer = getAnswer(answer);
        
        return answer;
    }
	
    // 집합 나누기
    private static void parsing(String s) {
        int strLen = s.length();
		
        List<Integer> list = new ArrayList<>();
        String partStr = "";
		
        for(int index = 1; index < strLen - 1; index++) {
            char ch = s.charAt(index);
			
            if(ch == '{') {
                continue;
            }
            else if(Character.isDigit(ch)) {
                partStr += ch;
            }
            else if(ch == ',') {
                // 집합 내 원소를 구분하는 ','인 경우
                if(s.charAt(index - 1) != '}') {
                    partStr += ch;
                }
            }
            else if(ch == '}') {
                String[] split = partStr.split(",");
				
                for(String tmp: split) {
                    list.add(Integer.parseInt(tmp));
                }
				
                map.put(list.size(), list);
				
                list = new ArrayList<>();
                partStr = "";
            }
        }
    }
	
    private static int[] getAnswer(int[] answer) {
        int n = map.size(); // tuple num
		
        answer = new int[n];
		
        Iterator<Integer> iter = map.keySet().iterator();
		
        while(iter.hasNext()) {
            int key = iter.next();
            int num = map.get(key).get(0); // 집합에 존재하는 유일한 원소
			
            // 현재 num을 모든 집합에서 삭제함. 
            // {2}, {1, 2}가 있다면, 2를 삭제함으로써 다음 집합에서 튜플의 다음 원소 순서를 파악할 수 있다.
            for(int index = key; index <= n; index++) {
                map.get(index).remove((Integer)num);
            }
			
            answer[key - 1] = num;
        }
		
        return answer;
    }
}

댓글