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

문제

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

15787번: 기차가 어둠을 헤치고 은하수를

코드

package com.company;

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

public class Main{

    static int n, m;
    static int[] train;

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

        train = new int[n+1];
        int order, tidx, idx;

        while(m-- != 0){
            st = new StringTokenizer(br.readLine());
            order = Integer.parseInt(st.nextToken());
            if(order == 1 || order == 2){
                tidx = Integer.parseInt(st.nextToken());
                idx = Integer.parseInt(st.nextToken()) - 1;
                if(order == 1){
                    train[tidx] = train[tidx] | (1 << idx);
                }
                else if(order == 2){
                    train[tidx] = train[tidx] & (~(1 << idx));
                }
            }

            else{
                tidx = Integer.parseInt(st.nextToken());
                if(order == 3){
                    train[tidx] = train[tidx] << 1;
                    train[tidx] = train[tidx] & ~(1 << 20);
                }
                else if(order == 4)
                    train[tidx] = train[tidx] >> 1;
            }
        }

        Set<Integer> set = new HashSet<>();
        for (int i = 1; i < n+1; i++) {
            set.add(train[i]);
        }
        System.out.println(set.size());
        br.close();
    }
}

풀이

구현 문제가 항상 그렇듯 풀이방식에 대해서 생각을 하기는 쉽지만 이를 손으로 옮기는 것은 다른 이야기 인것 같다. 처음에는 기차와 좌석에 대한 정보를 저장하기 위해 2차원 배열을 만들어 저장을 하려고 하였으나 생각보다 구현이 까다로워진다는 것을 깨닫고 결국은 답을 찾아 보았다. 나는 답지에서는 좌석에 대한 정보를 2진법으로 표현해 기차에 대한 정보는 1차원 배열로 저장을 하였다. 그리고 만약 해당 열차에 승객이 탑승하거나 하차하면 << >> 을 통해 연산을 진행한다. 그리고 명령이 3이나 4일경우에는 2의 보수연산처럼 1<<20을 해서 가장 끝에 있는 자리수만 1으로 만들어주고 & ~ | 을 적절하게 사용해서 값을 구해준다.

그리고 나서 열차들의 정보를 set에 넣는다. 이때 중요한 점은 중복에 대해서 신경을 쓰지 말고 넣어 준다는 점이다. (어차피 set은 중복을 허용하지 않기때문에) 그리고 마지막으로 정답을 출력할때는 set의 크기를 출력해준다.