[백준] 3665번 최종순위 문제 풀이

문제

이미지를 클릭하면 문제 페이지로 이동합니다.

 

 

풀이

고려해야할 점

 

• 순서 관계 변경:
  • 주어진 순서에 대해 여러 쌍의 순서 관계를 변경해야 하므로, 현재 상태의 순서와 이후에 주어지는 관계 변경이 어떻게 영향을 미치는지 추적해야 한다. 
  • currentPosition 배열에서 순서를 변경할 때, 중복된 위치나 범위 밖의 위치가 발생하지 않도록 해야 한다. 
• 유효성 검사:
  • 변경된 순서가 유효한지 검증하는 과정에서 resultMap에 중복된 위치가 없도록 해야 한다.
  • 위치가 배열 범위를 벗어나는지, 중복된 노드가 있는지 체크하여 잘못된 순서인 경우 “IMPOSSIBLE”을 출력한다. 
  • "?"인 경우는 존재하지 않는다. 올바른 순위를 결정할 수 없으면 모두 "IMPOSSIBLE"이다. 
• 최적화 고려:
  • 많은 쌍의 관계 변경이 있을 수 있으므로 효율적으로 현재 순서를 업데이트하는 방법이 필요하다.
  • O(n)의 시간 복잡도로 문제를 해결해야 한다.

 

 

알고리즘 분류(백준 기준)

• 그래프 이론
• 위상 정렬
• 방향 비순환 그래프 

 

풀이 아이디어

 

• 초기화:
  • 각 테스트 케이스에 대해 주어진 초기 순서를 arr 배열에 저장한다. 각 인덱스는 순위를 의미한다. 
  • originalPosition 배열을 통해 각 노드의 초기 위치를 저장하여, 초기 상태를 기록합니다. 각 인덱스는 팀 번호를 의미하며 값은 팀의 순위를 의미한다. 
  • currentPosition 배열을 사용해 관계 변경에 따라 위치를 갱신할 수 있도록 초기 위치를 복사한다.
  • 순위를 두 개의 배열에 저장하는 이유는 순위 비교와 순위 변경을 따로 진행하기 위해서이다. 순위 변경은 초기 순위를 기준으로 진행한다. 
• 관계 업데이트:
  • 각 쌍 (a, b)의 관계를 읽어와 originalPosition 배열에서 a와 b의 초기 위치를 비교합니다.
  • a의 위치가 b보다 뒤에 있으면, a를 한 칸 앞으로, b를 한 칸 뒤로 이동시킵니다. 반대의 경우 a를 뒤로, b를 앞으로 이동시킵니다. 이렇게 하는 이유는 두 관계쌍이 존재할 경우, 한 쪽은 순위가 하나 올라가고 다른 한 쪽은 순위가 내려갈 수 밖에 없다. 모든 관계 쌍에 대하여 순위 증감을 실시한 후 올바른 순위가 나오면 정보가 맞는 것이다. 
  • 이 과정을 통해 모든 관계를 반영하여 currentPosition 배열을 업데이트한다. 
• 유효성 검사 및 출력:
  • currentPosition 배열을 resultMap에 매핑하여 각 노드의 위치가 범위를 벗어나거나 중복되지 않는지 검증한다.
  • 만약 잘못된 순서가 발생한다면, "IMPOSSIBLE"을 결과에 추가하고, 그렇지 않으면 최종 순서를 출력한다. 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		// 테스트 케이스의 개수 입력
		int T = Integer.parseInt(br.readLine());
		
		// 테스트 케이스별 처리
		for (int t = 1; t <= T; t++) {
			// 노드 개수 입력
			int n = Integer.parseInt(br.readLine());
			
			int[] arr = new int[n];          // 입력 순서 저장
			int[] originalPosition = new int[n + 1]; // 입력 순서에 따른 위치 저장
			int[] currentPosition = new int[n + 1];  // 현재 위치 저장
			
			// 노드의 초기 상태 입력
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
				originalPosition[arr[i]] = i; // 노드의 초기 위치 설정
			}
			
			// 초기 위치를 현재 위치 배열로 복사
			for (int i = 1; i <= n; i++) {
				currentPosition[i] = originalPosition[i];
			}
			
			// 관계 변경 횟수 입력
			int m = Integer.parseInt(br.readLine());
			
			// 각 관계 변경에 따른 위치 조정
			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				// 두 노드의 위치 비교하여 조건에 따라 위치 조정
				if (originalPosition[a] > originalPosition[b]) {
					currentPosition[a]--;
					currentPosition[b]++;
				} else {
					currentPosition[a]++;
					currentPosition[b]--;
				}
			}
			
			// 결과 검증 및 출력
			boolean isImpossible = false;
			int[] resultMap = new int[n];
			
			for (int i = 1; i <= n; i++) {
				int pos = currentPosition[i];
				
				// 위치가 범위를 벗어나거나 중복된 경우
				if (pos < 0 || pos >= n || resultMap[pos] != 0) {
					isImpossible = true;
					break;
				} else {
					resultMap[pos] = i; // 결과 배열에 노드 위치 저장
				}
			}
			
			// 결과 출력
			if (isImpossible) {
				sb.append("IMPOSSIBLE\n");
			} else {
				for (int i = 0; i < n; i++) {
					sb.append(resultMap[i]).append(" ");
				}
				sb.append("\n");
			}
		}
		
		System.out.print(sb);
	}
}