1259번 - 금속막대

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
    1-1. 링크
    1-2. 문제 해석
2. 코드
3. 실행시간
4. 우리 반 1등 코드와의 차이
5. 싸피 1등 코드와의 차이

 

 

 

---

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

문제 해석에 앞서서 싸피하는 입장에서 이런말하기 좀 그렇지만 SWEA에는 참 별로인 문제들이 많다.

허술하다고 해야하나? 명확하지 못하다고 해야하나?

문제에서 확실히 줘야하는 조건들을 주지 않아서 삽질하게 만드는 경우가 많다.

이 문제도 마찬가지다.

문제 링크를 들어가보니 이미 많은 사람들이 불만을 표출하고 있다.

그래서 댓글에 적혀있는, 문제에서는 언급되지 않은 조건을 몇 개 적으려고 한다.

 

• 나사가 남는 경우는 없다.
  • 1 2 / 2 3 / 2 4 이렇게 주어지는 경우는 없다는 뜻이다. 이 경우 2 3 혹은 2 4가 무조건 남게 되는데 이런 테스트케이스는 주어지지 않는다.
  • 나사가 남는다고 가정해서 코드를 짜면 복잡해진다. 삽질하게 됨
• 수나사끼리 중복 없음, 암나사끼리 중복 없음
  • 1 2 라는 나사가 있으면 1 3 / 1 4 / 1 5 / ... 1 n 나사는 존재하지 않는다.
  • 1 2 라는 나사가 있으면 1 2 / 2 2 / 3 2 / ... n 2 나사는 존재하지 않는다.
• 나사의 굵기와 개수의 범위는 주어지지 않는다.
  • 주어졌다면 문제가 더 깔끔했겠지만 주어지지 않았으므로 모든 범위에서 가능한 풀이를 내도록 노력해본다.
  • 만약 범위가 꼭 필요하다면 굵기는 최대 30, 개수는 최대 20으로 잡고 푼다.

 

위 조건들은 주어진 테스트 케이스를 읽어보면 알아낼 수 있는 조건이긴 하나

SWEA가 히든케이스가 없어서 그렇지 일반적인 코테에서는 한 두개의 테스트케이스만 제공하므로

테스트케이스를 읽어보고 조건을 스스로 찾는다는 것은 일반적인 경우가 아니라고 생각한다.

특히 그 조건이 입력 조건이라는 점은 더더욱.

 

아무튼 이 문제는 남는 나사가 없이 줄줄이 사탕처럼 쭉 이어지기 때문에 그냥

첫 시작 부분을 찾아내고 그 뒤로 쭉 이으면 그게 가장 긴 결합이된다.

 

 

2. 코드

public class Day14_1259_금속막대 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int testCase = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= testCase; tc++) {
			int n = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			HashMap<Integer, Integer> map = new HashMap<>();

			// 암나사, 수나사를 map에 저장
			for (int i = 0; i < n; i++) {
				int male = Integer.parseInt(st.nextToken());
				int female = Integer.parseInt(st.nextToken());
				map.put(male, female);
			}

			// 시작 번호 구하기
			int idx = 0;
			for (int key : map.keySet()) {
				if (!map.containsValue(key)) {
					idx = key;
					break;
				}
			}

			// 순서 구하기
			sb.append("#").append(tc).append(" ");
			while (map.containsKey(idx)) {
				sb.append(idx).append(" ").append(map.get(idx)).append(" ");
				idx = map.get(idx);
			}
			sb.append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

}

나는 수나사와 암나사의 굵기를 map에 저장했다.

처음 사용될 나사를 찾기 위해 반복문으로 map을 돌면서

key와 동일한 값이 val에 있는지 탐색했다.

(= 수나사와 동일한 굵기가 암나사에 있는지 탐색했다.)

 

중간에 끼어질 나사는 수나사와 동일한 굵기의 암나사가 있지만

첫 시작부분에 끼어질 나사는 수나사와 동일한 굵기의 암나사가 없기 때문이다.

 

 

3. 실행시간

시무룩

 

😔😔😔😔😔😔😔

좋은 코드가 아니었나보다.

 

 

4. 우리 반 1등 코드와의 차이

 

네 가져가세요 제 포인트...

 

이건 못 참지

패배의 원인을 분석하기 위해 우리 반 1등 코드를 뜯어보았다.

다른 점은 딱 한 가지였다.

나는 map을 사용해서 시작 부분을 찾고 -> 순서에 맞게 출력

동기는 dfs를 사용해서 가장 긴 결합을 찾으면서 순서(인덱스)를 배열에 저장 -> 순서(인덱스)대로 출력

 

그니까 한 마디로 모든 경우의 수를 다 뒤져봤다는건데 이게 더 빠를 줄이야...

 

 

5. 싸피 1등 코드와의 차이

싸피 1등. 실행시간이 와...

 

 

사실 나는 이 문제를 DP로 어떻게 접근해야할지 감이 안왔다.

그래서 내 나름대로의 방법으로 푼건데

우리반 1등 코드를 보니 이 친구도 DP를 시도하려다가 포기한 것 같았다.

코드 그 어느곳에서도 쓰이지 않은 DP배열 선언만이 달랑 남아있었다.

그래서 이번엔 싸피 1등 코드를 뜯어보려고 한다.

 

 

포인트 네고좀요...

 

충격적이게도 1등 코드에도 DP 알고리즘은 없고 DFS만 존재했다.

코드도 특별한 기술이 들어가거나 한 것은 없었다. 배열 대신 ArrayList를 사용했다는 것 뿐

수나사와 암나사를 하나의 클래스로 만들어 관리했다는 것 뿐

흠.. DFS를 사용해야 했던 문제였던걸까.. 약간 허무했다.

 

 

 

 

---

💡 느낀 점

• 이 문제에 DP를 어떻게 적용시킬 수 있지? 아직도 감이 잘 안온다. 월요일에 수업을 들어보면 알겠지
• 배열이 ArrayList보다 빠르다고 생각했는데 아닌가?
  • 인터넷에 검색해보니 배열이 빠른게 맞다고 한다. 링크
  • 그렇다면 대체 이 코드가 68ms가 나올 수 있었던 이유가 뭐지? 진짜 모르겠다. 평범한데!!?
• 누가 저에게 이유를 설명해주세요...

---