20913번: Mixtape Management
Output $n$ distinct integers in lexicographically increasing order, your sequence of filenames. All numbers must be positive integers less than $10^{1000}$ and may not contain leading zeroes. Any valid sequence of filenames will be accepted.
www.acmicpc.net
이런 구성적은 재밌어서 좋다
노트에 조금 끄적이다 보면 두 개의 숫자만으로도 풀수있다는 사실을 금방 알 수 있다. 나는 1과 2로 풀었다.
n번째 단계에서, 입력으로 주어진 배열의 k번째 수가 n일때, 정답 배열에서 1부터 (k-1)번째까지는 1을, k번째부터는 2를 뒤에 붙여준다. 그리고 k번째 수는 그 뒤로 건들지 않는다. 이게 뭔소리냐 하면...
읽어도 별 도움은 안될것같다... 요즘 잠을 너무 많이자서 상태가 이상하다
입력이 4 1 3 2 인 경우를 살펴보자.
[1단계]
입력으로 주어진 배열에서 1의 위치 앞까지는 1, 1의 위치부터는 2를 적어준다.
이제 저 빨간 2는 건들지 않을 것이다.
[1, 2, 2, 2]
[2단계]
똑같이 해나간다.
[11, 2, 21, 22]
[3단계]
[111, 2, 212, 22]
[4단계]
[1112, 2, 212, 22]
이 배열은 사전순으로 정렬되어있으며, 또한 입력에 맞게 수의 크기대로 정렬되어있다.
내가 쓰고도 뭔소리인지 모르겠다. 나도 거의 감으로 푼것이라..
[소스코드]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
n = int(input())
a = list(map(int, input().split()))
ans = ["" for _ in range(n)]
v = [False for _ in range(n)]
now = 0
while now < n:
now += 1
for i in range(n):
if a[i] == now:
for j in range(n):
if v[j]: continue
if j < i:
ans[j] += "1"
else:
ans[j] += "2"
v[i] = True
# print(ans)
for i in ans:
print(i, end=" ")
|
cs |
v는 확정된 문자열을 건드리지 않기 위한 배열이다.
now는 앞서 설명한 단계이고, i는 입력 배열에서의 now의 위치를 찾는 역할을 해준다.
j와 i의 대소관계를 이용하여 1을 붙일지, 2를 붙일지 결정한다.
지금 글을 쓰는 도중에 알아낸건데 굳이 j에 대한 for문을 넣어서 코드가 더러워진것 같다. 필요는 없더라..
오타, 오류 지적 환영합니다.
'백준 문제풀이' 카테고리의 다른 글
| 백준 1655 - 가운데를 말해요 [Python] (0) | 2021.03.22 |
|---|---|
| 백준 21133 - N-Queen 2 [Python] (0) | 2021.03.12 |
| 백준 19240 - 장난감 동맹군 [C++] (0) | 2021.01.20 |
| 백준 16161 - 가장 긴 증가하는 팰린드롬 부분수열 [Python] (0) | 2021.01.06 |
| 백준 20531 - 인간관계 [Python] (0) | 2021.01.04 |