출처: [백준] 2002번 추월

문제

대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다.

소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다.

N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다. 대근이와 영식이를 도와 이를 구하는 프로그램을 작성해 보자.

입력

입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이가 적은 차량 번호 목록이 주어진다. 각 차량 번호는 6글자 이상 8글자 이하의 문자열로, 영어 대문자(‘A’-‘Z’)와 숫자(‘0’-‘9’)로만 이루어져 있다.

같은 차량 번호가 두 번 이상 주어지는 경우는 없다.

출력

첫째 줄에 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차가 몇 대인지 출력한다.

예제 입력 1

1
2
3
4
5
6
7
8
9

4
ZG431SN
ZG5080K
ST123D
ZG206A
ZG206A
ZG431SN
ZG5080K
ST123D

예제 출력 1

1

1

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11

5
ZG508OK
PU305A
RI604B
ZG206A
ZG232ZF
PU305A
ZG232ZF
ZG206A
ZG508OK
RI604B

예제 출력 2

1

3

예제 입력 3

1
2
3
4
5
6
7
8
9
10
11

5
ZG206A
PU234Q
OS945CK
ZG431SN
ZG5962J
ZG5962J
OS945CK
ZG206A
PU234Q
ZG431SN

예제 출력 3

1

2

출처

• Olympiad > Croatian Highschool Competitions in Informatics > 2002 > National Competition #1 - Seniors 1번
  • 빠진 조건을 찾은 사람: kipa00
  • 문제의 오타를 찾은 사람: pppqqqpq

알고리즘 분류

• 구현
• 자료 구조
• 문자열
• 브루트포스 알고리즘
• 해시를 사용한 집합과 맵

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import sys

input = sys.stdin.readline

N = int(input())

count = 0
input_car = {}
output_car = []

for i in range(N):
    input_car[input().rstrip()] = i

for i in range(N):
    output_car.append(input().rstrip())

for i in range(N - 1):
    for j in range(i + 1, N):
        if input_car[output_car[i]] > input_car[output_car[j]]:
            count += 1
            break

print(count)

출처: [백준] 17264번 I AM IRONMAN

문제

다들 문제 제목을 보고 요즘 가장 핫한 영화를 생각했겠지만 이 이야기는 LUL(League Us Legends) 게임에서 아이언(Iron) 티어에 있는 형동이의 슬픈 이야기이다. LUL에서 티어는 게임 실력을 판가름할 수 있는 지표이다. 그중 아이언 티어는 가장 낮은 단계에 위치해 있다. 친구인 강엽이와 건홍이에게 “Ironman”이라며 게임을 못한다고 놀림당하던 형동이는 꼭 아이언 티어에서 벗어나겠다고 결심했다. 하지만 형동이는 자신의 실력으로 절대 아이언(Iron) 티어에서 벗어나지 못하는 것을 알고 있다. LUL은 두 명의 플레이어가 같이 팀이 되어 하는 게임이기 때문에 자신이 못해도 게임에서 이길 수 있고 자신이 잘해도 게임은 질 수 있다. 형동이는 게임은 못하지만 머리가 매우 똑똑하여 LUL 게임을 해킹하여서 몇몇 플레이어와 같이 게임을 하게 되면 게임의 승패가 어떻게 되는지 알게 되었다. 하지만 해킹을 통하여 알아내지 못한 플레이어와 같이 게임을 하는 경우 형동이가 매우 못하기 때문에 같은 팀원이 아무리 잘해도 반드시 진다.

위와 같은 경우에서 “JIHOON”과 같이 게임을 하는 경우 20점(W = 20)을 획득하는 반면에 “GANGYEOP”이나 “MINSUNG”과 같이 게임 하는 경우 경우 15점(L = 15)을 잃게 된다. 뿐만 아니라, 해킹을 통해 알지 내지 못한 플레이어를 만나게 되는 경우 형동이가 매우 못하여 지기 때문에 15점을 잃게 된다. (단, 계속 지더라도 점수는 0점 밑으로 떨어지지 않는다.)

형동이가 N번에 게임을 통해서 아이언 티어에서 탈출한 경우 형동이는 “I AM NOT IRONMAN”이라고 외치지만 탈출하지 못한 경우 “I AM IRONMAN”이라고 외친다.

여기서 아이언 티어를 탈출하기 위해서 100점 (G = 100) 이상이 되어야 했다면 9번째 게임(주황색 사각형)을 하고 아이언 티어를 탈출하였기 때문에 형동이는 “I AM NOT IRONMAN”이라고 외친다. 아이언 티어에서 탈출한 경우 그 이후에 게임은 신경쓰지 않는다.

