문제 설명

회사 출입 기록이 주어졌을 때,
현재 회사에 남아있는 사람들의 이름을 출력하는 문제이다.

각 기록은 다음과 같이 주어진다.

이름 enter → 출근
이름 leave → 퇴근

마지막 상태 기준으로 회사에 남아 있는 사람들만 출력하면 된다.

---

입력

첫째 줄

N

출입 기록 개수

다음 N줄

이름 enter/leave

조건

2 ≤ N ≤ 1,000,000

---

출력

현재 회사에 있는 사람의 이름을

사전순 역순

으로 출력한다.

---

입력 예시

4
Baha enter
Askar enter
Baha leave
Artem enter

출력 예시

Askar
Artem

---

문제 해결 아이디어

이 문제의 핵심은 다음이다.

현재 회사에 있는 사람만 관리

즉

• enter → 추가
• leave → 제거

을 반복하면 된다.

---

내가 작성한 코드

나는 List를 사용해서 사람을 관리했다.

코드

import java.util.*;

class Main
{
    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        List<String> member = new ArrayList<>();

        sc.nextLine();

        for(int i = 0; i < N; i++) {

            String[] input = sc.nextLine().split(" ");

            if(input[1].equals("enter")) {
                member.add(input[0]);
            } else {
                member.remove(member.indexOf(input[0]));
            }
        }

        Collections.sort(member);
        Collections.reverse(member);

        for(String s : member)
            System.out.println(s);
    }
}

---

강의 코드

강의에서는 모든 기록을 저장한 뒤
정렬 후 상태를 판별하는 방식으로 해결했다.

코드

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

class Main
{
    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        String[][] records = new String[N][2];

        for (int i = 0; i < N; i++) {
            records[i][0] = sc.next();
            records[i][1] = sc.next();
        }

        Arrays.sort(records, new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                return o2[0].compareTo(o1[0]);
            }
        });

        for (int i = 0; i < N - 1; i++) {
            if (records[i][1].equals("enter") && !records[i][0].equals(records[i + 1][0]))
                System.out.println(records[i][0]);
        }

        if (records[N - 1][1].equals("enter"))
            System.out.println(records[N - 1][0]);
    }
}

---

내 코드 vs 강의 코드 비교

1. 자료구조 차이

내 코드

List 사용

• enter → add
• leave → remove

---

강의 코드

2차원 배열 사용

• 모든 기록 저장
• 정렬 후 판단

---

2. 시간초과 원인

내 코드의 핵심 문제는 이 부분이다.

member.remove(member.indexOf(input[0]));

이 연산은

indexOf → O(N)
remove → O(N)

즉 한 번 제거할 때마다

O(N)

이 걸린다.

전체 입력이 최대

1,000,000

이므로

O(N²)

수준이 되어 시간초과가 발생한다.

---

3. 강의 코드의 접근 방식

강의 코드는

정렬 + 상태 판별

을 사용한다.

정렬 비용

O(N log N)

으로 해결 가능하다.

---

4. 핵심 차이

항목	내 코드	강의 코드
접근 방식	현재 상태 유지	전체 기록 정렬
삭제 방식	리스트 remove	정렬 후 판단
시간복잡도	O(N²)	O(N log N)

---

더 좋은 방법 (핵심)

이 문제는 사실 다음 자료구조가 가장 적합하다.

HashSet

이유

• 추가: O(1)
• 삭제: O(1)

즉

enter → add
leave → remove

을 빠르게 처리할 수 있다.

---

핵심 개념

1. 자료구조 선택 중요

List → 느림
Set → 빠름

---

2. 시간복잡도 계산

N = 1,000,000
→ O(N²) 불가능
→ O(N log N) 또는 O(N) 필요

---

3. 문자열 정렬

Collections.sort()
Collections.reverse()

또는

TreeSet (역순)

---

시간 복잡도

내 코드

O(N²)

→ 시간초과

---

강의 코드

O(N log N)

→ 통과

---

정리

이 문제는 단순 구현 문제처럼 보이지만
실제로는 자료구조 선택이 핵심인 문제였다.

내 코드는 List를 사용해서
삭제 연산이 느려 시간초과가 발생했다.

강의 코드는 정렬을 활용하여 해결했지만,
가장 좋은 방법은

HashSet 또는 TreeSet 사용

이다.

이 문제를 통해 배운 점은 다음과 같다.

1. 입력 크기가 크면 자료구조 선택이 매우 중요하다
2. List의 remove는 느릴 수 있다
3. Set을 활용하면 효율적으로 해결할 수 있다

즉,

자료구조 선택 = 성능

이라는 것을 잘 보여주는 문제였다.