BOJ) 욱제는 결정장애야!!

욱제는 결정장애야!!

14646번: 욱제는 결정장애야!!

풀이

 

처음으로 시도했던 방법은 반환될 정답을 N으로 초기화하고, ArrayList에 메뉴를 넣으면서, 이미 들어가 있는 메뉴인지 아닌지 판단해서 정답을 1씩 빼주는 것이었다.

하지만, 시간초과가 뜨면서 ArrayList의 contains를 사용하기에는 비효율적이라는 것을 알게되었다.

 

그래서 배열로 선언해서 메뉴가 나온 횟수를 늘려가기로 했다.

돌림판을 돌릴 때마다, 메뉴에 해당하는 인덱스를 1 증가시켜주었고, 1인 경우 스티커가 붙어있는 경우니까 count를 증가 시켰다.

또한 2인 경우(총 2번밖에 나오지 않기 때문에 else), count를 감소시켰다.

증감이 끝나면 answer와 max값으로 갱신하면서 답을 구해주었다.

 

코드

 

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

public class Indecision_14646 {
    public static void main(String[] args) throws IOException {
        System.out.println(solution(new BufferedReader(new InputStreamReader(System.in))));
    }

    private static int solution(BufferedReader br) throws IOException {
        int answer =0;
        int N = Integer.parseInt(br.readLine());
        int[] menuArr = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());

        int cnt =0;
        for(int i=0; i<2*N; i++) {
            int idx = Integer.parseInt(st.nextToken());
            if(++menuArr[idx] ==1) {
                cnt++;
            } else {
                cnt--;
            }
            answer = Math.max(cnt,answer);
        }

        return answer;
    }
}