[Problem] 야바위 게임(백준 1547번)
백준 1547번
문제
https://www.acmicpc.net/problem/1547
첫 풀이
처음에는 문제에서 설명한 그대로 구현을 했습니다.
그렇게 작성한 제 코드는 다음과 같습니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] ar) throws Exception{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
int[] arr = {0, 1, 2, 3};
for(int i=0; i<n; i++){
String[] line = in.readLine().split(" ");
int n1 = Integer.parseInt(line[0]);
int n2 = Integer.parseInt(line[1]);
int n1Pos = getPos(arr, n1);
int n2Pos = getPos(arr, n2);
arr[n1Pos] = n2;
arr[n2Pos] = n1;
}
System.out.print(arr[1]);
}
public static int getPos(int[] arr, int a){
int res = 0;
for(int i=1; i<4; i++){
if(arr[i]==a){
res = i;
break;
}
}
return res;
}
}
이렇게 작성하고, 다른 사람들은 어떻게 풀었나 코드를 참고했습니다.
그런데 저보다 더 빠르게 푸신 분들은 이렇게 안풀고,
컵이 옮겨질 때 공도 같이 움직이는 방식으로 구현했습니다.
거기에 주어진 컵 이동 명령을 다르게 적용시켰습니다.
예를 들어 입력이
2
1 3
2 3
일 때, 원래 문제에서 설명한대로 하자면 컵의 번호대로 바꿔야 하므로,
[1, 2, 3] -> [3, 2, 1] -> [2, 3, 1]
으로 순서가 바뀌고, 공은 첫번째 자리에 그대로 있으므로, 정답은 2가 됩니다.
그런데 다른 분들의 풀이를 보니
주어진 입력을 컵의 번호대로 바꿔주는게 아니라 해당 자리에 있는 컵끼리 바꿔주는 대로 했습니다.
예를 들어 1 3 이면 1번컵과 3번컵을 바꿔주는게 아니라,
첫번째 자리에 있는 컵과 세번째 자리에 있는 컵을 바꿔줍니다. 즉,
[1, 2, 3] -> [3, 2, 1] -> [3, 1, 2]
가 되고, 원래 공은 1번컵에 있고, 컵과 같이 움직였다고 생각하므로,
1번 컵이 위치하고 있는 두번째 자리, 즉 정답은 2가 됩니다.
이렇게 구현한 코드는 다음과 같습니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] ar) throws Exception{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
int[] cup = {0, 1, 2, 3};
for(int i=0; i<n; i++){
String[] line = in.readLine().split(" ");
int a = Integer.parseInt(line[0]);
int b = Integer.parseInt(line[1]);
int temp = cup[a];
cup[a] = cup[b];
cup[b] = temp;
}
for(int i=1; i<4; i++){
if(cup[i]==1){
System.out.print(i);
break;
}
}
}
}
두 방법의 효율성 비교
첫번쨰 방법은 컵을 이동시키는 명령 한번당 getPos() 메소드가 두번 실행됩니다.
그리고 getPos() 메소드는 배열 전체를 탐색하죠. 즉, O(N)이 걸립니다.
만약 K번 컵이동 명령이 있다면 복잡도는 O(KN) 이 됩니다.
두번째 방법은 한번 명령당 cost는 O(1)이니,
K번 명령에는 O(K)가 걸립니다.
거기에 맨 마지막에 1번 컵의 위치를 찾기위해 배열 전체를 한번 탐색하니 O(N)이 걸리고
모든 시간을 합치면 O(K + N) 이 걸립니다.
N이나 K가 커질수록 두번째 방법이 더 효율적일 것입니다.
그럼 왜 두번째 방법으로 해도 결과가 같게 나오는 것일까요…
왜 결과는 같은가
처음엔 이해가 잘 안되서 구글링을 좀 해봤습니다.
그래서 알아낸 점은… 과거에 문제 설명은 두번째 방법으로 설명돼있었다는 것입니다.
최근에 바뀐듯 합니다.
어쨋든 왜 결과가 같은지 살펴보겠습니다.
입력이 다음과 같을 때
2
1 3
2 3
첫번째 방법대로 하면 컵의 위치는 다음과 같이 바뀝니다.
[1, 2, 3] -> [3, 2, 1] -> [2, 3, 1]
그리고 두번쨰 방법대로 하면 컵의 위치는 다음과 같습니다.
[1, 2, 3] -> [3, 2, 1] -> [3, 1, 2]
두번째 방법을 기준으로 한다면, 첫번째 방법으로 나오는 배열은 다음과 같이 해석할 수 있습니다.
마지막 배열의 [2, 3, 1]에서 1이 나타내는 바는
3번 컵의 위치가 1이다 == 첫번째 자리에 3번 컵이 있다
즉, 입력 값에서 1 3 은 원래 문제에서는 1번 컵과 3번 컵을 바꾸라는 의미이지만,
첫번째 자리에 있는 컵과 세번째 자리에 있는 컵을 바꾸란 의미도 됩니다.
이 뜻대로 바꾼게 두번째 방법대로 배열을 바꾸는 것입니다.
그렇다면 명령대로 다 바꾼후에,
첫번째 방법대로 라면 첫번째 수인 2가 정답이 됩니다.
여기서 2가 나타내는 바는
1번 컵의 위치가 2이다 == 두번째 자리에 1번 컵이 있다
즉, 정답인 2를 구하기 위해서는
두번째 방법대로 구한 마지막 배열에서 1의 위치가 어딘지 찾으면 됩니다.
마무리
처음엔 이 문제를 보고 ‘구현하기 쉽네’ 라고 문제 그대로 풀어버렸습니다.
물론 답은 맞았지만, 만약 명령의 수인 K값이 커지면 커질수록
첫번째 방법보다는 두번째 방법이 훨씬 빠른 코드가 될 것입니다.
분명 이 문제를 보고 처음부터 두번째 방법으로 푼 사람도 있을 것입니다.
그런 분들에 비하면 아직 한참 부족한 것 같습니다.
더 깊게 생각하는 습관을 가져야할 것 같습니다.
그런 의미에서 두번째 방법 동영상 투척