[백준] 15787번 기차가 어둠을 헤치고 은하수를

U_U·2024년 2월 26일

15787 15787 기차가 어둠을 헤치고 은하수를 boj 구현 기차가 어둠을 헤치고 은하수를 백준 코딩테스트

문제

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

접근방법

기차 자리를 이차원배열로 구현하여 각 명령어별로 값을 변경하고,
StringBuilder를 이용하여 기차 좌석표를 String으로 받아 내 값을 비교하는 방식

대부분의 정답 코드가 비트연산자로 되어있다.
하지만 나는 비트연산자에 대해 잘 몰라서, 진짜 코딩테스트였다면 .. 라는 생각에 찾아보지 않고 2차원 배열로 문제를 풀었다.

내가 간과한 점

바로 자리를 한자리씩 옮기는 3,4 명령어일 때, 발생할 수 있는 경우의 수에 대해 생각해 보지 못했다.
단순히 자리에 사람이 앉아있을 경우, 옆으로 자리를 옮기면 된다고 생각해서 아래와 같이 코드를 짰다.

if(cmd == 3) {
	for(int j=19;j>0;j--) {
		if(trains[train][j]==1) {
			trains[train][j+1] = 1;
			trains[train][j] = 0;
		}
	}
}

else {
	for(int j=2;j<21;j++) {
		if(trains[train][j]==1) {
			trains[train][j-1] = 1;
			trains[train][j] = 0;
		}
	}
}

하지만, 이렇게 될 경우, 19번째 자리에 앉아있지 않고 20번째 자리에 사람이 앉아있다면 20 번째 자리에 하차가 구현되어있지 않다.

그래서 3과 4에 아래 코드를 처음에 넣어주었다.

if(trains[train][19]==0 && trains[train][20]==1) trains[train][20]=0;

if(trains[train][2]==0 && trains[train][1]==1) trains[train][1] =0;

두번째로는 HashSet에서 배열로는 중복값을 체크할 수 없다는 점이다.
처음에는 그냥 HashSet<int[]>라고 적었는데, 이렇게 하니깐 중복값이 모두 들어갔다. 그래서 열차별로 값을 저장한 String이 있어야 되겠다는 생각이 들었다. 아래는 배열값들을 StringBuilder로 붙이는 코드이다.

String [] trainsInteger = new String [N+1];
		for(int i=1;i<N+1;i++) {
			StringBuilder sb = new StringBuilder();
			for(int j=1;j<21;j++) {
				sb.append(trains[i][j]);
			}
			trainsInteger[i] = sb.toString();
			System.out.println(trainsInteger[i]);
		}

정답코드

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

public class Main {
	static int N;
	static int M;
	static int [][] trains;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String [] strs = br.readLine().split(" ");
		N = Integer.parseInt(strs[0]);
		trains = new int [N+1][21];
		M = Integer.parseInt(strs[1]);
		for(int i=0;i<M;i++) {
			strs = br.readLine().split(" ");
			int cmd = Integer.parseInt(strs[0]);
			int train = Integer.parseInt(strs[1]);
			if(strs.length >2) {
				int seat = Integer.parseInt(strs[2]);
				if(cmd == 1) {
					trains[train][seat] = 1;
				}
				else if(cmd == 2) {
					trains[train][seat] = 0;
				}
			}
			else {
				if(cmd == 3) {
					if(trains[train][19]==0 && trains[train][20]==1) trains[train][20]=0;
					for(int j=19;j>0;j--) {
						if(trains[train][j]==1) {
							trains[train][j+1] = 1;
							trains[train][j] = 0;
						}
					}
				}
				else {
					if(trains[train][2]==0 && trains[train][1]==1) trains[train][1] =0;
					 for(int j=2;j<21;j++) {
						 if(trains[train][j]==1) {
							 trains[train][j-1] = 1;
							 trains[train][j] = 0;
						 }
					 }
				}
			}
			
			
		}
		String [] trainsInteger = new String [N+1];
		for(int i=1;i<N+1;i++) {
			StringBuilder sb = new StringBuilder();
			for(int j=1;j<21;j++) {
				sb.append(trains[i][j]);
			}
			trainsInteger[i] = sb.toString();

		}
		
		HashSet<String> set = new HashSet<>();
		for(int i=1;i<N+1;i++) {
			set.add(trainsInteger[i]);
		}
		
		System.out.println(set.size());

	}

}