코딩테스트 #6

#6

간격(interval)로 이루어진 배열이 주어지면, 겹치는 간격 원소들을 합친 새로운 배열을 만드시오. 간격은 시작과 끝으로 이루어져 있으며 시작은 끝보다 작거나 같습니다.

 

예제)

Input: {{2,4}, {1,5}, {7,9}}

Output: {{1,5}, {7,9}}

Input: {{3,6}, {1,3}, {2,4}}

Output: {{1,6}}

리스트안에 리스트가 존재하여 어떻게 풀지 고민을 많이했었는데, 시작과 끝으로 구성된 클래스를 하나 구현해서 사용하니 쉽게 풀렸다.

풀이법은 이렇다.

1. 우선 {시작, 끝} 을 표현할 수 있는 Interval 클래스를 생성한다.

2. List에 들어있는 Interval들을 {시작, 끝} 시작크기순으로 정렬한다. {{2,4}, {1,5}, {7,9}} => {{1,5}, {2,4}, {7,9}}

3. for문을 돌면서 Interval의 끝이 다음 Interval의 처음보다 크면 두 Interval을 합친다.

package everyProgramming;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
 
public class Ch06 {
    /*
    Input: {{2,4}, {1,5}, {7,9}}
    Output: {{1,5}, {7,9}}

    Input: {{3,6}, {1,3}, {2,4}}
    Output: {{1,6}}
    */
    
    public static void main(String[] args) {
        List<Interval> input = new ArrayList<Interval>();
        input.add(new Interval(3,6));
        input.add(new Interval(1,3));
        input.add(new Interval(2,4));
        
        LinkedList<Interval> output = new LinkedList<Interval>();
        
        Collections.sort(input);
        
        output.addFirst(input.get(0));
        for(int i=1; i<input.size(); i++) {
            Interval interval = input.get(i);
            
            if(output.getLast().getEnd() < interval.getStart()) {
                output.addLast(interval);
            }else {
                if(output.getLast().getEnd() < interval.getEnd()){
                    output.getLast().setEnd(interval.getEnd());
                }
            }
        }
        
        for(Interval result : output) {
            System.out.print(result);
        }
    }
    
}
 
class Interval implements Comparable<Interval>{
    
    private int start;
    private int end;
    
    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
    
    public int getStart() {
        return start;
    }
    public void setStart(int start) {
        this.start = start;
    }
    public int getEnd() {
        return end;
    }
    public void setEnd(int end) {
        this.end = end;
    }
    
    public String toString() {
        return "[" + this.getStart() + " , " + this.getEnd() + "] ";
    }
 
    @Override
    public int compareTo(Interval comparision) {
        return this.getStart() - comparision.getStart();
    }
}
 

우선 Interval 클래스를 만들어서, Comparable을 구현한다. (start로 정렬이 필요하기 때문에)

그리고 나서 for문을 돌면서 list를 합치면 된다..^^..