백준 11292 자바 - 키 큰 사람 (BOJ 11292 JAVA)

문제 : boj11292

 

 

  각 TC마다 N개를 모두 입력받기 전에는 뭐를 출력해야할지 알 수 없다. 또한 입력이 들어온 순서를 유지해야 하므로 정렬해서 처리할 수도 없다. 그렇다면 전부 어딘가에 저장하면서 입력받는다. 이 때 입력받으면서 최대값을 확인한 후, 다시 순회하며 최대값에 부합하는 String을 출력해주면 된다. 이 경우 O(N+N)이 된다.

 

  내 경우엔 ArrayList를 두고 최대값이 갱신되면 리스트를 초기화하는 방식을 택했다. 즉, 현재 최대값과 동일한 값이 들어오면 ArrayList에 String을 추가하고, 최대값보다 낮으면 무시하고, 최대값보다 크면 리스트를 초기화하고 현재 최대값도 갱신하면서 새로 만들어진 리스트에 String을 추가한다. 이 경우 O(N)이 된다. 메모리도 덜쓴다. 사실 어느방식을 택하든 아주 여유롭게 통과되는 이-지한 문제라 큰 의미는 없다.

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) break;

            double max = 0;
            ArrayList<String> answer = new ArrayList<>();
            while (n-->0) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String a = st.nextToken();
                double b = Double.parseDouble(st.nextToken());
                if (b < max) continue;
                if (b > max) answer = new ArrayList<>();
                answer.add(a);
                max = b;
            }
            for (String s : answer) sb.append(s).append(' ');
            sb.append('\n');
        }
        System.out.print(sb);
    }

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