문제 풀이
위 그림처럼 돌림판에서 두 번 나오면 해당 수를 지워간다.
소스 코드
첫 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys
input = sys.stdin.readline
n = int(input()) # 3
arr = list(map(int, input().split())) # [1, 3, 3, 2, 1, 2]
visited = [0] * n # [0, 0, 0]
answer = 0
for i in arr:
if visited[i-1] >= 0:
visited[i-1] += 1
if visited[i-1] == 2:
visited[i-1] = 0
answer = max(answer, sum(visited))
if answer == n:
break
print(answer)
위와 같이 구현했더니 시간 초과가 났다. 다른 분들 풀이도 비슷하던데 answer 갱신해주는 부분에서 sum() 계산시 시간이 많이 걸리는 거 같다.
최종 풀이는 cnt를 계산해주는 것으로 바꿔서 풀어봤다.
최종 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys
input = sys.stdin.readline
n = int(input()) # 3
arr = list(map(int, input().split())) # [1 3 3 2 1 2]
visited = [False] * n
cnt = 0
answer = 0
for i in arr:
if not visited[i-1]:
cnt += 1
visited[i-1] = True
else:
cnt -= 1
visited[i-1] = False
answer = max(answer, cnt)
if answer == n:
break
print(answer)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.*;
public class indecisiveness {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int[] visited = new int[100001]; // 기본 타입으로 배열 선언시 초기값은 0
int n = sc.nextInt();
int sum = 0;
int max = 0;
for(int i = 1; i<= n*2;i++)
{
int arr = sc.nextInt();
if(visited[arr] == 0)
{
sum++;
visited[arr]++;
}
else
sum--;
if(sum > max)
max = sum;
}
System.out.println(max);
}
}