[백준] 2002번 추월 자바 풀이

문제

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 1081 460 346 41.587%
문제
영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고객들이 어느 위치에 존재하는지 파악을 하였고, 모든 고객들의 거리의 합을 최소로 하려한다. 두 위치의 거리는 |x1-x2|+|y1-y2|로 정의한다.

n명의 주요 고객들의 위치 (xi,yi)이 주어질 때, 모든 고객들의 거리 합을 최소로 하는 위치에 편의점을 세울 때, 그 최소 거리 합을 출력하시오.

입력
첫째 줄에는 주요 고객들의 수n이 주어진다.(1≤n≤100,000)

다음 n줄에는 고객들의 위치 (x,y)가 주어진다.(-1,000,000≤x,y≤1,000,000)

출력
모든 고객들의 거리 합을 최소로 하는 위치에 편의점을 세울 때, 그 최소 거리 합을 출력하시오.

풀이

1. 첫번째로 들어간 차는 추월이 불가능하다.
2. 확인대상 차량의 index보다 앞에 있던 차량 중 하나라도 추월 했다면 추월 차량이다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int answer = 0;
        int N = Integer.parseInt(br.readLine());
        String[] s = new String[N];
        ArrayList<String> comp = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            s[i] = br.readLine();
        }
        for (int i = 0; i < N; i++) {
            comp.add(br.readLine());
        }

        for (int i = 1; i < N; i++) { // 0번 차량은 확인 불필요
            for (int j = 0; j < i; j++) { // i번 차량보다 먼저 들어간 차량만 확인 대상
                int compIndex = comp.indexOf(s[j]);
                int index = comp.indexOf(s[i]);
                if (compIndex > index) {
                    answer++;
                    break;
                }
            }
        }
        System.out.println(answer);
    }
}