하지만 만약 탈출하기 위해서 200점(G = 200) 이상이 되어야 한다고 했을 경우 형동이는 아이언 티어를 탈출하지 못했기 때문에 “I AM IRONMAN”이라고 외치게 된다.

과연 형동이는 게임이 끝난 후 어떤 대사를 할 지 우리가 맞춰보자.

입력

첫 번째 줄에는 총 게임 횟수 N과 해킹을 통해 얻은 플레이어 정보의 수 P가 주어진다. (N과 P는 1,000이하의 자연수)

그리고 두 번째 줄에는 이긴 경우 획득 점수 W와 졌을 때 떨어지는 점수 L, 그리고 IRON 티어에서 벗어나기 위한 점수 G가 주어진다. (0 ≤ W, L ≤ 100, 1 ≤ G ≤ 100,000, 이 때, W, L, G는 정수)

그리고 다음 P개의 줄에는 플레이어의 이름과 무조건 이길 수 있는 경우 W, 무조건 지는 경우 L이라는 단어가 플레이어 이름과 쌍으로 나온다.

그리고 그 다음 N개의 줄에는 같이 게임을 하는 플레이어의 이름이 나온다.

플레이어 이름은 반드시 대문자로 나오며 길이는 20이 넘지 않는다.

출력

0점부터 시작하였을 때 형동이가 아이언 티어에서 벗어나지 못한 경우 "I AM IRONMAN!!", 아이언 티어에서 벗어난 경우 “I AM NOT IRONMAN!!”을 출력한다.

예제 입력 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

10 3
20 15 100
JIHOON W
GANGYEOP L
MINSUNG L
JIHOON
MYEONGKI
GANGYEOP
MINSUNG
JIHOON
JIHOON
JIHOON
JIHOON
JIHOON
MINSUNG

예제 출력 1

1

I AM NOT IRONMAN!!

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

10 3
20 15 100
JIHOON W
GANGYEOP L
MINSUNG L
JIHOON
GANGYEOP
JISUP
MINSUNG
JIHOON
JIHOON
MOJI
KYUNGMIN
SOOHO
SEOKGYE

예제 출력 2

1

I AM IRONMAN!!

출처

• University > 인하대학교 > 2019 인하대학교 프로그래밍 경진대회(IUPC) B번
  • 문제를 만든 사람: hahawjstk

알고리즘 분류

• 구현
• 자료 구조
• 해시를 사용한 집합과 맵

소스코드

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
29
30
31
32

import sys

input = sys.stdin.readline

N, P = map(int, input().split())

W, L, G = map(int, input().split())

hacking = {}
for _ in range(P):
    name, WL = input().rstrip().split()
    hacking[name] = WL

score = 0
for _ in range(N):
    name = input().rstrip()
    if name in hacking.keys():
        if hacking[name] == 'W':
            score += W
        else:
            score -= L
    else:
        score -= L

    if score < 0:
        score = 0
    elif score >= G:
        print('I AM NOT IRONMAN!!')
        exit(0)

print('I AM IRONMAN!!')

출처: [백준] 9322번 철벽 보안 알고리즘

문제

소희는 공개키와 개인키 한 쌍으로 보안을 유지하는 것이 매우 불편하다고 생각했다. 그래서 소희는 공개키만을 이용하는 암호화 체계를 개발했다. 이를 “철벽 보안 알고리즘”이라고 부르기로 했다. 알고리즘은 다음과 같다.

한 단어는 1~10개의 대문자(A-Z)들로 이루어진 문자열이다. 한 문장은 공백으로 구분된 단어들로 이루어졌다.

제 1 공개키는 최대 한 번만 사용된 단어들로 되어있다.

제 2 공개키는 제 1 공개키의 단어들을 재배치하여 만들어진다.

평문(암호화 되지 않은 문장)은 제 1 공개키와 같이 여러 단어들로 되어있지만, 제 1 공개키와 다르게 각 단어들은 중복이 가능하다.

암호문(암호화 된 문장)은 평문을 제 2 공개키를 만든 규칙의 반대로 재배치하여 만들어진다.

주어진 2개의 공개키와 암호문으로 평문을 복구하라.

입력

입력의 첫 줄에는 테스트 케이스의 수를 의미하는 하나의 정수가 입력된다. 정수는 100을 넘지 않는다.

