[JAVA] 백준 14467번 소가 길을 건너간 이유 1

구분 : 구현

 

코드

public class Main {
    //14467 소가 길을 건너간 이유 1
    static int n;
    static int[] cow;
    static boolean[] isfirst;

    static int result;
    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        result  = 0;

        cow = new int[n + 1]; //0으로 모두 초기화
        isfirst = new boolean[n + 1];
        for(int i = 1; i <= n; i++){
            st = new StringTokenizer(br.readLine());
            int cownum = Integer.parseInt(st.nextToken());
            int side = Integer.parseInt(st.nextToken());

            //만약 처음일 때
            if(!isfirst[cownum]){
                cow[cownum] = side;
                isfirst[cownum] = true;
            }else {
                if (cow[cownum] != side) {
                    cow[cownum] = side;
                    result++;
                }
            }
        }

        System.out.println(result);


    }
}

 

int cow[] : 소의 위치를 저장하는 배열

boolean isfirst[] : 해당번호의 소의 위치 파악이 처음인지 아닌지 확인할 수 있는 배열

 

cow[cownum(소의 번호)] = side(소의 위치)

isfirst[ cownum(소의 번호)] = false -> 해당 번호 소의 위치 파악이 처음임.

isfirst[ cownum(소의 번호)] = true -> 해당 번호 소가 이전에도 나온 적이 있음.

 

풀이 방법

 

소의 수만큼 for문을 돌리고

 

번호당 소의 첫 위치를 알아야하기 때문에 isfirst 배열을 false로 초기화시키고

false일때(해당 번호의 소가 처음 나왔을 때) cow배열의 해당번호인덱스에 위치를 넣는다.

그런 다음 처음이 아니라는 표시로 false를 true로 바꿔준다.

 

소의 수만큼 for문이 돌아가는 동안 이전에 나왔던 소의 번호가 또 다시 나온다면

해당 번호의 isfirst배열의 값은 true이다.

이때는 cow배열의 값이 다르다면 위치를 이동했다는 의미이므로

위치를 업데이트해준 다음, 이동 횟수를 의미하는 변수 result값을 하나 증가시킨다.

 

for문이 끝나면 result값을 출력한다.