[백준] 2141번 우체국

[CMSSKKK]

TITLE

우체국

LINK

• 문제 출처 사이트 : 백준
• Link

📷 Screenshots

댓글 양식

• 아래 양식을 복사한 뒤 [shift]+[tab] 2회를 하고 작성하여 주세요

    ### 풀이 언어

    - python/java

    ### 코드

    ```python/java

    ```

    ### 핵심 로직 혹은 자료구조

    - 

    ### 시간 복잡도

    - O(  )

[CMSSKKK]

풀이 언어

• java

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Town[] towns = new Town[n];
        long count = 0;
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            towns[i] = new Town(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            count += towns[i].a;
        }

        Arrays.sort(towns);
        long mid = (count + 1) >> 1;
        long sum = 0;
        for (int i = 0; i < n ; i++) {

            sum += towns[i].a;
            if(sum >= mid) {
                System.out.println(towns[i].x);
                break;
            }
        }

    }

    private static class Town implements Comparable<Town>{
        long x;
        long a;

        public Town(long x, long a) {
            this.x = x;
            this.a = a;
        }

        @Override
        public int compareTo(Town o) {
            return (int) (this.x - o.x);
        }
    }
}

핵심 로직 혹은 자료구조

• 댜른 사람의 아이디어를 보고 해결했습니다.

시간 복잡도

• O( )