[자바] 백준 20956 - 아이스크림 도둑 지호 (java)

목차

문제 : boj20956

 

 

필요 알고리즘

• 두 포인터 (투 포인터, two pointer), 정렬
  
  • 투 포인터로 해결할 수 있는 문제이다. 다만 일반적인 투 포인터 사용 형태와는 약간 다르다.

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

 

 

풀이

  입력받은 N개의 아이스크림 정보에 대해 양을 a, 번호를 idx 라고 하자. 그럼 우선 입력받은 후 a desc, idx asc로 정렬한다. 

@Override
public int compareTo(final IceCream o) {
    if (this.a == o.a)
        return this.idx - o.idx;
    return o.a - this.a;
}

 

 

  그리고 각 a가 총 몇 번 나왔는지도 세둔다. (코드의 cnt)

그럼 만약 입력이 이하와 같다면

6 6
7 4 7 6 7 6

 

 

  정렬한 결과는 다음과 같다.

 

  이 문제에서 아이스크림은 양이 많은 것 부터 먹긴하는데 7의 배수가 될 때 마다 idx를 기준으로 작은걸 선택할지 큰걸 선택할지가 바뀌는 문제이다. 그럼 이제 아직 안먹은 것 중 양이 가장 많은건 정렬을 해서 알고 있고, 그 중 idx가 가장 작은 것과 가장 큰 것도 각 a가 총 몇 번 나왔는지 알고 있으므로 알 수 있다. 따라서 양이 동일한 것 끼리 투 포인터를 진행하면 된다!

 

  코드 기준으로 동일한 양에서 가장 idx가 낮은걸 가르키는게 pts, 높은걸 가르키는게 pte이다. s는 다음으로 많은 양을 미리 가르킨다. 현재 가장 큰 a는 7 이므로 처음엔 다음과 같이 된다. 그럼 이제 7의 배수를 만나기 전까진 pts를 증가하면서 idx를 출력하고, 7의 배수를 만나면 pte를 감소하면서.. 다시 7의 배수를 만나면 pts를 증가하면서.. 처럼 진행하면 된다.

 

boolean isReverse = false;	// !isReverse면 pts증가하면서 출력, isReverse면 pte감소하면서 출력
while (m!=0) {	// m개를 다 선택하기 전까지
    int pts = s;
    int pte = pts + cnt.get(arr[pts].a) - 1;
    s = pte+1;
    boolean isMultiplesOf7 = arr[pts].a%7 == 0;	// 민초맛인지 여부

    while (pts<=pte && m!=0) {	// 투 포인터 진행
        m--;
        sb.append(!isReverse ? arr[pts++].idx : arr[pte--].idx).append('\n');
        if (isMultiplesOf7) isReverse = !isReverse;
    }
}

 

 

 

 

코드 : github

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

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

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        IceCream[] arr = new IceCream[n];
        Map<Integer, Integer> cnt = new HashMap<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(st.nextToken());
            arr[i] = new IceCream(a, i+1);
            cnt.put(a, cnt.getOrDefault(a, 0) + 1);
        }
        Arrays.sort(arr);

        StringBuilder sb = new StringBuilder();
        int s = 0;
        boolean isReverse = false;
        while (m!=0) {
            int pts = s;
            int pte = pts + cnt.get(arr[pts].a) - 1;
            s = pte+1;
            boolean isMultiplesOf7 = arr[pts].a%7 == 0;

            while (pts<=pte && m!=0) {
                m--;
                sb.append(!isReverse ? arr[pts++].idx : arr[pte--].idx).append('\n');
                if (isMultiplesOf7) isReverse = !isReverse;
            }
        }

        System.out.print(sb);
    }
}

class IceCream implements Comparable<IceCream> {
    int a, idx;

    public IceCream(final int a, final int idx) {
        this.a = a;
        this.idx = idx;
    }

    @Override
    public int compareTo(final IceCream o) {
        if (this.a == o.a)
            return this.idx - o.idx;
        return o.a - this.a;
    }
}