[Softeer] GBC - Java

https://softeer.ai/practice/info.do?idx=1&eid=584&sw_prbl_sbms_sn=178750 

Softeer

---

1. 문제

구간 길이, 구간별 제한 속도가 주어진다.

임의의 구간 길이, 구간별 제한 속도가 주어질 때

제한 속도가 가장 크게 벗어난 값을 구하는 문제이다.

무슨 뜻이냐면 50m길이의 구간에서 50m/s의 제한 속도를 가져야 하는데

임의의 구간 60m길이의 구간에서 76m/s의 제한 속도를 가진다면

차이가 나는 구간은 (0~50m), (51~60m) 두 구간이 생길 것이고

제한 속도의 차이는 (76-50=26 m/s), (76-40=36 m/s) 로 차이가 더 큰 36이 답이 될 것이다.

이렇게 구한 차이 중 가장 큰 차이가 답이 된다.

 

2. 풀이

구현 문제다. 배열의 인덱스를 활용해서 풀었다.

처음에는 구간의 시작점, 끝점을 멤버변수로 가지는 클래스를 만들고 그 클래스의 리스트를 만들었는데, 

이렇게 푸니까 틀렸다고 나왔다. 그래서 방법을 바꿨다. 1시간 32분 걸렸다.

 

구간의 총 길이는 100m로, 0~100까지를 인덱스로 가지는 arr[101]을 만들고

각 인덱스마다 차이를 넣어줬다.

처음에 for문으로 정해진 제한 속도를 먼저 넣어주고

그다음에 또 for문으로 임의의 제한속도와 기존의 배열값(정해진 제한 속도)과의 차이로 값을 갱신한다.

여기서, for문 안에 max값을 갱신하는 Math.max(ans, arr[idx]); 를 두어 계속해서 차이의 최대값을 갱신해주었다.

이렇게 풀었더니 통과했다.

 

주의해야할 점은 arr[0]이다. 인덱스가 0일 때 제한 속도를 넣고 시작하여

1~50

1~40

1~10 이런식으로 1부터 구간길이만큼 반복문을 돌려야 100까지 값이 채워진다.

 

3. 코드

import java.util.*;
import java.io.*;


public class Main
{
    static int N, M, ans=0;
    static int[] arr = new int[101];

    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        int idx = 0;
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int len = Integer.parseInt(st.nextToken());
            int speed = Integer.parseInt(st.nextToken());
            if (i==0) {
                arr[idx] = speed;
                idx++;
            }
            for (int j=1; j<=len; j++) {
                arr[idx] = speed;
                idx++;
            }
        }
        idx = 0;
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int len = Integer.parseInt(st.nextToken());
            int speed = Integer.parseInt(st.nextToken());
            if (i==0) {
                arr[idx] = speed - arr[idx];
                ans = Math.max(ans, arr[idx]);
                idx++;
            }
            for (int j=1; j<=len; j++) {
                arr[idx] = speed - arr[idx];
                ans = Math.max(ans, arr[idx]);
                idx++;
            }
        }
        
        System.out.println(ans);
    }
}

 

4. 사담

배열의 인덱스를 활용하면 나름 풀기 편한 문제들이 있다.

문제가 복잡하면 초심으로 돌아가서 배열의 인덱스를 생각해보자..