스카이라인 쉬운거 [백준#1864]

골드4

스카이라인 쉬운거 JAVA 코드

문제 이해

건물 높이의 윤곽을 보고 건물의 최소 수를 알아내는 문제다.

건물 높이는 윤곽만 보이기 때문에 중복 높이는 같은 건물이라고 볼 수도 있다. 단, 중복 높이 사이에 그 높이보다 낮은 높이의 윤곽이 존재한다면, 두 개의 건물로 나뉜다고 볼 수 있다.

(예시1) 높이가 {5, 7, 5}로 주어지면, 건물의 최소 수는 2다. 5와 5는 같은 건물이라 생각할 수 있고, 높이가 다른 7도 하나의 건물이다.

(예시2) 높이가 {4, 0, 4}로 주어지면, 건물의 최소 수는 2다. 높이 4가 두 개 있지만, 중간에 0이 있기 때문에 중복을 제거하지 않는다.

그래서 건물 높이의 순서가 중요하다. 현재 높이보다 다음 높이가 더 낮으면, 이 다음 높이보다 높은 건물들은 앞으로 순회할 모든 건물들과 분리된 별도의 건물이다.

해결 방안

스택 자료구조를 활용해서 풀이를 고안했다.

1. 현재 스택이 비어있을 경우

스택이 비어있으면 비교할 높이가 없기 때문에 단순히 더해주면 된다.

2. 현재 스택의 가장 오른쪽 값보다 다음 높이가 더 높을 경우

다음 높이가 더 높으면 (예시1)의 경우를 고려하기 위해 일단 스택에 더해준다.

3. 현재 스택의 가장 오른쪽 값보다 다음 높이가 더 낮을 경우

이 경우는 (예시2)와 같으므로, 다음 높이와 같거나 낮은 높이까지 pop해줘야 한다.

4. 현재 스택의 가장 오른쪽 값과 다음 높이가 같을 경우

이 때는 중복 높이기 때문에 굳이 더해줄 필요 없다.

ArrayDeque<Integer> stack = new ArrayDeque<>();

int ans = 0;
for (int i = 0; i < N; i++) {
    st = new StringTokenizer(br.readLine());
    int x = Integer.parseInt(st.nextToken());
    int y = Integer.parseInt(st.nextToken());

    while (!stack.isEmpty() && stack.peekLast() > y) {
        ans++;
        stack.pollLast();
    }
    if (stack.isEmpty() || stack.peekLast() < y) {
        stack.add(y);
    }
}

마지막으로, 순회가 끝난 이후 스택에 남아있는 높이는 0이 아닌 이상 모두 개별 빌딩이다.

while (!stack.isEmpty()) {
    if (stack.pollLast() > 0) ans++;
}

System.out.println(ans);

---

좋다 [백준#1253]

골드4

좋다 JAVA 코드

문제 이해

• N개의 수가 주어진다
  • 1 <= N <= 2000
  • 수 절댓값 범위: 1,000,000,000
• N개 의 수 중 어떤 수가 다른 수 2 개의 합으로 나타낼 수 있으면 좋다.
  • 다른 2 개의 수로 표현해야 한다 => 본인 포함 금지
  • 수의 위치가 다르면 값이 같아도 다른 수다
  • 좋은 수의 개수 출력

해결 방안

조건을 만족하는 타겟 숫자를 효율적으로 찾아야 한다는 생각에 이분탐색 또는 투포인터를 생각했다.

private static boolean binarySearch(int[] nums, int target, int idx) {
    int left = 0, right = nums.length - 1;

    while (left < right) {
        if (left == idx) {
            left++; // 자기 자신은 사용할 수 없다.
            continue;
        } else if (right == idx) {
            right--; // 자기 자신은 사용할 수 없다.
            continue;
        }

        int sum = nums[left] + nums[right];
        if (sum == target) {
            return true;
        } else if (sum > target) {
            right--;
        } else {
            left++;
        }
    }
    return false;
}

---

세 용액 [백준#2473]

골드3

세 용액 JAVA 코드

문제 이해

• 전체 용액 N개
  • 3 <= N <= 5000
  • -1,000,000,000 <= 용액 값 <= 1,000,000,000
• 0에 가장 가까운 특성값을 만드는 서로 다른 3개 용액을 오름차순 정렬하여 출력

해결 방안

용액 한 개를 선택한 다음, 나머지 두개를 투포인터로 골라가며 0에 가장 가까운 특성값을 찾는다.

1. 용액 배열을 정렬한 다음, 기준 용액을 골라 투포인터 함수를 호출한다.

Arrays.sort(nums);

long minDiff = Long.MAX_VALUE;
long[] ans = new long[3];
for (int i = 0; i < N; i++) {
    long[] tmp = solve(nums, nums[i], i);
    if (Math.abs(tmp[0] + tmp[1] + tmp[2]) < minDiff) {
        minDiff = Math.abs(tmp[0] + tmp[1] + tmp[2]);
        ans = tmp;
    }
}
Arrays.sort(ans);
System.out.println(ans[0]+" "+ans[1]+" "+ans[2]);

0에 더 가까운 특성값을 찾으면 정답 배열을 업데이트한다.

2. 투포인터 알고리즘을 구현한다.

투포인터 함수에 기준 용액과 그 인덱스를 인자로 받아 중복 선택하지 않도록 유의한다.

private static long[] solve(long[] nums, long chosen, int idx) {
    int left = 0, right = nums.length - 1;
    long[] ans = new long[3];
    ans[0] = chosen;

    long tmpDiff = Long.MAX_VALUE;

    while (left < right) {
        if (left == idx) {
            left++;
            continue;
        } else if (right == idx) {
            right--;
            continue;
        }

        long s = Math.abs(chosen + nums[left] + nums[right]);
        if (s < tmpDiff) {
            ans[1] = nums[left];
            ans[2] = nums[right];
            tmpDiff = s;
            if (tmpDiff == 0) {
                return ans;
            }
        } else if (chosen + nums[left] + nums[right] > 0) {
            right--;
        } else {
            left++;
        }
    }
    return ans;
}

---

디지털 티비 [백준#2816]

브론즈1

디지털 티비 JAVA 코드

문제 이해

• N개의 중복 없는 채널명을 입력 받는다
  • 2 <= N <= 100
• 목표는 KBS1를 첫번째로, KBS2를 두번째로 이동시키는 것이다
  • 이미 KBS1가 첫번째, KBS2가 두번째인 입력은 주어지지 않는다
• 4개 이동이 가능하다
  • 1 - 화살표를 한 칸 아래로 내린다 (i에서 i+1로)
  • 2 - 화살표를 한 칸 올린다 (i에서 i-1로)
  • 3 - 현재 선택한 채널을 아래로 내린다 (화살표는 i+1을 가르킨다)
  • 4 - 현재 선택한 채널을 위로 올린다 (화살표는 i-1을 가르킨다)
• 이동 횟수는 500으로 제한한다

해결 방안

최대 채널 수가 100개로 제한되어 있고, 우리의 목표는 두 채널의 위치기 때문에 단순하게 1과 4만 이용해서 풀이해도 최대 이동 횟수인 500을 넘지 않는다

1. KBS1과 KBS2의 인덱스를 저장한다.

int kbs1_idx = -1, kbs2_idx = -1;
for (int i = 0; i <N; i++) {
    String channel = br.readLine();
    if (channel.equals(FIRST)) kbs1_idx = i;
    if (channel.equals(SEC)) kbs2_idx = i;
}

2. KBS2의 인덱스를 조정한다

KBS2가 KBS1 이전에 존재하면 KBS1을 위한 이동작업 때문에 한 칸 아래로 밀릴 것이다. (KBS1을 위로 올리려면 그 위의 채널들이 한 칸씩으로 아래로 이동한다)
그래서 이 경우에는 KBS2 인덱스에 1을 추가한다

if (kbs1_idx > kbs2_idx) kbs2_idx++;

3. KBS1 인덱스까지 1로 화살표를 이동한 다음, 4로 첫번째 위치까지 이동시킨다

화살표는 0에서 시작해서 kbs1_idx까지 이동하기 위해 kbs1_idx번 1을 사용한다.

그 다음 kbs1_idx에 있는 채널을 0까지 올리기 위해 kbs1_idx번 4를 사용한다.

output.append(CURSOR_DOWN.repeat(kbs1_idx));
output.append(SWAP_UP.repeat(kbs1_idx));

4. KBS2 인덱스까지 1로 커서 이동한 다음, 4로 두번째 위치까지 이동시킨다

이미 KBS2가 첫번째 위치에 위치한다면 필요없는 작업이다.

KBS1를 0번째 위치에 이동시킨 상태이니 또 0에서 시작해서 kbs2_idx까지 이동한다. kbs2_idx번 1을 사용한다.

그 다음 kbs2_idx에 있는 채널을 1까지 올리기 위해 kbs2_idx-1번 4를 사용한다.

if (kbs2_idx != 1) {
    output.append(CURSOR_DOWN.repeat(kbs2_idx));
    output.append(SWAP_UP.repeat(kbs2_idx-1));
}

---