2일차

2020-09-03
초급 : 11719 그대로 출력하기 2 (Bronze I)

www.acmicpc.net/problem/11719

11719번: 그대로 출력하기 2

 

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    while (getline(cin, s)) {
        cout << s << "\n";
    }
    return 0;
}

 

from sys import stdin
def input(): return stdin.readline()

while 1:
    line = input()
    if not line: break
    print(line, end="")

 

C++은 getline 함수를 사용했다. 

자세한 내용은 http://www.cplusplus.com/reference/string/string/getline/ 에서 확인할 수 있다.

 

Python은 평소 쓰던 stdin.readline()을 써서 풀고 싶었다.

그냥 print(line) 했더니 개행까지 그대로 출력해 출력 형식 오류가 발생했다.

 

공백 등을 제거해주는 rstrip 함수를 항상 사용해서 놓치고 있던 부분이다.

 

 

중급 : 13413 오셀로 재배치 (Silver V)

www.acmicpc.net/problem/13413

13413번: 오셀로 재배치

 

from sys import stdin
def input(): return stdin.readline().rstrip()

for _ in range(int(input())):
    l, s1, s2 = int(input()), input(), input()
    b, w = 0, 0
    for i in range(l):
        if s1[i] == s2[i]: continue
        if s1[i] == "B": b += 1
        else: w += 1
    print(max(b, w))

 

색을 바꾸고 싶은 말이 몇 개 있는지 색깔별로 구분하여 센다.

 

검은색으로 바꾸고 싶은 말과 흰색으로 바꾸고 싶은 말이 하나씩 있다면, 둘을 각각 뒤집는 것보다 서로의 위치를 바꾸는 것이 더 빠른 방법이다.

 

그렇다면 위와 같은 쌍이 더는 없을 때 까지 위치를 바꾸어 준다.

이 작업은 min(검은색으로 바꾸고 싶은 말의 수, 흰색으로 바꾸고 싶은 말의 수) 번 하게 된다.

 

남은 말은 하나씩 뒤집어 주는 방법밖에 없다.

이 작업은 abs(검은색으로 바꾸고 싶은 말의 수 - 흰색으로 바꾸고 싶은 말의 수) 번 하게 된다.

 

둘을 더하면 결국 max(검은색으로 바꾸고 싶은 말의 수, 흰색으로 바꾸고 싶은 말의 수) 와 같다.

 

 

고급 : 13022 늑대와 올바른 단어 (Gold V)

www.acmicpc.net/problem/13022

13022번: 늑대와 올바른 단어

 

from sys import stdin
def input(): return stdin.readline().rstrip()

res = True
wDis = 0
base = 0
s = input()
sLen = len(s)
if s[0] != "w": res = False
if s[-1] != "f": res = False
s += "z"*51

for i in range(sLen):
    if not res: break
    if s[i] == "w":
        if wDis == 0: base = i
        wDis += 1
    else:
        if wDis > 0:
            for j in range(wDis):
                if s[base+wDis+j] != "o" or s[base+wDis*2+j] != "l" or s[base+wDis*3+j] != "f":
                    res=False
                    break
            if s[base+wDis*4] not in ["w", "z"]:
                res = False
        wDis = 0

print(1 if res else 0)

 

일단 w로 시작하지 않거나 f로 끝나지 않는 단어는 답이 될 수 없으니 바로 틀렸다고 저장한다.

 

올바른 단어의 예로 wwoollffwolf 가 주어졌을 때의 모습은 다음과 같다.

 

 

먼저 w가 처음 나온 위치를 저장하고, w가 몇 번 나오는지 wDis에 저장한다.

 

w가 아닌 문자가 등장하면, 시작 지점으로부터 wDis 만큼의 거리로 탐색 범위를 나누어 o, l, f가 필요한 만큼 올바른 위치에 있는지 검증한다.

 

마지막으로 f 뒤에 w가 오거나 문자열이 끝나는지 검증하면, 그 위치까지는 올바른 단어임을 확신할 수 있다.

 

 

이제 다음 위치에서부터 같은 작업을 반복하면 된다.

 

문자열이 끝날 때까지 틀렸음을 확인하지 못하면 올바른 단어라고 출력하면 된다.

 

 

 

검증하다가 잘못된 문자열임을 확인한 예시이다.

 

"wwwwwo" 같은 문자열은 범위 밖의 인덱스에 접근하려 할 텐데, 처리하기 귀찮아서 z 같은 입력에 들어오지 않는 문자를 뒤에 잔뜩 붙이는 잔꾀를 부렸다.