각 테스트케이스마다 아래 항목들을 한 줄씩 입력받는다.

• 한 문장의 단어 수 n (1 ≤ n ≤ 1 000)
• 제 1 공개키
• 제 2 공개키
• 암호문

모든 단어들은 최소 1개, 최대 10개의 대문자들로 이루어져있다.

출력

각 케이스마다

• 암호문을 해독한 평문

을 한 줄에 줄력한다.

예제 입력 1

1
2
3
4
5
6
7
8
9

2
4
A B C D
D A B C
C B A P
3
SECURITY THROUGH OBSCURITY
OBSCURITY THROUGH SECURITY
TOMORROW ATTACK WE

예제 출력 1

1
2

B A P C
WE ATTACK TOMORROW

출처

• ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 Preliminaries E번
  • 문제를 번역한 사람: joonas
  • 문제의 오타를 찾은 사람: lakshimi

알고리즘 분류

• 구현
• 자료 구조
• 문자열
• 해시를 사용한 집합과 맵

소스코드

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

T = int(input())

for _ in range(T):
    N = int(input())
    first_public_key = list(input().split())
    second_public_key = list(input().split())
    cipher_text = list(input().split())

    rule = []
    for i in range(N):
        rule.append(second_public_key.index(first_public_key[i]))

    for i in rule:
        print(cipher_text[i], end=' ')

출처: [백준] 11655번 ROT13

문제

ROT13은 카이사르 암호의 일종으로 영어 알파벳을 13글자씩 밀어서 만든다.

예를 들어, “Baekjoon Online Judge”를 ROT13으로 암호화하면 “Onrxwbba Bayvar Whqtr”가 된다. ROT13으로 암호화한 내용을 원래 내용으로 바꾸려면 암호화한 문자열을 다시 ROT13하면 된다. 앞에서 암호화한 문자열 “Onrxwbba Bayvar Whqtr”에 다시 ROT13을 적용하면 “Baekjoon Online Judge”가 된다.

ROT13은 알파벳 대문자와 소문자에만 적용할 수 있다. 알파벳이 아닌 글자는 원래 글자 그대로 남아 있어야 한다. 예를 들어, “One is 1”을 ROT13으로 암호화하면 “Bar vf 1”이 된다.

문자열이 주어졌을 때, “ROT13”으로 암호화한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다.

출력

첫째 줄에 S를 ROT13으로 암호화한 내용을 출력한다.

예제 입력 1

1

Baekjoon Online Judge

예제 출력 1

1

Onrxwbba Bayvar Whqtr

예제 입력 2

1

One is 1

예제 출력 2

1

Bar vf 1

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 구현
• 문자열

소스코드

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

import sys

input = sys.stdin.readline

sentence = list(input().rstrip())

result = []
for x in sentence:

    if x.isupper():
        if ord(x) + 13 <= 90:
            result.append(chr(ord(x) + 13))
        else:
            result.append(chr(ord(x) - 13))
    elif x.islower():
        if ord(x) + 13 <= 122:
            result.append(chr(ord(x) + 13))
        else:
            result.append(chr(ord(x) - 13))
    else:
        result.append(x)

for x in result:
    print(x, end='')

출처: [백준] 9093번 단어 뒤집기

문제

문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 공백이 하나 있다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 문장의 단어를 모두 뒤집어 출력한다.

예제 입력 1

1
2
3

2
I am happy today
We want to win the first prize

예제 출력 1

1
2

I ma yppah yadot
eW tnaw ot niw eht tsrif ezirp

출처

• ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Taejon 2001 PA번
  • 문제를 번역한 사람: baekjoon

알고리즘 분류

• 구현
• 문자열

소스코드

1
2
3
4
5
6
7
8
9
10
11
12

import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    sentence = list(input().rstrip().split(" "))
    for x in sentence:
        print(''.join(reversed(list(x))), end=" ")
    print()

출처: [백준] 10988번 팰린드롬인지 확인하기

문제

알파벳 소문자로만 이루어진 단어가 주어진다. 이때, 이 단어가 팰린드롬인지 아닌지 확인하는 프로그램을 작성하시오.

팰린드롬이란 앞으로 읽을 때와 거꾸로 읽을 때 똑같은 단어를 말한다.

level, noon은 팰린드롬이고, baekjoon, online, judge는 팰린드롬이 아니다.

입력

첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 팰린드롬이면 1, 아니면 0을 출력한다.

예제 입력 1

1

level

예제 출력 1

