[자바] 백준 27988 - 리본 (Hard) (java)

목차

• 문제 : boj27988
• 필요 알고리즘
• 풀이
• 코드 : github

문제 : boj27988

 

 

필요 알고리즘

• 그리디 알고리즘, 정렬
  
  • 문제를 좀 더 간단히 생각해보면 동일한 규칙을 적용시켜서 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  생각 과정은 다음과 같다.

 

1. 일단 입력으로 들어온 데이터부터 좀 더 이해하기 편하게 바꿔보자.

  X위치에 달린 길이 L의 구부릴 수 있는 리본이라 함은 결국 [X-L, X+L] 에서 다른 색상을 만나기만 하면 되는 리본이라 볼 수 있다. [X-L, X+L] 은 이후 [s, e] 라고 생각하겠다.

 

 

2. 우선 답이 없는 'NO'를 출력해야 하는 경우를 생각해보자.

  이 경우 당연하게도 [s, e]의 모든 리본이 만나는 경우는 동일한 색상인 경우밖에 없다.

이하의 예시를 생각해보자.

5
1 2 5 10 11
1 1 1 2 2
R R B Y Y

 

  차례대로 [s, e]는 [0, 2], [1, 3], [4, 6], [8, 12], [9, 13] 이 될 것이고 그려보면 이하와 같다.

이 경우 NO가 될 것이다.

 

 

3. 그렇다면 반대로 생각해서, 서로 겹쳐있는 리본들의 집합에서 색상이 다른게 하나라도 존재한다면 그게 답이다.

  이하는 2번째 리본의 L값만 3으로 바뀐 경우이다.

5
1 2 5 10 11
1 3 1 2 2
R R B Y Y

 

  이 경우  [0, 2], [-1, 5], [4, 6], [8, 12], [9, 13] 가 되고, 마찬가지로 그려보면 이하와 같다.

  이 경우 서로 겹쳐있는 리본들의 집합중에 서로 색상이 다른게 존재하게되고, 답이 존재하게 된다.

 

 

4. 그럼 어떻게 구현할까?

  우선 입력 그대로 [X-L, X+L]을 가지고 처리해도 가능하겠지만, 생각한바를 코드로 잘 옮기기 위해 우선 생각해둔 [s, e] 형태로 변경하는게 편할 것 같다.

class Ribbon implements Comparable<Ribbon> {
    int s, e, num;
    char color;

    public Ribbon(int num) {
        this.num = num;
    }

    public void setup(int len) {
        int tmp = s;
        s = tmp-len;
        e = tmp+len;
    }

	...
}

 

  그리고 s와 e값을 기준으로 정렬해준다. 그 이유는 서로 겹쳐있는 리본들의 집합을 쉽게 찾기 위해서이다.

class Ribbon implements Comparable<Ribbon> {
    int s, e, num;
    char color;

    public Ribbon(int num) {
        this.num = num;
    }

    public void setup(int len) {
        int tmp = s;
        s = tmp-len;
        e = tmp+len;
    }

    @Override
    public int compareTo(final Ribbon o) {
        if (this.s == o.s)
            return this.e-o.e;
        return this.s-o.s;
    }
}

 

  이제 그리디 규칙을 정해보면 다음과 같다.

A. s와 e를 기준으로 정렬해둔 데이터를 순차적으로 보면서 이하를 체크한다.

B. 현재까지 기록해두었던 가장 마지막 e값보다 현재 보고 있는 리본의 s값이 더 크다면 -> 겹쳐진 리본의 집합이 끝난거다. 새로운 집합이 시작된다! 새로운 집합이 시작될 때 색상을 기록해둔다.

C. 이후 다른 색상이 동일 집합에 나온다면 답이 나온거다.

D. 동일한 집합이긴한데, e값이 증가했다면 해당 리본으로 번호를 바꿔둬야 한다. 어차피 '답이 여러 개 존재한다면 아무거나 출력해도 상관없다.' 라는 조건이 있으므로, e값이 증가할 때 리본의 번호를 바꿔둔다면 항상 답이 될 수 있다.

char curColor = 0;
int lastNum = -1;
int lastE = Integer.MIN_VALUE;
for (Ribbon cur : arr) { // [A]
    if (cur.s > lastE) { // [B]
        curColor = cur.color;
        lastNum = cur.num;
        lastE = cur.e;
        continue;
    }

    if (cur.color != curColor) { // [C]
        System.out.printf("YES\n%d %d\n", lastNum, cur.num);
        return;
    }

    if (cur.e > lastE) { // [D]
        lastE = cur.e;
        lastNum = cur.num;
    }
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
       new Main().solution();
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        Ribbon[] arr = new Ribbon[n];
        for (int i = 0; i < n; i++) arr[i] = new Ribbon(i+1);

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i].s = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i].setup(Integer.parseInt(st.nextToken()));
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i].color = st.nextToken().charAt(0);

        Arrays.sort(arr);

        char curColor = 0;
        int lastNum = -1;
        int lastE = Integer.MIN_VALUE;
        for (Ribbon cur : arr) {
            if (cur.s > lastE) {
                curColor = cur.color;
                lastNum = cur.num;
                lastE = cur.e;
                continue;
            }

            if (cur.color != curColor) {
                System.out.printf("YES\n%d %d\n", lastNum, cur.num);
                return;
            }

            if (cur.e > lastE) {
                lastE = cur.e;
                lastNum = cur.num;
            }
        }

        System.out.println("NO");
    }
}

class Ribbon implements Comparable<Ribbon> {
    int s, e, num;
    char color;

    public Ribbon(int num) {
        this.num = num;
    }

    public void setup(int len) {
        int tmp = s;
        s = tmp-len;
        e = tmp+len;
    }

    @Override
    public int compareTo(final Ribbon o) {
        if (this.s == o.s)
            return this.e-o.e;
        return this.s-o.s;
    }
}