이렇게 풀어도 되는지 궁금합니다.

자바 코딩테스트 - it 대기업 유제

4. "피부과" 문제 해법

작성

177

import java.util.*;

class Node implements Comparable<Node>{
  int time;
  char state;
  public Node(int time, char state){
    this.time = time;
    this.state = state;
  }

  @Override
  public int compareTo(Node o){
    if(this.time == o.time)return this.state - o.state;
    return this.time - o.time;
  }
}

class Solution {
	public int solution(int[] laser, String[] enter){
		int answer = 0;
    ArrayList<Node> arr = new ArrayList<>();
    for(String s:enter){
      String t = s.split(" ")[0];
      String l = s.split(" ")[1];

      int start = Integer.parseInt(t.split(":")[0])*60 + Integer.parseInt(t.split(":")[1]);
      int end = start + laser[Integer.parseInt(l)];

      arr.add(new Node(start, 's'));
      arr.add(new Node(end, 'e'));
    }

    Collections.sort(arr);
    
    int cnt = 0;
    for(Node x:arr){
      if(x.state == 's')cnt++;
      else{
        cnt--;
        answer = Math.max(answer, cnt);        
      }
    }

		return answer;
	}

	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[]{30, 20, 25, 15}, new String[]{"10:23 0", "10:40 3", "10:42 2", "10:52 3", "11:10 2"}));
		System.out.println(T.solution(new int[]{30, 20, 25, 15}, new String[]{"10:23 0", "10:40 3", "10:42 2", "10:52 3", "15:10 0", "15:20 3", "15:22 1", "15:23 0", "15:25 0"}));
		System.out.println(T.solution(new int[]{30, 20, 25, 15}, new String[]{"10:20 1", "10:40 1", "11:00 1", "11:20 1", "11:40 1"}));
    System.out.println(T.solution(new int[]{30, 20, 25, 15}, new String[]{"10:20 1", "10:20 1", "10:20 1", "10:20 1", "10:20 1"}));
	}
}

입문강의 결혼식과 비슷한 문제로 생각해 이렇게 짰는데 답은 맞게 나왔습니다. 혹시 반례가 있을까요? 아니면 이 방법도 맞는 방법일까요?

java 코딩-테스트

답변 2

김태원

지식공유자

안녕하세요^^

반례입니다. 답은 3입니다.

System.out.println(T.solution(new int[]{50, 10, 25, 15}, new String[]{"10:00 0", "10:10 1", "10:21 1", "10:31 1"}));

min

질문자

답변 감사합니다!

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

min님께서 짜신 코드는 레이저 문제의 해결을 위해 시작 시각과 끝나는 시각을 이용한 시간표 점검 방식으로 접근하셨습니다. 코드를 보면 각 강의의 시작 시각(’s’)과 끝나는 시각(‘e’)을 기준으로 Node 객체를 생성하고, 이를 ArrayList에 담아 정렬한 후 카운트를 증가시키거나 감소시키며 동시간대 최대 사용량을 계산하는 로직으로 구성되어 있습니다.

이 방식은 각 이벤트(레이저 사용 시작과 종료)을 시간 순으로 정렬하여 순차적으로 접근함으로써 동시간대 레이저 사용의 최대 갯수를 파악하는 sweep line 알고리즘(혹은 line sweep)에 기반합니다. 시간복잡도는 sort 함수에 의해 O(n log n)이 됩니다.

제시된 코드에서는 ‘e’ 이벤트(종료 이벤트)가 ’s’ 이벤트(시작 이벤트)보다 먼저 오는 경우 ’s’ 이벤트를 먼저 처리하도록 하고 있습니다. 이렇게 처리하는 이유는 같은 시간에 끝나는 이벤트와 시작하는 이벤트가 있을 경우, 끝나는 이벤트를 먼저 처리하여 동시간대의 최대 사용량을 정확히 계산하기 위함입니다.

결과값이 올바르게 나온다면, 코드 로직이 주어진 문제 조건과 반례 없이 잘 대응하고 있는 것으로 보입니다. 하지만 다양한 상황의 테스트 케이스를 고려하여 문제 요구사항에 부합하는지 추가적으로 검증해 보는 것이 좋습니다. 문제의 정확한 설명과 조건, 예외 상황을 고려하여 테스트를 진행해 보세요. 코드가 정확하게 동작하는 것을 확인하려면 다양한 입력에 대한 출력 값을 확인하거나, 문제에 대한 추가적인 반례를 찾아보는 것이 중요합니다.

제시한 방법도 반례가 없다면 맞는 해결 방법입니다. 다만 문제에 따라 접근 방법이나 요구사항이 달라질 수 있으므로, 문제의 조건을 정확히 이해하고 알고리즘을 적용하는 연습을 계속하시면 좋겠습니다.

인프런 커뮤니티 질문&답변

이렇게 풀어도 되는지 궁금합니다.