문제 바로가기

접근방식

처음엔 리스트로 접근했다.
요소를 모두 리스트에 집어넣어서 처음 인덱스부터 탐색하면서 이웃한 숫자가 짝수면 숫자를 빼는 식으로 했더니 시간초과가 났다.
그래서 클로드한테 물어보니까(요즘은 gpt보다 클로드가 코드를 잘 짜주는 느낌...) 스택을 추천해줬다. 어떤 블로그글에선 deque를 썼다고도 하는데 뭘 쓰든 자유지만 일단 뭐든 리스트보단 빠른 것 같다.

첫번째 - 리스트(시간초과)

모든 요소를 다 add하고 풀이를 시작해서 그런지 시간초과

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class b1_28323 {
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int n=Integer.parseInt(br.readLine());
        List<Integer> list=new ArrayList<>();
        StringTokenizer st=new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            list.add(Integer.parseInt(st.nextToken()));
        }

//        System.out.println(list.toString());

        int t=1;
        while(t<list.size()){
            if((list.get(t)+list.get(t-1))%2!=0){
                t++;
            }else{
                list.remove(t+1);
            }
        }

        System.out.println(list.size());
    }
}

두번째 - 스택(정답)

반면 요소 넣을때마다 확인하고 넣을지 말지 결정하니 맞았다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class b1_28323_2 {
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int n=Integer.parseInt(br.readLine());
        Stack<Integer> list=new Stack<>();
        StringTokenizer st=new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            int c=Integer.parseInt(st.nextToken());

            if(list.isEmpty()){
                list.push(c);
            }else{
                if((list.peek()+c)%2==1){
                    list.push(c);
                }
            }
        }

        System.out.println(list.size());
    }
}

후기

다양한 자료구조를 알아야겠다 생각했다.
알고리즘 안풀다보니 점점 까먹어서...
이제 susc 알고리즘 스터디 시작하니까 열심히 다시 감 잡아봐야지