[코드트리] 지그재그로 이동하기 - 자바(Java)

문제

https://www.codetree.ai/training-field/search/problems/moving-with-zigzag?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

일직선 상에서 A 지점과 B 지점을 입력받아 A에서 B까지 도착하려고 할 때, A + 1, A - 2, A + 4, A - 8, A + 16,... 와 같이 지그재그로 방향을 바꾸면서 움직인다.

 

A지점에서 시작하여 B지점에 처음 도착할 때 이동한 총 거리를 구한다.

 

 

코드

첫 번째 줄에 A 지점과 B 지점을 공백(" ")으로 구분하여 입력받는다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        boolean direction = true;   // 이동 방향 true 오른쪽, false 왼쪽
        int distance = 1;           // 이동할 거리
        int next = 0;               // 다음 지점
        int current = a;            // 현재 지점
        int result = 0;             // 총 이동 거리

        while (true) {
            // 다음 지점 구하기
            next = direction ? a + distance : a - distance;

            // 오른쪽으로 이동할 때, 현재 지점은 b보다 작고, 다음 지점은 b보다 크거나 같으면
            if (direction && current < b && next >= b) {
                // 도착 지점에서 현재 지점을 뺀 만큼만 더한다.
                result += b - current;
                break;

            // 왼쪽으로 이동할 때, 현재 지점은 b보다 크고, 다음 지점은 b보다 작거나 같으면
            } else if (!direction && current > b && next <= b) {
                // 현재 지점에서 도착 지점을 뺀 만큼만 더한다.
                result += current - b;
                break;
            }

            // 총 이동 거리 계산
            result += next > current ? next - current : current - next;
            
            // 다음 계산을 위한 데이터 변경
            current = next;
            distance *= 2;
            direction = !direction;
        }

        System.out.println(result);
    }
}

• 학생의 이름과 점수를 map에 담아 두 번째로 낮은 점수를 가진 학생의 이름을 출력할 수 있다.
• 만약, map의 길이가 1인 경우 한 학생을 제외한 나머지 학생은 모두 점수가 0이므로 map에 담겨 있는 학생이 최고 점수이자 두 번째로 낮은 점수가 된다.
• 오름차순 정렬된 map의 첫 번째 value는 가장 낮은 점수가 되며, 다음으로 높은 점수를 가진 학생이 두 번째로 낮은 점수를 가진 학생이 된다.
• 만약 다음으로 높은 점수를 가진 학생이 없는 경우, map에 담긴 학생들이 두 번째로 높은 점수를 가졌으며 여려 명이 된다. 따라서 Tie를 출력한다.