[코딩테스트] SWEA 1259 금속막대(Java)

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 1259 금속막대입니다.

포인트

문제의 포인트를 잡기 앞서, 조건을 몇개 추가하여야 문제의 해결이 가능합니다.

첫째, 나사들의 중복은 존재하지 않아야합니다. 예를 들어 숫나사의 값들에는 중복이 없으며, 암나사의 값들에는 중복이 없습니다.

둘째, 남는 나사는 없습니다. 즉 모든 나사는 연결이 가능합니다.

 

이러한 조건을 바탕으로 맨 첫번째 숫나사는 어떠한 나사의 암나사와도 일치하지 않음을 알 수 있습니다.

첫번째 나사를 기준으로 암나사의 값과 숫나사의 값이 일치하는 나사를 찾고 그 다음 나사로 반복해주면 문제를 해결할 수 있습니다.

소스코드

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

public class Q1259 {
    static int T, N;
    static Map<Integer, Integer> chain;
    static Map<Integer, Integer> revChain;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());

            chain = new HashMap<>();
            revChain = new HashMap<>();

            for (int i = 0; i < N; i++) {
                int male = Integer.parseInt(st.nextToken());
                int female = Integer.parseInt(st.nextToken());
                chain.put(male, female);
                revChain.put(female, male);  // 역방향도 저장
            }

            // 시작점 찾기: 수나사인데, 누구의 암나사에도 안 쓰인 것
            int start = -1;
            for (int key : chain.keySet()) {
                if (!revChain.containsKey(key)) {
                    start = key;
                    break;
                }
            }

            sb.append("#").append(t);

            // 체인 순서대로 출력
            while (chain.containsKey(start)) {
                int end = chain.get(start);
                sb.append(" ").append(start).append(" ").append(end);
                start = end;
            }

            sb.append("\n");
        }

        System.out.print(sb);
    }
}

코드 설명

• 암나사와 숫나사의 중복이 존재하지 않기에 이를 저장하는 자료구조 Map을 사용합니다.
  • chain: 숫나사가 key고 암나사가 value인 map
  • revChain: 암나사가 key 숫나가사 value인 map

int start = -1;
for (int key : chain.keySet()) {
    if (!revChain.containsKey(key)) {
        start = key;
        break;
    }
}

• 숫나사의 value가 어떠한 암나사와도 일치하지 않는 나사 찾기

while (chain.containsKey(start)) {
    int end = chain.get(start);
    sb.append(" ").append(start).append(" ").append(end);
    start = end;
}

• map을 순회하면서 나사의 연결을 찾습니다.