[Algorithm/Java] 백준 14467번 - 소가 길을 건너간 이유 1

---

https://www.acmicpc.net/problem/14467

---

🔍 문제 풀이

풀이

1. 소 번호별로 이전 위치를 저장할 Map을 생성한다.
2. 입력받은 (소 번호, 현재 위치)를 처리한다.
3. 처음 보는 소라면 map.put(a, b)로 저장만, 이미 본 소인데 이전 위치와 다르면 cnt++ 후 위치 갱신
4. 모든 입력 처리 후 cnt 출력

배운 점

처음엔 visited 배열로 소가 등장했는지만 체크하려고 했다.

3 1
3 1

하지만, 위 예시처럼 같은 소가 같은 위치에 연속해서 등장하는 경우도 있는데,

단순히 방문 여부만 가지고 판단하면 이미 등장한 소라는 이유로 이동으로 잘못 처리될 수 있다.

그래서 위치 정보까지 저장할 수 있는 int[] 배열을 사용해서, 처음 등장한 소인지 + 이전 위치와 다른지를 같이 확인하도록 수정했다.

💻 전체 코드

HashMap 사용

package org.example;

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

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());

        int cnt = 0;

        Map<Integer, Integer> map = new HashMap<>();

        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if(!map.containsKey(a)){
                map.put(a, b);
            }else if(map.get(a) != b){
                cnt++;
                map.put(a, b);
            }

        }
        System.out.println(cnt);

    }
}

배열 사용

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

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());
        int[] cow = new int[11];
        Arrays.fill(cow, -1);

        int cnt = 0;

        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if(cow[a] == -1){
                cow[a] = b;
            }else if (cow[a] != b) {
                cnt++; // 위치 바뀜
                cow[a] = b; // 위치 갱신
            }
        }
        System.out.println(cnt);

    }
}