1

1

예제 입력 2

1

baekjoon

예제 출력 2

1

0

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: oopar2, pda_pro12

알고리즘 분류

• 구현
• 문자열

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import sys

input = sys.stdin.readline

input_string = list(input().rstrip())

while len(input_string) >= 1:
    if len(input_string) == 1:
        break
    elif input_string[0] == input_string[-1]:
        input_string.pop(0)
        input_string.pop(-1)
    else:
        print(0)
        exit(0)

print(1)

소스코드2

1
2
3
4
5
6
7
8
9
10
11
12

import sys

input = sys.stdin.readline

input_string = list(input().rstrip())
compare_string = list(reversed(input_string))

if input_string == compare_string:
    print(1)
else:
    print(0)

소스코드3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import sys

input = sys.stdin.readline

input_string = list(input().rstrip())
palindrome = 1
for i in range(len(input_string) // 2):
    if input_string[i] != input_string[len(input_string) - 1 - i]:
        palindrome = 0

if palindrome:
    print(1)
else:
    print(0)

출처: [백준] 1259번 팰린드롬수

문제

어떤 단어를 뒤에서부터 읽어도 똑같다면 그 단어를 팰린드롬이라고 한다. ‘radar’, ‘sees’는 팰린드롬이다.

수도 팰린드롬으로 취급할 수 있다. 수의 숫자들을 뒤에서부터 읽어도 같다면 그 수는 팰린드롬수다. 121, 12421 등은 팰린드롬수다. 123, 1231은 뒤에서부터 읽으면 다르므로 팰린드롬수가 아니다. 또한 10도 팰린드롬수가 아닌데, 앞에 무의미한 0이 올 수 있다면 010이 되어 팰린드롬수로 취급할 수도 있지만, 특별히 이번 문제에서는 무의미한 0이 앞에 올 수 없다고 하자.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다.

출력

각 줄마다 주어진 수가 팰린드롬수면 ‘yes’, 아니면 ‘no’를 출력한다.

예제 입력 1

1
2
3
4

121
1231
12421
0

예제 출력 1

1
2
3

yes
no
yes

출처

• ICPC > Regionals > South Pacific > South Pacific Region > New Zealand Programming Contest > NZPC 2006 B번
  • 문제를 번역한 사람: kks227

알고리즘 분류

• 구현
• 문자열

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import sys

input = sys.stdin.readline


def isPalindrome(value):
    for i in range(len(value)):
        if value[i] != value[len(value) - 1 - i]:
            return 0
    return 1


while True:
    num = int(input())
    if not num:
        break
    else:
        arr = list(str(num))
        if isPalindrome(arr):
            print('yes')
        else:
            print('no')

출처: [백준] 10798번 세로읽기

문제

아직 글을 모르는 영석이가 벽에 걸린 칠판에 자석이 붙어있는 글자들을 붙이는 장난감을 가지고 놀고 있다.

이 장난감에 있는 글자들은 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’이다. 영석이는 칠판에 글자들을 수평으로 일렬로 붙여서 단어를 만든다. 다시 그 아래쪽에 글자들을 붙여서 또 다른 단어를 만든다. 이런 식으로 다섯 개의 단어를 만든다. 아래 그림 1은 영석이가 칠판에 붙여 만든 단어들의 예이다.

1
2
3
4
5

A A B C D D
a f z z 
0 9 1 2 1
a 8 E W g 6
P 5 h 3 k x

<그림 1>

한 줄의 단어는 글자들을 빈칸 없이 연속으로 나열해서 최대 15개의 글자들로 이루어진다. 또한 만들어진 다섯 개의 단어들의 글자 개수는 서로 다를 수 있다.

심심해진 영석이는 칠판에 만들어진 다섯 개의 단어를 세로로 읽으려 한다. 세로로 읽을 때, 각 단어의 첫 번째 글자들을 위에서 아래로 세로로 읽는다. 다음에 두 번째 글자들을 세로로 읽는다. 이런 식으로 왼쪽에서 오른쪽으로 한 자리씩 이동 하면서 동일한 자리의 글자들을 세로로 읽어 나간다. 위의 그림 1의 다섯 번째 자리를 보면 두 번째 줄의 다섯 번째 자리의 글자는 없다. 이런 경우처럼 세로로 읽을 때 해당 자리의 글자가 없으면, 읽지 않고 그 다음 글자를 계속 읽는다. 그림 1의 다섯 번째 자리를 세로로 읽으면 D1gk로 읽는다.

그림 1에서 영석이가 세로로 읽은 순서대로 글자들을 공백 없이 출력하면 다음과 같다:

Aa0aPAf985Bz1EhCz2W3D1gkD6x

칠판에 붙여진 단어들이 주어질 때, 영석이가 세로로 읽은 순서대로 글자들을 출력하는 프로그램을 작성하시오.

입력

총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’ 중 하나이다. 각 줄의 시작과 마지막에 빈칸은 없다.

출력

영석이가 세로로 읽은 순서대로 글자들을 출력한다. 이때, 글자들을 공백 없이 연속해서 출력한다.

예제 입력 1

1
2
3
4
5

ABCDE
abcde
01234
FGHIJ
fghij

예제 출력 1

1

Aa0FfBb1GgCc2HhDd3IiEe4Jj

예제 입력 2

1
2
3
4
5

AABCDD
afzz
09121
a8EWg6
P5h3kx

예제 출력 2

1

Aa0aPAf985Bz1EhCz2W3D1gkD6x

출처

• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 초등부 2번
  • 데이터를 만든 사람: baekjoon

알고리즘 분류

• 구현
• 문자열

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import sys

input = sys.stdin.readline

input_string = [[0] * 15 for _ in range(5)]

for i in range(5):
    temp = list(input().rstrip())
    for j in range(len(temp)):
        input_string[i][j] = temp[j]

for i in range(15):
    for j in range(5):
        if input_string[j][i] == 0:
            continue
        else:
            print(input_string[j][i], end="")

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13

import sys

input = sys.stdin.readline

input_string = [list(input().rstrip()) for _ in range(5)]

for i in range(15):
    for j in range(5):
        if not input_string[j]:
            continue
        else:
            print(input_string[j].pop(0), end="")

출처: [백준] 1913번 달팽이

문제

홀수인 자연수 N이 주어지면, 다음과 같이 1부터 N2까지의 자연수를 달팽이 모양으로 N×N의 표에 채울 수 있다.

N이 주어졌을 때, 이러한 표를 출력하는 프로그램을 작성하시오. 또한 N2 이하의 자연수가 하나 주어졌을 때, 그 좌표도 함께 출력하시오. 예를 들어 N=5인 경우 6의 좌표는 (4,3)이다.

입력

첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.

출력

N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 출력한다.

예제 입력 1

1
2

7
35

예제 출력 1

1
2
3
4
5
6
7
8

49 26 27 28 29 30 31
48 25 10 11 12 13 32
47 24 9 2 3 14 33
46 23 8 1 4 15 34
45 22 7 6 5 16 35
44 21 20 19 18 17 36
43 42 41 40 39 38 37
5 7

출처

• 문제를 만든 사람: author5

알고리즘 분류

• 구현

소스코드

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
29
30
31
32
33
34
35
36
37

import sys

input = sys.stdin.readline

N = int(input())
M = int(input())

snail = [[0 for _ in range(N)] for _ in range(N)]

move = [(1, 0), (0, 1), (-1, 0), (0, -1)]  # 하, 우, 상, 좌

cur_num = N ** 2
cur_x, cur_y = 0, 0
direction = 0
while cur_num > 0:
    snail[cur_y][cur_x] = cur_num
    ny, nx = move[direction]
    dx = cur_x + nx
    dy = cur_y + ny
    if 0 > dx or dx >= N or 0 > dy or dy >= N or snail[dy][dx] != 0:  # 갈 수 없는 곳만 (방문했던 곳X, 벽X)
        direction = (direction + 1) % 4

    ny, nx = move[direction]
    cur_x += nx
    cur_y += ny
    cur_num -= 1

temp_x, temp_y = 0, 0
for i in range(N):
    for j in range(N):
        if snail[i][j] == M:
            temp_x = j
            temp_y = i
        print(snail[i][j], end=" ")
    print()
print(temp_y + 1, temp_x + 1)

출처: [백준] 1138번 한 줄로 서기

문제

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다.

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

예제 입력 1

1
2

4
2 1 1 0

예제 출력 1

1

4 2 1 3

출처

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: dsa2341, taedy0311

알고리즘 분류

• 구현

소스코드

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())

memo = list(map(int, input().split()))
result = [0 for _ in range(N)]
for i in range(N):
    cnt = 0
    for j in range(N):
        if memo[i] == cnt and result[j] == 0:
            result[j] = i + 1
            break
        elif result[j] == 0:
            cnt += 1

print(*result)